Math 409, Discrete Optimization

Lecture:  MWF 9:30, Denny 314
Instructor:  Jim Morrow
Phone:  543-1161

E-mail:  morrow@math.washington.edu
Web address: http://www.math.washington.edu/~morrow/409 98/409.html

Office Hours: MW 10:30-11:30, C439 Padelford
TA:  Maya Geliazkova
Office Hours: TTh 9:30-10:30, C113 Padelford

E-mail:  geliazko@math.washington.edu

Text:  Combinatorial Optimization (required)
Author:  William Cook, et. al.
Text:  Algorithms and Complexity (required)
Author:  Herbert Wilf

Wilf’s book is available from Professional Copy ’n’ Print 4200 University Way NE

Math 409 investigates several topics connected with optimization and flow questions on networks. The following list of topics includes more than I can cover, so I will make some choices as the quarter proceeds.

1. Elementary estimation of orders of magnitude. (Wilf, §1.1 - 1.6; Cook, Chapter 1)

2. Graphs and networks – elementary properties and concepts. (Wilf, §1.6)

3. Recursive algorithms for graphs. (Wilf, §2.3)

4. Minimum spanning trees. (Cook, §2.1)

5. Shortest paths. (Cook, §2.2)

6. Network flow problems. (Wilf, §3.1 - 3.8; Cook, §3.1 - 3.3))

7. Minimum cost flow problems (Cook, §4.1)

8. Optimal matchings (Cook, §5.1 - 5.2)

9. Electrical networks (lectures)

10. Critical path analysis and scheduling (lectures)

11. Multi-terminal flow (lectures)

12. NP completeness (Wilf, §5.1 - 5.8; Cook, §9.1 - 9.9)

Homework will be collected at regular intervals and will count 30% of the course grade. There will be one 50 minute midterm test which will count 30% of the course grade. The midterm test will be closed book but you will be allowed to bring notes on one side of a notebook size sheet of paper. There will be a two hour closed book final exam which will count 40% of the course grade. For the final you will be allowed to bring notes on both sides of a notebook size sheet of paper. No calculators will be allowed on tests.

Here are the first few homework assignments :

DATE ASSIGNMENT
Apr. 6 Wilf, §1.1: 3; §1.4: 1(vii); §1.6: 12
Apr. 13 Wilf, §2.3: 8, 9, 11
Apr. 20 Cook, 2.1, 2.4, 2.5, 2.9
Apr. 27 Cook, 2,8, 2.19

May 4

May 6 MIDTERM

May 11 May 18 May 27 Jun 1 Jun 8

Jun. 10 FINAL EXAM (8:30-10:20 a.m.)

These assignments are due at the beginning of class on the due date.