GraphTheoretic Algorithms

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:
Schedule:
MWF 12: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.
depthfirst search, shortest path algorithms), algorithm design techniques
(e.g. greedy algorithms, dynamic programming), and algorithm analysis
(e.g. Onotation, NPhardness, reductions.)
In terms of Introduction to Algorithms
(T. Cormen, C. Leiserson, R. Rivest (& C. Stein)) you should know:
(1st edition) Chapters 114, 1618, 2326, 3637 or
(2nd edition) Chapter 113, 1517, 2225, 3435, Appendix AC.
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 theoremproving 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  020%  Completely optional, any credit not obtained transfers to the final exam. Meet with me 11 inperson 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 courserelated topic, write lecture notes, and create a video (or present the topic to the class).  
Final Exam  4060%  Oral questioning, 1on1, 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