Examination Description 

The mid-term exam will cover material from Notes 1 to 5, as well as the homework exercises. You are expected to understand the proofs of the theorems described in class. You might be asked to reproduce the crucial parts of a proof, or extend a proof to a more general case. You would also be told when you could use a result without proving it.

Rules: The usual rules of a written exam apply. No collaboration or communication allowed. This is a closed book exam. However, you are allowed to use the following items during the exam.

• A basic calculator. Although a calculator is not necessary for the exam, you can bring a calculator for basic calculation. Programmable calculators are fine, but calculators that can store pages of text are not allowed. In particular, laptops, iPhones and mobile phones are not acceptable.
• One sheet of A4 paper with notes on both sides.

Topics: The mid-term covers all materials taught up to the class on Oct 6, and Homeworks 1 and 2. The following topics are especially important.

• Method of Moment Generating Function for Measure Concentration.
• Proofs of Chernoff Bound/Hoeffding's Inequality.
• Use of convexity in dealing with continuous random variables (e.g. in the proof of Hoeffding's Inequality).
• Approximate Counting/Random Sampling.