Math 409, Discrete Optimization, Spring 2018
Instructor : Rekha Thomas
- Office : Padelford C-438
- Office Phone : (206) 616 9374
- E-mail : rrthomas (at) u (dot) washington (dot) edu
(Please use email sparingly. Please talk to me in class for all the usual issues.)
- Office hours : Wednesday 3-4, Friday 11:30-12:30 (in Padelford C-438).
Teaching Assistant : Sean Griffin
- Office : Padelford C-552
- E-mail : stgriff (at) uw (dot) edu
- Office hours : Thursday 12-1 and Friday 1:30-2:30 pm (in Padelford C-552)
Course Information
- Lecture : MGH 231
MWF 10:30 - 11:20
- Textbook : Lectures will follow these notes
written by Professor Rothvoss.
There are 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, Prentice-Hall, 1982.
- B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21 Springer, Berlin Heidelberg New York, 2006.
- 3-volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency , Springer-Verlag, 2003.
- 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. You will be expected to
write proofs in homework and on tests.
-
Homeworks and Exams
- Homeworks (20% of overall grade):
There will be weekly homework assignments.
Homework is due on Mondays IN CLASS. No late homework can
be graded. 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) : Friday, April 27, in class.
- Final Exam (50% of overall grade) : 8:30-10:20 a.m.
Monday, June 4, MGH 231 (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 make-up exams: : Homeworks are due in
class on MONDAYS. 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
Week 1 (March 26 - 30)
Week 2 (April 2 - April 6)
Week 3 (April 9 - April 13)
-
Lecture Notes :
- Chapter 3: Shortest paths
-
Homework (complete) : (due Monday 4/16 in class)
Problem set 3
Week 4 (April 16 - April 20)
Week 5 (April 23 - April 27)
-
Lecture Notes :
- 4/23, 4/25: Chapter 4.4: Applications to bipartite matching
-
No Homework this week
- Midterm on Friday 4/27 in class (on Chapters 1-4)
Week 6 (April 28 - May 4)
Week 7 (May 7 - May 11)
Week 8 (May 14 - May 18)
-
Lecture Notes :
- Chapter 6: Total unimodularity
-
Homework (complete): (due Monday 5/21 in class)
Problem set 7
Week 9 (May 21 - May 25)
-
Lecture Notes :
- Chapter 7: Branch and bound
(The worked out example in the notes is now fixed.)
- Chapter 9: Knapsack problem
-
Homework (complete):
Problem set 8
Week 10 (May 29 - June 1)
Lecture Notes :
- Chapter 9: Knapsack problem
- Traveling salesman problem