409 - Discrete Optimization - Winter 2025
Course information
- Class schedule: MWF
9:30am - 10:20am in MEB 246
- Instructor:
Thomas Rothvoss,
rothvoss@uw.edu.
Office hour: We 11-12 in PDL C440.
- TAs:
- Rainie Bozzai. Office hour: TBD
- 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 assignment 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. You may not use 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 on Ed.
- 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 6, 2025: First day of class. Logistics + Chapter
1.1 on "Algorithms and Complexity"
- Wednesday, Jan 8, 2025: Graph Theory
- Friday, Jan 10, 2025: TSP. Started with Chapter 2 on spanning
trees.
- Monday, Jan 13, 2025: Minimum spanning trees
- Wednesday, Jan 15, 2025: Finished Chapter 2 on spanning trees.
Just started with Chapter 3 on shortest paths.
Last class is Friday, Mar 14, 2025.
Problem sets
The solutions to the problem sets will be available later. You can
check your points on the GradeScope webpage.
Midterm exam
- Wednesday, Feb 12, 2025 in class (i.e. 9:30am-10:20am in MEB
246). You may bring one sheet of notes (printed on one side or
handwritten on both sides).
Final exam
- Wednesday, Mar 19, 2025, 8:30am - 10:20am in MEB 246. 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
- Jan 6, 2025: Minor typos in Chapter 1.