随机算法 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
|||
| Line 17: | Line 17: | ||
#* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]] | #* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]] | ||
# Hashing and Fingerprinting | # Hashing and Fingerprinting | ||
#* [[随机算法 (Fall 2011)/Pair-wise Independence|Pair-wise Independence]] | |||
#* [[随机算法 (Fall 2011)/Derandomization: Two-Point Sampling|Derandomization: Two-Point Sampling]] | |||
# Moment and Deviation | # Moment and Deviation | ||
#* [[随机算法 (Fall 2011)/Chebyshev's Inequality|Chebyshev's Inequality]] | #* [[随机算法 (Fall 2011)/Chebyshev's Inequality|Chebyshev's Inequality]] | ||
Revision as of 02:40, 19 July 2011
Lecture Notes
- Introduction
- Probability basics
- Balls and bins
- Hashing and Fingerprinting
- Moment and Deviation
- 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
- Horizon