####
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.

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.