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.
  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 Las Vegas algorithm that solves the SELECTION problem (see Homework 2, Problem 2 and a brief mention in Week 3 lecture notes).

  3. A problem on the Karger-Klein-Tarjan Sampling Theorem and the Karger-Klein-Tarjan MST algorithm.

  4. An application of Chernoff bounds to a setting you are familiar with such as the balls and bins problem or the sampling-based median-finding algorithm.