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

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.