Computer Science 160
Graph Theory
Fall 2019 Syllabus
http://www.cs.tufts.edu/comp/150GT


Handouts:

Announcements, homework assignments, project assignment, and other handouts will be posted on the class web pages http://www.cs.tufts.edu/comp/150GT/documents . Please check frequently. We may also decide to shift this predominantly to PIAZZA. Please sign up for the Comp 150GT PIAZZA group.

Brief Description:

Introduction to graph theory, including trees, matchings, connectivity, colorings, and planar graphs. There is no required programming in this class-- one may choose either an implementation project or a theoretical project-- but there are applications in computational geometry, computational biology, and algorithms.

Prerequisites:

COMP 160 OR COMP 170 OR any Math course numbered 100 or above.

Class Meetings in Bromfield-Pearson 002:

Thursdays, 6:00-9:15 PM, Block 13+ (N+/Q+)

TENTATIVE CLASS SCHEDULE

  • Thursday, 9/5: Lecture
  • Thursday, 9/12: Lecture
  • Thursday, 9/19: Group Problem Solving/Office Hours/Guest lecture
  • Thursday, 9/26: Lecture
  • Thursday, 10/3: Lecture, shortened: starts at 7:00pm (TA Office hours/Group Problem Solving from 6-7pm) UNLESS we can reschedule the class for Monday 9/30 or possible Tuesday 10/1.
  • Thursday, 10/10: Lecture
  • Thursday, 10/17: Lecture
  • Thursday, 10/24: Lecture
  • Thursday, 10/31: 90-minute exam on first 6 Lectures; 90 minute group problem session/project discussion/guest lecture UNLESS we can reschedule the class for Monday 10/28.
  • Thursday, 11/7: Lecture
  • Thursday, 11/14: Lecture
  • Thursday, 11/21: Group Problem Solving/Project work/Guest Lecture. UNLESS we can reschedule for Monday 12/2
  • Thursday, 12/5: Eleventh Lecture/Project Presentations/Examination
  • Friday, 12/13, 6:30-9:00pm (Assigned EXAM BLOCK) OR Friday, 12/12, at one of 8:30-11AM or 12-2:30PM or 3:30-6:00PM or 6:30-9:00PM: Examination/Project Presentations -- unless we can move it to Thursday, 12/12.

    Instructor: Prof. Diane L. Souvaine ( Diane.Souvaine@tufts.edu )

    Office: Halligan 239.
    Appointment sign-ups: http://www.cs.tufts.edu/~dls/advising.php . Email me if no slots are available, and I will add more.

    TA: Oliver Korten ( email )

    Office Hours: Tuesdays from 1:30-2:30 and Wednesdays from 12 - 1 in the Halligan Collaboration Room on the 2nd Floor

    Mail sent to ta150gt@cs.tufts.edu is sent to both Prof. Souvaine and to Oliver Korten.


    Textbook:

    Douglas West: Introduction to Graph Theory, 2nd edition, Prentice-Hall, 2001. ISBN 0-13-014400-2.
    http://www.amazon.com/Introduction-Graph-Theory-Douglas-West/dp/0130144002/ref=tmm_hrd_title_0
    Online: http://docshare01.docshare.tips/files/26167/261678089.pdf
    Can be rented or purchased through the Tufts Bookstore: https://tinyurl.com/F19-COMP-150-11

    Optional Reference:

    Béla Bollobás: Modern Graph Theory, Springer Science & Business Media, 1998. ISBN 978-0-387-98488-9.


    Expected Work:

    Students are expected to attend class regularly and to complete regular reading assignments in the text. Students are responsible for all material covered in class as will as all material covered in the assigned reading, whether or not the material is also covered in class. Graded course work will include weekly homework sets, occasional quizzes or in-class group problem solving, two examinations, a project including a write-up and oral presentation, and regular class participation.