随机算法 (Fall 2011)

Lecture Notes

1. Introduction
   • Complexity Classes
2. Probability basics
   • Probability Space
   • Verifying Matrix Multiplication
   • Conditional Probability
   • Randomized Min-Cut
   • Random Variables and Expectations
   • Randomized Quicksort
3. Balls and bins
   • Distributions of Coin Flipping
   • Birthday Problem
   • Coupon Collector
   • Balls-into-balls Occupancy Problem
   • Bloom Filter
   • Stable Marriage
4. Hashing and Fingerprinting

1. Tail inequalities
2. Chernoff bounds
3. Martingales
4. Hashing, limited independence
5. Fingerprinting
6. The probabilistic method
7. Markov chains and random walks
8. Expander graphs
9. Rapid mixing random walks
10. Random sampling, MCMC
11. Approximate counting
12. Randomized approximation algorithms
13. Distributed algorithms, data streams