随机算法 (Fall 2011)

Lecture Notes

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

Future plan

Topics that I'm considering to cover at next time when I teach this class (perhaps):

• Janson's inequality,
• Talagrand's inequality
• The Poisson Approximation
• Fourier analysis
• Random graphs
• Entropy and randomness
• Derandomization
• Color-coding
• On-line algorithms
• Property testing
• Compressed sensing