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 midterm 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 MoserTardos algorithm.
 You are given a problem closely related to maxcut and asked to mimic the application of the
semidefinite programming approach for maxcut and solve the given problem.