CSE290A - Randomized Algorithms

MR stands for Motwani-Raghavan, and MU stands for Mitzenmacher-Upfal.
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