随机算法 (Fall 2011)

Lecture Notes

1. Introduction
   • Randomized Algorithms: an 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. Moment and Deviation
   • Markov's Inequality
   • Chebyshev's Inequality
   • Median Selection
   • Random Graphs
5. Hashing and Fingerprinting
   • Pair-wise Independence
   • Derandomization: Two-Point Sampling
6. Chernoff Bound
   • Chernoff Bound
   • Set Balancing
   • DNF Counting
   • Routing in a Parallel Network
7. Concentration of Measure
   • Martingales
   • Azuma's Inequality
   • The Method of Bounded Differences
8. Dimension Reduction
   • Johnson-Lindenstrauss Theorem
   • Locality Sensitive Hashing
9. The Probabilistic Method
   • The Probabilistic Method
   • Lovász Local Lemma
   • Derandomization: Conditional Expectation
   • Derandomization: Color Coding
10. Approximation Algorithms, On-line Algorithms
    • Max-SAT
    • Linear Programming
    • Randomized Rounding
    • On-line Algorithms
11. Markov Chain and Random Walk
    • Markov Chains
    • Random Walks on Undirected Graphs
    • Electrical Network
    • Cover Time
    • Graph Connectivity
12. Random Walk Algorithms
    • Randomized 2SAT
    • Randomized 3SAT
    • Perfect Matching in Regular Bipartite Graph
    • The Metropolis Algorithm
    • Dynamics on Spins
13. Coupling and Mixing Time
    • Mixing Time
    • Coupling
    • Card Shuffling
    • Path Coupling
    • Graph Coloring
14. Expander Graphs I
    • Expander Graphs
    • Graph Spectrum
    • The Spectral Gap
    • Random Walk on Expander Graph
15. Expander Graphs II
    • Expander Mixing Lemma
    • Chernoff Bound for Expander Walks
    • The Zig-Zag Product
    • USTCON in LOGSPACE
16. Sampling and Counting
    • The #P Class and Approximation
    • DNF Counting
    • Canonical Paths
    • Count Matchings
    • Sampling and Counting
17. MCMC
    • Spin Systems
    • Simulated Annealing
    • Volume Estimation
18. Complexity