Welcome to Math 409,
Spring 2009
(last updated June 4, 2009)
 No class on Friday, June 5!

For information about the final exam on Wednesday June 10,
see Handout 2
 HW 7 & 8 comments are posted below.
What is 409?
Math 409 studies discrete optimization,
which concerns minimizing/maximizing a function
of variables taking on discrete/integer values.
Examples include the Traveling Salesman problem, minimum spanning
tree problem, maximum matching problem, shortest path problem,
minimum cost network flow problem, and integer program.
These problems were first
studied in the 18th century by Euler and have important applications in
engineering, science, statistics, economics and management.
We will study the theory of and algorithms for solving these problems.
Since this is a fourth year math course, you will be expected
to do some proofs, as well as numerical examples.
Course Info:
 Instructor:
Paul Tseng (Padelford C344; tseng@math.washington.edu)
Office Hours: Tuesdays 2:003:30 pm or whenever I am free
 Lecture: MWF 11:3012:20 PM, Room
LOW 113
 Teaching Assistant:
Julie/Julia Eaton
(Padelford C404; jreaton@math.washington.edu)
Office Hours: Tuesday 10:3012:30 (or by arrangement)
 Textbook:
Course Notes (version March 2009).
References:
Applied Combinatorics, either 1st edition by Fred Roberts, 1984
or 2nd edition by Fred Roberts and Barry Tesman, 2003. [The book is also
on reserve at Math Research Library in Padelford.]
Prerequisites:
Math 407 and preferrably also Math 310.
Experience with mathematical proofs is needed.
This is a rigorous course in which less prepared students struggle.
Topics to be covered:
Graphs and digraphs, Eulerian paths, spanning trees,
minimum spanning trees,
shortest path, maximum flow, bipartite (optimal) matching,
integer program, NPcompleteness, traveling salesman problem.
Important Dates
 April 24, May 8, May 29
Quizzes 13 (1520 min).
 Fri, May 15 Midterm (50 min).
 Wed, June 10 (2:304:20) Final Exam (110 min).
Notes and Comments:
If you have any questions about the course, please feel free to email me at
tseng@math.washington.edu. This course gives a mathematically
rigorous treatment of discrete optimization and, as such,
proofs will be expected.
Handouts (Pdf files)
Homeworks (Pdf files)
 TA's Hmwk Guidelines
 Homework 1 (due April 8, 11:30 AM) ,
comments
 Homework 2 (due April 15, 11:30 AM) ,
comments
 Homework 3 (due April 22, 11:30 AM) ,
comments
 Homework 4 (due April 29, 11:30 AM)
,
comments
 Homework 5 (due May 6, 11:30 AM)
,
comments
 Homework 6 (due May 20, 11:30 AM) ,
comments
 Homework 7 (due May 27, 11:30 AM) ,
comments
 Homework 8 (due June 3, 11:30 AM) ,
comments
Links of Interest: Ø