409 - Discrete Optimization - Winter 2026
Course information
- Class schedule: MWF
8:30am - 9:20am in CMU 120
- Instructor:
Thomas Rothvoss,
rothvoss@uw.edu.
Office hour: We 10-11 in PDL C440.
- TAs:
- Tracy
Chin. Office hour: Thursdays 11am-noon in PDL C-110.
- Topics to be covered: computational complexity, minimum
spanning trees, shortest paths, max flow problems, min cost flow
problems, matchings, traveling salesman problem, integrality of
polytopes.
- Prerequisites : This course requires a good working
knowledge of Math 407 (Linear Programming) and Math 308 (Linear
Algebra).
- Grading: The grade will be a convex combination of the
performance in the submitted problem sets (20%; lowest scoring
assignment is dropped), the mid term exam (30%) and the final
exam (50%).
- Problem sets: Problem sets will be posted each Friday;
due date is the following Friday 11pm via GradeScope.
Late policy: GradeScope will accept submissions until
Monday 11pm. Every student is allowed 6 late days in total. So
you are allowed to submit for example 6 assignments up to 24h
late or two assignments 3 days late. No prior approval required.
Simply submit to GradeScope when you are done. If you submit
late and you are out of late days the submission counts 0.
Collaboration policy: You are allowed (in fact
encouraged) to discuss the homework problems in groups. You may
submit the solutions in groups up to 3. Each group is required
to write up their own solutions. Absolutely identical submission
will be considered as a violation of this policy. AI may not be
used in any form in solving the homework problems. You may not
use or rely on pre-existing solutions from the internet or
elsewhere.
- Lecture notes for the course are available here
- Discussion forum: Other than in office hours, you may
ask questions on course content and homework on the course
discussion forum.
- Religious Accommodations: Washington state law requires
that UW develop a policy for accommodation of student absences
or significant hardship due to reasons of faith or conscience,
or for organized religious activities. The UWs policy, including
more information about how to request an accommodation, is
available at https://registrar.washington.edu/staffandfaculty/religious-accommodations-policy/.
Accommodations must be requested within the first two weeks of
this course using the Religious Accommodations Request form, see
https://registrar.washington.edu/students/religious-accommodations-request/.
Covered material
- Monday, Jan 5, 2026: First day of class. Logistics + Chapter
1.1 on "Algorithms and Complexity"
- Wednesday, Jan 7, 2026: Graph Theory
- Friday, Jan 9, 2026: TSP. Started with Spanning Trees.
- Monday, Jan 12, 2026: Theorem 3 in Spanning trees.
- Wednesday, Jan 14, 2026: Spanning trees (Lemma 4 and Theorem
5).
- Friday, Jan 16, 2026: Kruskal's algorithm. Shortest paths and
Bellman's Principle.
- Monday, Jan 19, 2026: MLK Day --- NO CLASS
- Wednesday, Jan 21, 2026: Dijkstra's algorithm.
- Friday, Jan 23, 2026: The Moore-Bellman-Ford algorithm.
- Monday, Jan 26, 2026: Finished shortest path chapter. Beginnig
of flow chapter.
- Wednesday, Jan 28, 2026: The Ford Fulkerson algorithm. The s-t
MinCut problem.
- Friday, Jan 30, 2026: The MaxFlow=MinCut Theorem. The
Edmonds-Karp algorithm.
- Monday, Feb 2, 2026: Completed the Edmons-Karp algorithm.
Reduction from matchings in bipartite graphs to maximum flows.
- Wednesday, Feb 4, 2026: Koenig's Theorem.
- Friday, Feb 6, 2026: Proof of Hall's Theorem. Polyhedra,
polytopes and convexity.
- Monday, Feb 9, 2026: Characterization of extreme points. Weak
duality.
- Wednesday, Feb 11, 2026: MIDTERM EXAM
Last class is Friday, Mar 13, 2026.
Problem sets
The solutions to the problem sets will be available later. You can
check your points on the GradeScope
webpage.
Midterm exam
- Feb 11, 2026, in class. You will be allowed to bring one sheet
of notes (printed on one side or handwritten on both sides).
Final exam
- Tuesday, Mar 17, 2026, 8:30am - 10:20am in CMU 120. You may
bring one sheet of notes (printed on both sides or handwritten
on both sides).
Text books
The lecture notes will contain all information given in the lecture
and will be fully sufficient for the exams. However, for additional
information, I recommend the following text books:
- "Combinatorial Optimization" by
Cook, Cunningham,Pulleyblank, Schrijver: Contains most topics
that are also covered in class (plus many more). A very
readable, though quite expensive book.
- "Computational complexity" by Arora
and Barak: State of the art book for complexity theory.
From the topics covered in class, this book contains only the
small complexity part. A preliminary version is available for
free here.
Corrections to the lecture notes