随机算法 (Fall 2011)

Lecture Notes

1. Introduction
2. Complexity classes, lower bounds
3. Balls and bins
4. Tail inequalities
5. Set balancing, packet routing, and metric embedding
6. Hashing, limited independence
7. Martingales
8. The probabilistic method
9. Markov chains and random walks
10. Expander graphs, rapid mixing random walks
11. Random sampling, MCMC
12. Approximate counting, linear programming
13. Randomized approximation algorithms
14. Fingerprinting
15. 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
• Learning and boosting
• Compressed sensing