## [ 409 - Discrete Optimization ]

### Course information

- Class schedule: MWF 10:30 - 11:20 in EEB 037
- Office hours: WE 4-5pm and TH 2-3pm (Padelford C442)
- Email: rothvoss@uw.edu
**TA:**Jiashan Wang

- E-mail: jsw1119@uw.edu
- Office: Padelford C-552

- Office hour: Tue and Thu 1:00 - 2:00 p.m.
**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 and cutting planes.-
**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. The file will be updated regularly.**Midterm exam:**The midterm exam will take place on**Friday, February 7**in class. A training exam is available on catalyst together with a study guide/FAQ. I will post solutions to the training exam on Tuesday, February 4.

### Problem sets

- Problem set 1 (due date: Friday, January 17 in class)
- Problem set 2 (due date: Friday, January 24 in class)
- Problem set 3 (due date: Friday, January 31 in class)
- Problem set 4 (due date: Friday, February 14 in class)
- Problem set 5 (due date: Friday, February 21 in class)
- Problem set 6 (due date: Friday, February 28 in class)
- Problem set 7
(due date: Friday, March 7 in class)

### Final exam

- The
**final exam**will take place**8:30-10:20am on Monday, March 17, 2014**in the usual lecture hall**EEB 037**

- A study guide with additional exercises is available here.

### 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.