随机算法 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
| Line 74: | Line 74: | ||
#* [[随机算法 (Fall 2011)/The #P Class and Approximation|The #P Class and Approximation]] | #* [[随机算法 (Fall 2011)/The #P Class and Approximation|The #P Class and Approximation]] | ||
#* [[随机算法 (Fall 2011)/DNF Counting|DNF Counting]] | #* [[随机算法 (Fall 2011)/DNF Counting|DNF Counting]] | ||
#* [[随机算法 (Fall 2011)/Canonical Paths|Canonical Paths]] | #* [[随机算法 (Fall 2011)/Canonical Paths|Canonical Paths]] | ||
#* [[随机算法 (Fall 2011)/Count Matchings|Count Matchings]] | #* [[随机算法 (Fall 2011)/Count Matchings|Count Matchings]] | ||
#* [[随机算法 (Fall 2011)/Sampling and Counting|Sampling and Counting]] | |||
# MCMC | # MCMC | ||
#* [[随机算法 (Fall 2011)/Spin Systems|Spin Systems]] | #* [[随机算法 (Fall 2011)/Spin Systems|Spin Systems]] | ||
Revision as of 15:47, 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 I
- Expander Graphs II
- Sampling and Counting
- MCMC
- Complexity