随机算法 (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
   • Balls and bins

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