随机算法 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
| Line 41: | Line 41: | ||
#* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]] | #* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]] | ||
# Approximation Algorithms | # Approximation Algorithms | ||
#* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]] | |||
#* [[随机算法 (Fall 2011)/Linear Programming|Linear Programming]] | |||
#* [[随机算法 (Fall 2011)/Randomized Rounding|Randomized Rounding]] | #* [[随机算法 (Fall 2011)/Randomized Rounding|Randomized Rounding]] | ||
# Markov Chain and Random Walk | # Markov Chain and Random Walk | ||
Revision as of 14:33, 19 July 2011
Lecture Notes
- Introduction
- Probability Basics
- Balls and Bins
- Moment and Deviation
- Hashing and Fingerprinting
- Chernoff Bound
- Concentration of Measure
- Dimension Reduction
- The Probabilistic Method
- Approximation Algorithms
- Markov Chain and Random Walk
- Random Walk Algorithms
- Coupling and Mixing Time
- Expander Graphs
- Sampling and Counting
- MCMC
- On-line Algorithms
- Complexity