About the midterm
The midterm exam will be from 6:30 pm to 8:30 pm in B13 MLH on Thursday, 10/4. You are free to use your notes, printouts, and textbooks during
the exam, but you cannot use any electronic devices. The exam is worth 20% of your grade.
The exam will consist of 4 poblems. 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 Las Vegas algorithm that solves the SELECTION problem
(see Homework 2, Problem 2 and a brief mention in Week 3 lecture notes).
 A problem on the KargerKleinTarjan Sampling Theorem and the KargerKleinTarjan MST algorithm.
 An application of Chernoff bounds to a setting you are familiar with
such as the balls and bins problem or the samplingbased
medianfinding algorithm.