随机算法 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
Line 40: | Line 40: | ||
#* [[随机算法 (Fall 2011)/Lovász Local Lemma|Lovász Local Lemma]] | #* [[随机算法 (Fall 2011)/Lovász Local Lemma|Lovász Local Lemma]] | ||
#* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]] | #* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]] | ||
# Approximation Algorithms | # Approximation Algorithms, On-line Algorithms | ||
#* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]] | #* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]] | ||
#* [[随机算法 (Fall 2011)/Linear Programming|Linear Programming]] | #* [[随机算法 (Fall 2011)/Linear Programming|Linear Programming]] | ||
#* [[随机算法 (Fall 2011)/Randomized Rounding|Randomized Rounding]] | #* [[随机算法 (Fall 2011)/Randomized Rounding|Randomized Rounding]] | ||
#* [[随机算法 (Fall 2011)/On-line Algorithms|On-line Algorithms]] | |||
# Markov Chain and Random Walk | # Markov Chain and Random Walk | ||
#* [[随机算法 (Fall 2011)/Markov Chains|Markov Chains]] | #* [[随机算法 (Fall 2011)/Markov Chains|Markov Chains]] |
Revision as of 15:49, 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, On-line Algorithms
- Markov Chain and Random Walk
- Random Walk Algorithms
- Coupling and Mixing Time
- Expander Graphs I
- Expander Graphs II
- Sampling and Counting
- MCMC
- Complexity