随机算法 (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
   • Pair-wise Independence
   • Derandomization: Two-Point Sampling
5. Moment and Deviation
   • Chebyshev's Inequality
   • Median Selection
   • Random Graphs
   • Chernoff Bound
   • Set Balancing
6. Concentration of Measure
   • Routing in a Parallel Network
   • Martingales
   • Azuma's Inequality
   • The Method of Bounded Differences
7. Dimension Reduction
   • Johnson-Lindenstrauss Theorem
   • Locality Sensitive Hashing
8. The Probabilistic Method
   • The Probabilistic Method
   • Lovász Local Lemma
   • Derandomization: Conditional Expectation
9. Approximation Algorithms
   • Randomized Rounding
10. Markov Chain and Random Walk
11. Random Walk Algorithms
12. Coupling and Mixing Time
13. Expander Graphs
14. Sampling and Counting
15. MCMC
16. On-line Algorithms
17. Complexity
18. Horizon

1. Rapid mixing random walks