About the midterm

The midterm exam will be from 6:30 pm to 8:30 pm in 110 MLH on Thursday, 10/17. You are free to use your notes and the textbook during the exam. The exam is worth 30% of your grade. The exam will consist of 6 poblems; these will be less challenging than the homework problems. Here is a brief description of of each problem.
  1. Analysis of a simple sampling scheme to show that the obtained sample has certain properties with probability bounded below by a constant. This will involve basic probability calculations and the use of inequalities such as 1+x <= e^x.

  2. Further analysis of the median-finding algorithm that is similar to randomized quicksort.

  3. A balls-and-bins analysis involving the computation of variance and the use of Chebyshev's inequality.

  4. A simple, direct application of Chernoff bounds.

  5. The analysis of a simple, distributed coloring algorithm. The algorithm is randomized and the analysis will involve a direct application of Chernoff bounds.

  6. Proving a Chernoff-type tail inequality in a setting nor covered in class. This will largely involve mimicking the original moment-generating-function-based proof of Chernoff.