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.
  1. The use of Chernoff bounds along with the probabilistic method to prove the existence of a graph with certain properties.

  2. The analysis of a given randomized rounding algorithm of a (given) LP relaxation of a combinatorial optimization problem.

  3. A simple application of the Lovasz Local Lemma and the Moser-Tardos algorithm.

  4. 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.