| Date | Topic | Slides | Handout | Reference | Scribe Notes |
| 03/31/20 | Linearity of expectation, Randomized quicksort, Karger's mincut | lec1 | Youtube | MR 1, MU 2.11, 2.5 | Vishal's notes |
| 04/02/20 | The Hoeffding bound, implications for population estimation and binomial parameter estimation | lec2 | Youtube | MR 3 | Basu's notes |
| 04/07/20 | Chernoff bound to Poisson tails, high probability bounds for Randomized quicksort, the median estimation | lec3 | Youtube | MR 3 | Ross's notes |
| 04/09/20 | Importance sampling: Karp-Luby | lec4 | Youtube | MU 11-11.2 | Zehui's notes |
| 04/14/20 | Importance sampling: geometric random variables, improved Karp-Luby | lec5 | Youtube | Yatong's notes | |
| 04/16/20 | More importance sampling: Cohen-Lewis approximate matrix multiplication, a discussion of generating samples from a distribution | lec6 | Youtube | ||
| 04/21/20 | A showcase of techniques: Estimating the average degree of a graph through random sampling | lec7-alias lec7-avgdeg | Youtube-alias Youtube-avg-deg | Jayanth's notes (part 1) Jayanth's notes (part 2) | |
| 04/23/20 | Dimension reduction and the Johnson-Lindenstrauss lemma | lec8 | Youtube | Ross's notes | |
| 04/28/20 | Understanding the upper tail: moment generating functions, a proof of the Chernoff bound | lec9 | Youtube | MR 4, MU 4 | Nicolas' notes |
| 04/30/20 | Balls and bins | lec10 | Youtube | MU 5 | Nitin's notes |
| 05/05/20 | The Poisson approximation and Poissonization | lec11 | Youtube | MU 5 | Balaram's notes |
| 05/07/20 | Introduction to distribution testing | lec12 | Youtube | Goldreich (Intro to Property Testing), 11 | |
| 05/12/20 | Uniformity testing | lec13 | Youtube | Goldreich (Intro to Property Testing), 11 | |
| 05/14/20 | Introduction to streaming algorithms, counting distinct elements | lec14 | Youtube | Amit Chakrabarti's Dartmouth notes | Yatong's notes |
| 05/19/20 | The BJKST algorithm for distinct elements, heavy hitters, and reservoir sampling | lec15 | Youtube | Chap 2 of Amit Chakrabarti's notes | |
| 05/21/20 | The Count-Min sketch, estimating frequency moments, and AMS second-moment sketch | lec16 | Youtube | Chap 4, 5, 6 of Amit Chakrabarti's notes | Zehui's notes |
| 05/26/20 | The experts problem, the Randomized Weighted Majority algorithm | lec17 | Youtube | Deeparnab's Chakrabarty's Dartmouth notes | Basu's notes |
| 05/28/20 | Follow the Perturbed Leader | lec18 | Youtube | Bobby Kleinberg's Cornell notes Kalai-Vempala | Nicolas' notes |
| 06/02/20 | Lower bounds for regret minimization, Yao's minimax lemma | lec19 | Youtube |