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.
- 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.
- Further analysis of the median-finding algorithm that is similar to randomized quicksort.
- A balls-and-bins analysis involving the computation of variance and the use of
Chebyshev's inequality.
- A simple, direct application of Chernoff bounds.
- The analysis of a simple, distributed coloring algorithm. The algorithm is randomized
and the analysis will involve a direct application of Chernoff bounds.
- 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.