Welcome to Math 409,
Spring 2008
(last updated June 4, 2008)
- No class on Friday, June 6.
For information about the final exam on Wednesday June 11,
see Handout 2
- HW 8 has been graded and can be picked up from outside of
PDL C-344. HW 8 comments are posted below.
- If you are interested in participating in
a survey of undergrad study habits (conducted by
Professor Jaime Diaz in the Dept. Psychology &
Behavioral Neuroscience at UW), see
this webpage It promises two iPod Shuffles being raffled
to survey takers.
- If you are interested in spending July 14-August 8 this summer
in Vancouver (Burnaby, actually) Canada doing
mathematical research in groups on real-world problems, check out the
MITACS Industrial Math Summer School
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 C-344; tseng@math.washington.edu)
Office Hours: Tuesdays 2:00-3:30 pm or whenever I am free
- Lecture: MWF 11:30-12:20 PM, Room
SMI 304
- Teaching Assistant:
Ting-Kei Pong
(Padelford C-8D; tkpong@math.washington.edu)
Office Hours: Tuesdays 3:30-5 PM or by arrangement
- Textbook:
Course Notes (version March 2008).
Recommended:
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, NP-completeness, traveling salesman problem.
Important Dates
- April 25, May 9, May 30
Quizzes 1--3 (15-20 min).
- Fri, May 16 Midterm (50 min).
- Wed, June 11 (2:30-4: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 9, 11:30 AM) ,
comments
- Homework 2 (due April 16, 11:30 AM) ,
comments
- Homework 3 (due April 23, 11:30 AM) ,
comments
- Homework 4 (due April 30, 11:30 AM) ,
comments
- Homework 5 (due May 7, 11:30 AM) ,
comments
- Homework 6 (due May 21, 11:30 AM) ,
comments
- Homework 7 (due May 28, 11:30 AM) ,
comments
- Homework 8 (due June 4, 11:30 AM) ,
comments
Links of Interest: Ø