[ 409  Discrete Optimization ]
Course information
 Class schedule:
MWF 10:30  11:20 in MUE 155
 Office hours:
Monday 12  1pm and Wednesday 12pm (Padelford C440)
 Email:
rothvoss@uw.edu
 TA:
Amy Wiebe
 Email: awiebe@uw.edu
 Office: Padelford
C132
 Office hour:
Thursday 1011am
 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%), 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 in class.
Late submission: You are allowed to submit the
problem sets in the lecture following the deadline, but then
the reached points will count with only 80%.
 Lecture notes for the course are available here
(I made some changes in chapter 8 on May 26, 2017 and fixed
a typo on May 30)
 Midterm exam: The midterm exam will take place
Wednesday, May 3 in class. You may bring one sheet of
notes (either printed on one side or handwritten on both
sides).
Problem sets
The solutions to the problem sets will be available via the
class mailing list. You can check your points on the catalyst
webpage.
Final exam

Time and place:
Monday, June 5, 2017, 8:3010:20, MUE 155
Text books
The lecture notes will contain all information given in the
lecture. 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.