随机算法 (Fall 2011): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
Line 17: Line 17:
#* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]]
#* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]]
# Hashing and Fingerprinting
# Hashing and Fingerprinting
# Moment and Deviation
#* [[随机算法 (Fall 2011)/Chebyshev's Inequality|Chebyshev's Inequality]]
#* [[随机算法 (Fall 2011)/Median Selection|Median Selection]]
#* [[随机算法 (Fall 2011)/Random Graphs|Random Graphs]]
#* [[随机算法 (Fall 2011)/Chernoff Bound|Chernoff Bound]]
#* [[随机算法 (Fall 2011)/Set Balancing|Set Balancing]]
# Concentration of Measure
#* [[随机算法 (Fall 2011)/Routing in a Parallel Network|Routing in a Parallel Network]]
#* [[随机算法 (Fall 2011)/Martingales|Martingales]]
#* [[随机算法 (Fall 2011)/The Method of Bounded Differences|The Method of Bounded Differences]]
# Dimension Reduction
#* [[随机算法 (Fall 2011)/Johnson-Lindenstrauss Lemma|Johnson-Lindenstrauss Lemma]]
#* [[随机算法 (Fall 2011)/Locality Sensitive Hashing|Locality Sensitive Hashing]]
# The Probabilistic Method
#* [[随机算法 (Fall 2011)/The Probabilistic Method|The Probabilistic Method]]
#* [[随机算法 (Fall 2011)/Lovász Local Lemma|Lovász Local Lemma]]
#* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]]
# Approximation Algorithms
#* [[随机算法 (Fall 2011)/Randomized Rounding|Randomized Rounding]]
# Markov Chain and Random Walk
# Random Walk Algorithms
# Coupling and Mixing Time
# Expander Graphs
# Sampling and Counting
# MCMC
# On-line Algorithms
# Complexity
# Horizon


# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]
# [[随机算法 (Fall 2011)/Chernoff bounds| Chernoff bounds]]
# [[随机算法 (Fall 2011)/Martingales | Martingales]]
# [[随机算法 (Fall 2011)/Hashing, limited independence | Hashing, limited independence]]
# [[随机算法 (Fall 2011)/Fingerprinting|Fingerprinting]]
# [[随机算法 (Fall 2011)/The probabilistic method | The probabilistic method]]
# [[随机算法 (Fall 2011)/Markov chains and random walks | Markov chains and random walks]]
# [[随机算法 (Fall 2011)/Expander graphs | Expander graphs]]
# [[随机算法 (Fall 2011)/Rapid mixing random walks | Rapid mixing random walks]]
# [[随机算法 (Fall 2011)/Rapid mixing random walks | Rapid mixing random walks]]
# [[随机算法 (Fall 2011)/Random sampling | Random sampling, MCMC]]
# [[随机算法 (Fall 2011)/Approximate counting|Approximate counting]]
# [[随机算法 (Fall 2011)/Randomized approximation algorithms|Randomized approximation algorithms]]
# [[随机算法 (Fall 2011)/Distributed algorithms, data streams|Distributed algorithms, data streams]]

Revision as of 16:07, 18 July 2011

Lecture Notes

  1. Introduction
  2. Probability basics
  3. Balls and bins
  4. Hashing and Fingerprinting
  5. Moment and Deviation
  6. Concentration of Measure
  7. Dimension Reduction
  8. The Probabilistic Method
  9. Approximation Algorithms
  10. Markov Chain and Random Walk
  11. Random Walk Algorithms
  12. Coupling and Mixing Time
  13. Expander Graphs
  14. Sampling and Counting
  15. MCMC
  16. On-line Algorithms
  17. Complexity
  18. Horizon


  1. Rapid mixing random walks
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4437"