Graph-Theoretic Algorithms Spring 2024 Outline

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Final

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: MWF 1-2:20pm, DC 2568. First meeting Monday, May 6, 2024.
The course will run on a condensed schedule, with 3 classes per week in May and June and no classes in July.

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; knowledge of 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; 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:

Participation	10%	You are expected to be physically in class, pay attention, and participate where suitable.
Assignments	0-20%	Completely optional, any credit not obtained transfers to the final exam. Meet with me 1-1 in-person and talk about some questions that I will post. (Depending on enrollment these may get switched to submitting written answers instead.)
Projects	30%	Pick a course-related topic, write lecture notes, and create a video (or present the topic to the class).
Final Exam	40-60%	Oral questioning, 1-on-1, in July or 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 information (yes, even ChatGPT). But: you must fully understand what you wrote and be able to explain 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