Graph-Theoretic Algorithms Spring 2017 Outline

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Exams

Official course description from UW

Objective: To give the student further exposure to the design, analysis, and application of algorithms for problems defined on graphs.

Outline: For various graphs classes, we will study algorithms tailored to graphs in the class. Specific graph classes are:

• Planar graphs and friends, in particular outerplanar graphs.
• Interval graphs and friends, in particular chordal graphs.
• Trees and friends, in particular series-parallel graphs and graphs of bounded treewidth.
• Cross-connections: Using treewidth to solve problems in minor-free graphs.

Schedule: MW 10-11:50, DC 2568. First meeting Monday, May 1, 2017.

Required background: Students must have solid understanding of graph algorithms (e.g. depth-first search, shortest path algorithms), algorithm design techniques (e.g. greedy algorithms, dynamic programming), and algorithm analysis (e.g. O-notation, NP-hardness, reductions.)
In terms of Introduction to Algorithms (T. Cormen, C. Leiserson, R. Rivest (& C. Stein)) you should know: (1st edition) Chapters 1-14, 16-18, 23-26, 36-37 or (2nd edition) Chapter 1-13, 15-17, 22-25, 34-35, Appendix A-C. In terms of UW courses, you should have done well in CS341, and knowing at least one of CS466, CO342 or CO351 is helpful, but not required. The appendix of the lecture notes gives (very brief) overviews of some results that we need.
The course is purely theoretic (no programming.) On the other hand, there will be high demands on theorem-proving and argumentation of algorithm correctness.

Intended audience: Graduate students in Computer Science or Combinatorial Optimization. Undergraduate students may be admitted in exceptional cases; please contact the instructor. AUD credit will be given to students that pass the final exam.

References: Course notes from previous offerings will be made available to students.

Grade determination:

Assignments	0-30%	Written, with oral questioning as required. Any credit not obtained transfers to the final exam.
Projects	30%	Read a paper, write a summary and present it to me.
Final Exam	40-70%	Oral questioning, 1-on-1, in August.

Cheating policy: The cheating policy for this course is unusual and differs from the usual university policy. It is specifially allowed to collaborate with other students, use foreign sources such as the web, and any other means of copying. But: you must fully understand the solution, you must present it in your own words, and you must acknowledge all your sources.
I reserve the right to question you (orally) about anything that you submit in written, to make sure that you have fully understood it. If you haven't understood it, or failed to acknowledge your sources, this will be considered cheating or plagiarism and treated as such.

For more information: Please contact the instructor, Therese Biedl, at or see http://www.student.cs.uwaterloo.ca/~cs762.

Webmaster: