随机算法 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
| Line 41: | Line 41: | ||
#* [[随机算法 (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]] | ||
#* [[随机算法 (Fall 2011)/Derandomization: Color | #* [[随机算法 (Fall 2011)/Derandomization: Color-coding|Derandomization: Color-coding]] | ||
# Approximation Algorithms, On-line Algorithms | # Approximation Algorithms, On-line Algorithms | ||
#* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]] | #* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]] | ||
Revision as of 16:08, 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