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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
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]]
# [[随机算法 (Fall 2011)/Balls and bins|Balls and bins]]
# Balls and bins
#* [[随机算法 (Fall 2011)/Distribution |Balls and bins]]
#* [[随机算法 (Fall 2011)/Distributions of Coin Flipping|Distributions of Coin Flipping]]
#* [[随机算法 (Fall 2011)/Birthday Problem|Birthday Problem]]
#* [[随机算法 (Fall 2011)/Coupon Collector|Coupon Collector]]
#* [[随机算法 (Fall 2011)/Balls-into-balls Occupancy Problem|Balls-into-balls Occupancy Problem]]
#* [[随机算法 (Fall 2011)/Bloom Filter|Bloom Filter]]
#* [[随机算法 (Fall 2011)/Stable Marriage|Stable Marriage]]
# Hashing and Fingerprinting


# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]
# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]

Revision as of 14:57, 18 July 2011

Lecture Notes

  1. Introduction
  2. Probability basics
  3. Balls and bins
  4. Hashing and Fingerprinting
  1. Tail inequalities
  2. Chernoff bounds
  3. Martingales
  4. Hashing, limited independence
  5. Fingerprinting
  6. The probabilistic method
  7. Markov chains and random walks
  8. Expander graphs
  9. Rapid mixing random walks
  10. Random sampling, MCMC
  11. Approximate counting
  12. Randomized approximation algorithms
  13. Distributed algorithms, data streams
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4436"