Slides. Annotated slides. Reading: MIT short videos and exercises on probability (Unit 4). Khan academy probability lessons (a bit more basic, Units 7 and 9). Chapters 1-3 of Probability and Computing for basic probability: events, random variables, expectation, and variance.
Lecture 2 (09/04 Thu): Linearity of Expectation and Variance. Counting Duplicates. Markov’s Inequality.
Slides. Annotated slides. Reading: Chapters 2.1-2.2 of Probability and Computing for linearity of expectation and Bernoulli (indicator) random variables. Chapter 3.1 for Markov's inequality.
Lecture 3 (09/09 Tue): Fully Random, Pairwise Independent, and Two-Universal Hash Functions. Collision-Free and Two-Level Hashing.
Slides. Reading: Chapters 13.1 and 13.3 of Probability and Computing for hash functions. Section 1.3 of notes by Sanjeev Arora and Pravesh Kothari at Princeton for constructing 2-universal hash functions. Pages 11-23 of slides by Kevin Wayne at Princeton for asymptotics and big O notation.
Lecture 4 (09/11 Thu): Hashing for Load Balancing. Chebyshev's Inequality. The Union Bound.
Slides to be posted. Reading: Chapter 3.3 of Probability and Computing for Chebyshev's inequality.