About the final
The midterm exam will be from 8:00 pm to 10:00 pm in 302 LC (our classroom) on Wednesday, 12/18.
You are free to use your notes, printouts from the web and the textbook during
the exam. The exam is worth 30% of your grade.
The exam will consist of 4 poblems; these will be less challenging than the homework problems and also
less challenging than the mid-term problems. Here is a
brief description of of each problem.
The use of Chernoff bounds along with the probabilistic method to prove the existence of
a graph with certain properties.
- The analysis of a given randomized rounding algorithm of a (given) LP relaxation of
a combinatorial optimization problem.
- A simple application of the Lovasz Local Lemma and the Moser-Tardos algorithm.
- You are given a problem closely related to maxcut and asked to mimic the application of the
semi-definite programming approach for maxcut and solve the given problem.