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 with Oliver Korten from 6:00-7:20pm. Lecture by Hugo Alves Akitaya from 7:30-8:50pm.
  • Thursday, 9/26: Lecture
  • Thursday, 10/3: Lecture by Oliver Korten from 6:00-7:20pm. Lecture by DLS from 7:35-8:50pm.
  • Thursday, 10/10: Lecture
  • Thursday, 10/17: Lecture
  • Thursday, 10/24: Lecture
  • Thursday, 10/31: First exam from 6:00-7:20pm. Lecture by Anselm Blumer from 7:30-9
  • Thursday, 11/7: Lecture
  • Thursday, 11/14: Lecture
  • Thursday, 11/21: Guest lecturer/Problem Solving/Project Work!!
  • Thursday, 12/5: Project Presentations and Final Lecture
  • Friday, 12/13, 6:00-8:00pm or 7:00-9:00pm.

    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.