## CS174 Spring 2008 Lecture Notes

#### Readings Key: MU = Mitzenmacher and Upfal

 Lect. Date Topics Readings 1 1/23 Introduction; events & probability MU Sections 1.1-1.2 2 1/28 Verifying matrix multiplication; Minimum cut MU Sections 1.3-1.4 3 1/30 Random variables and expectation MU Section 2.1 4 2/4 Binomial and geometric distributions; coupon collecting; Quicksort MU Sections 2.2, 2.4-5 5 2/6 Markov's inequality; variance; Chebyshev's inequality MU Sections 3.1-3 6 2/11 Chebyshev's inequality; Coupon collecting bounds MU Sections 3.3 7 2/13 Randomized median finding, generating functions (notes) MU Section 3.4 8 2/20 no class 9 2/25 Chernoff bounds; set balancing MU Sections 4.2-4 10 2/27 Proof of Chernoff bounds; randomized routing MU Sections 4.2, 4.5 3/3 Midterm 1 in class 11 3/5 Wrap-up routing, Intro. to statistical testing MU Section 4.5 12 3/10 Stats: Hypothesis Testing Online notes 13 3/12 Stats: Permutation Tests and Bootstrapping Online notes 14 3/17 Birthday problem MU Sections 5.1 15 3/19 Poisson distribution and Bloom Filters MU Sections 5.3, 5.5 16 3/31 Random graphs; Hamiltonian cycle algorithm MU Section 5.5 17 4/2 Hamiltonian cycle algorithm MU Sections 5.6 18 4/7 Probabilistic method; method of conditional expectations MU Sections 6.2, 6.3 19 4/9 More on the probabilistic method; thresholds in random graphs MU Section 6.4, 6.5 20 4/14 Markov chains; 2-SAT MU Section 7.1 21 4/16 Markov chains: gambler's ruin, stationary distributions, fundamental theorem MU Sections 7.2-3 4/21 Midterm 2 in class 22 4/23 Markov chains: examples; card shuffling, random walks, simple queue, cover time MU Sections 7.3-4 23 4/28 Markov chain Monte Carlo; Metropolis algorithm MU Sections 10.3 (no details), 10.4 24 4/30 Martingales MU Sections 12.1-2 25 5/5 Tail bounds for Martingales MU Section 12.4 26 5/7 27 5/12 Applications of Martingales MU Section 12.5