flâneur

CSE290A - Randomized Algorithms

users.soe.ucsc.edu · 310 words · saved by 1 readers

CSE290A - Randomized Algorithms Schedule 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-

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…

saved by

related reading