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