Math 409, Discrete Optimization, Spring 2010
Instructor : Rekha Thomas
 Office : Padelford C438
 Office Phone : (206) 616 9374
 Email : rrthomas (at) u (dot) washington (dot) edu
 Office hours : Monday 14 pm (in Padelford C438).
Grader : Christopher McMurdie
 Office : Padelford C404
 Email : mcmurdie (at) math (dot) washington (dot) edu
 Office hours : Tuesday 45:30 pm (in Padelford C404).
Course Information
 Lecture : Loew (LOW) 102,
MWF 11:30  12:20
 Textbook : There is no official textbook for this class. The syllabus will be
covered through lecture notes that will be posted on this web page.
There are however many good books on discrete and combinatorial optimization that you can
consult if you would like to read more. Here are some recommendations.
 J. Lee, A First Course in Combinatorial Optimization, Cambridge University Press, 2004.
 W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver, Combinatorial Optimization.
 C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, PrenticeHall, 1982.
 B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21 Springer, Berlin Heidelberg New York, 2006.
 3volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency , SpringerVerlag, 2003.
 Topics to be covered : running time of algorithms,
minimum spanning trees, shortest paths, max flow problems, min cost flow
problems, matchings, assignments, matroid optimization, traveling salesman problem,
general methods for integer programs.
 Prerequisites : This course requires a good working
knowledge of Math 407 (Linear Programming) and Math 308 (Linear
Algebra). The material covered in these two courses will be assumed to
be familiar to students throughout this course. Please review these
materials if you took these classes a while ago.

Homeworks and Exams
 Homeworks (20% of overall grade):
The mechanics: There will be weekly homework assignments
consisting of about five problems each.
Homework is due on Wednesdays IN CLASS. No late homework can
be graded. I will post each lecture on this web page and the lecture
notes contain the exercises for this course. A subset of these
problems will be assigned as homework each week. The list will be
posted below in the section titled "Weekly assignments". Homework problems
relevant to a lecture will be posted immediately after the lecture.
Please check the website over the weekend to make sure you have the
full assignment for the next Wednesday. A subset of the problems
will be graded each week.
Expectations: The homework problems are meant to improve your
understanding of the material taught in class. About fifty percent of
both exams will consist of problems related to the homework
problems. Homework is worth only 20% of the overall grade. Thus it
would be worthwhile to spend most of your time really understanding
how to solve these problems as opposed to just turning in the
solutions. You must understand the problems well enough to be able to
work with variants of these questions. I would like to encourage you
to talk to your fellow students and to work together to understand
the material. However, solutions have to be written individually.
 Exams (80% of overall grade):
There will be two exams : a midterm exam and a final exam.
NO NOTES ARE ALLOWED IN EXAMS.
 Midterm Exam (30% of overall
grade) : Wednesday, May 5, in class.
 Final Exam (50% of overall grade) : Wednesday, June 9, 2:304:20 p.m. in
LOW 102 (usual classroom)
General Comments
 Guidelines on how to write up solutions to problems:
You must show all your work to get full credit. Explain your
steps or methods clearly. Use words to give such explanations if
needed. After you have written a solution ask yourself if someone else
in the class could follow and understand your solution easily. Always
put yourself in the shoes of the grader when you write solutions to
problems. It is important that it be apparent to the grader that you
did this work on your own and that he/she understands your logic. Make
it easy to grade your work. This also requires you to be organized and
clear in your writing. Writing that is hard to understand or
disorganized will be assumed to be wrong.
 Late homeworks and makeup exams: : Homeworks are due in
class on WEDNESDAYS. No late homeworks will be accepted. Exams can only
be made up because of illnesses or other serious reasons. In these
situations, I will need written documentation explaining the
situation. Please let me know as soon as possible if you cannot take
an exam on the scheduled date.
 Partial Credit: There might be several questions on an
exam that carry no partial credit. This is usually because of the
nature of the question where a partially correct answer may make no
sense at all. For instance, a misstated theorem or definition is just
a false statement and couldn't be graded with partial credit. It is
important to learn to do computations and make arguments correctly
from beginning to end.
 Keep records : Please hold on to all your graded
homeworks and exams until you receive your final grade. You
will be asked to produce these if there are any questions or
complications regarding records during the quarter.
 Tips on getting a good grade:
 Read all assigned reading materials. It is
very important to really understand the concepts (as opposed to
memorizing facts). It is not enough to know recipes to solve numerical
problems. You will be asked questions that test your understanding of
the material. A good way to find out whether you really understand
something is to try to explain it to someone. You might be surprised
to see how hard it is to accurately explain/reproduce a concept that
you think you understand.
 Write clearly and correctly. Be logical in your arguments. Learn
definitions and statements of theorems accurately. Remember that I can
only evaluate your written work and so it is important to convey your
knowledge precisely in your writing.
 Do the homework problems. Even if you understand the material, it
is hard to reproduce this on a test without practice. It's important
to learn to work relatively quickly. This can only come with
practice.
 Come to office hours or talk to me if you are having
trouble. Let me know early in the quarter if you are having problems
with the course for whatever reason.
Weekly Assignments
(This section is updated after every
lecture and completed each Friday night. The lecture notes are cobbled
together from various books. In particular I have liberally borrowed
material from the books recommended above. Figures might be missing
from the notes. They are usually drawn in class. They will eventually
show up in the notes. )
Week 1 (March 29  April 2)
Week 2 (April 5  April 9)
Week 3 (April 12  April 16)
Week 4 (April 19  April 23)
Week 5 (April 26  April 30)

Lecture Notes :

Homework (complete): (due Friday 5/14 in class)
Lecture 13, Exercises 2,3
Lecture 14, Exercise 5
Lecture 16, Exercise 5
Lecture 17, Exercises 4,6,7
Solutions
Week 6 (May 3  May 7)
Midterm on Wednesday, May 5.
Solutions
Week 7 (May 10  May 14)

Lecture Notes :

Homework (complete): (due Wednesday 5/19 in class)
Lecture 17, Exercise 8
Lecture 1921, Exercises 4, 5
Solutions
Week 8 (May 17  May 21)

Lecture Notes :

Homework (complete): (due Wednesday 5/26 in class)
Lecture 22, Exercises 2,6,8
Lecture 23, Exercise 1
Solutions
Week 9 (May 24  May 28)
Week 10 (June 1  June 4)
Lecture Notes :
Final Exam
YOU MAY BRING A 8.5x11 PAGE WITH NOTES TO THE FINAL EXAM  WRITTEN ON BOTH
SIDES.