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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
imported>WikiSysop
Line 2: Line 2:
# [[随机算法 (Fall 2011)/Introduction|Introduction]]
# [[随机算法 (Fall 2011)/Introduction|Introduction]]
#*[[随机算法 (Fall 2011)/Complexity Classes|Complexity Classes]]
#*[[随机算法 (Fall 2011)/Complexity Classes|Complexity Classes]]
# Probability basics
# Probability Basics
#* [[随机算法 (Fall 2011)/Probability Space|Probability Space]]
#* [[随机算法 (Fall 2011)/Probability Space|Probability Space]]
#* [[随机算法 (Fall 2011)/Verifying Matrix Multiplication|Verifying Matrix Multiplication]]
#* [[随机算法 (Fall 2011)/Verifying Matrix Multiplication|Verifying Matrix Multiplication]]
Line 9: Line 9:
#* [[随机算法 (Fall 2011)/Random Variables and Expectations|Random Variables and Expectations]]
#* [[随机算法 (Fall 2011)/Random Variables and Expectations|Random Variables and Expectations]]
#* [[随机算法 (Fall 2011)/Randomized Quicksort|Randomized Quicksort]]
#* [[随机算法 (Fall 2011)/Randomized Quicksort|Randomized Quicksort]]
# Balls and bins
# Balls and Bins
#* [[随机算法 (Fall 2011)/Distributions of Coin Flipping|Distributions of Coin Flipping]]
#* [[随机算法 (Fall 2011)/Distributions of Coin Flipping|Distributions of Coin Flipping]]
#* [[随机算法 (Fall 2011)/Birthday Problem|Birthday Problem]]
#* [[随机算法 (Fall 2011)/Birthday Problem|Birthday Problem]]
Line 16: Line 16:
#* [[随机算法 (Fall 2011)/Bloom Filter|Bloom Filter]]
#* [[随机算法 (Fall 2011)/Bloom Filter|Bloom Filter]]
#* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]]
#* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]]
# 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)/Markov's Inequality|Markov's Inequality]]
#* [[随机算法 (Fall 2011)/Chebyshev's Inequality|Chebyshev's Inequality]]
#* [[随机算法 (Fall 2011)/Chebyshev's Inequality|Chebyshev's Inequality]]
#* [[随机算法 (Fall 2011)/Median Selection|Median Selection]]
#* [[随机算法 (Fall 2011)/Median Selection|Median Selection]]
#* [[随机算法 (Fall 2011)/Random Graphs|Random Graphs]]
#* [[随机算法 (Fall 2011)/Random Graphs|Random Graphs]]
# Hashing and Fingerprinting
#* [[随机算法 (Fall 2011)/Pair-wise Independence|Pair-wise Independence]]
#* [[随机算法 (Fall 2011)/Derandomization: Two-Point Sampling|Derandomization: Two-Point Sampling]]
# Chernoff Bound
#* [[随机算法 (Fall 2011)/Chernoff Bound|Chernoff Bound]]
#* [[随机算法 (Fall 2011)/Chernoff Bound|Chernoff Bound]]
#* [[随机算法 (Fall 2011)/Set Balancing|Set Balancing]]
#* [[随机算法 (Fall 2011)/Set Balancing|Set Balancing]]
#* [[随机算法 (Fall 2011)/Routing in a Parallel Network|Routing in a Parallel Network]]
# Concentration of Measure
# Concentration of Measure
#* [[随机算法 (Fall 2011)/Routing in a Parallel Network|Routing in a Parallel Network]]
#* [[随机算法 (Fall 2011)/Martingales|Martingales]]
#* [[随机算法 (Fall 2011)/Martingales|Martingales]]
#* [[随机算法 (Fall 2011)/Azuma's Inequality|Azuma's Inequality]]
#* [[随机算法 (Fall 2011)/Azuma's Inequality|Azuma's Inequality]]

Revision as of 03:40, 19 July 2011

Lecture Notes

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


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