Math 409, Discrete Optimization, Winter 2019
Instructor : Rekha Thomas
- Office : Padelford C-438
- E-mail : rrthomas (at) uw (dot) edu
(Please use email sparingly. Please talk to me in class for all the usual issues.)
- Office hours : TBA
Friday 12:00-2:00
Teaching Assistant : Amy Wiebe
- Office : Padelford C-132
- E-mail : awiebe (at) uw (dot) edu
- Office hours : Wednesday 1:30-3:30
Course Information
- Lecture : MGH 231
MWF 9:30 - 10: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.
You may bring one 8.5x11 sheet of paper with notes, written
on both sides.
- Midterm Exam (30% of overall
grade) : Monday, February 11, in class.
- Final Exam (50% of overall grade) : 8:30-10:20 a.m.
Wednesday, March 20, 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. In general, partial credit will be awarded rather sparingly in
this class, both on homework and on exams.
- 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 (Jan 7-11)
-
Read from Lecture Notes :
- Chapter 5.1: Linear programming
-
Homework: (due Monday 1/14 in class)
Problem set 1
Week 2 (January 14-18)
-
Read from Lecture Notes :
-
Homework: (due Monday 1/23 in class)
Problem set 2
Week 3 (January 22-25)
-
Read from Lecture Notes :
-
Homework: (due Monday 1/28 in class)
Problem set 3
Week 4 (January 28 - February 1)
-
Read from Lecture Notes :
-
Homework: (due Monday 2/4 in class)
Problem set 4
Week 5 (Feb 4 - 8)
-
Lecture Notes :
- Chapter 7: Branch and Bound
-
Homework (complete) : (due Monday 2/11 in class)
Problem set 5
Week 6 (Feb 11 - 15)
-
Lecture Notes :
-
Homework: (due !!!! Wednesday 2/20 !!! in class)
Problem set 6
Midterm on Friday Feb 15 in class on Chapters 1,2,5
Week 7 (Feb 19-22)
-
Lecture Notes :
- Chapter 4.4: Applications to bipartite matching
-
Homework (incomplete) : (due Monday 3/4 in class)
Problem set 7
Week 8 (Feb 25 - March 1)
Week 9 (Mar 4-8)
-
Lecture Notes :
- Traveling Salesman Problem
- Chapter 9: Knapsack Problem
-
Homework:
Problem set 9
Week 10 (Mar 11-15)
-
Lecture Notes :
- Chapter 3: Shortest paths
-
Last Homework:
Problem set 10