Graph-Theoretic Algorithms Spring 2020 Outline

Resources

Outline

Summaries

Project

Exams

Delivery

Official course description from UW

Official outline. The content below should be the same for all strict rules, but exapnds on some details.

Objective: Gain further experience with to the design and analysis on of algorithms, especially for problems on graphs with a special structure. Learn about major algorithmic techniques, especially treewidth, separators, and bidimensionality. Practice technical reading and presentation skills.

Topics: 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: Online. New material (equivalent to about 110 minutes of class time) will be uploaded twice per week from May 11 to Jul 10 on LEARN.

Intended audience: Graduate students (in CS or C&O) with strong interest in algorithms. Undergraduate students may be admitted in exceptional cases; please contact the instructor.

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). A detailed list is available on the web page.
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.

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

Grade determination:

Quizzes	0-9%	Short-answer questions, written, graded pass/fail. Any credit not obtained transfers to the final exam.
Assignment	0-27%	Written, with possible oral questioning in an online-meeting. Any credit not obtained transfers to the final exam.
Projects	40%	Prepare a course lecture (both lecture notes and videos) for a topic related to the course.
Final Exam	24-60%	Oral questioning in an online-meeting, 1-on-1, in August.

AUD credit will be given to students that pass the final exam.

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 (both within the course and outside), and to use foreign sources such as the web. 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://cs.uwaterloo.ca/~biedl/cs762.

Webmaster: