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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
Line 1: Line 1:
= Lecture Notes =
= Lecture Notes =
# [[随机算法 (Fall 2011)/Introduction|Introduction]]
# [[随机算法 (Fall 2011)/Introduction|Introduction]]
# [[随机算法 (Fall 2011)/Complexity classes and lower bounds|Complexity classes, lower bounds]]
#*[[随机算法 (Fall 2011)/Complexity Classes|Complexity Classes]]
# Probability basics
#* [[随机算法 (Fall 2011)/Probability Space|Probability Space]]
#* [[随机算法 (Fall 2011)/Verifying Matrix Multiplication|Verifying Matrix Multiplication]]
#* [[随机算法 (Fall 2011)/Conditional Probability|Conditional Probability]]
#* [[随机算法 (Fall 2011)/Randomized Min-Cut|Randomized Min-Cut]]
#* [[随机算法 (Fall 2011)/Random Variables and Expectations|Random Variables and Expectations]]
#* [[随机算法 (Fall 2011)/Randomized Quicksort|Randomized Quicksort]]
# [[随机算法 (Fall 2011)/Balls and bins|Balls and bins]]
# [[随机算法 (Fall 2011)/Balls and bins|Balls and bins]]
#* [[随机算法 (Fall 2011)/Distribution |Balls and bins]]
# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]
# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]
# [[随机算法 (Fall 2011)/Chernoff bounds| Chernoff bounds]]
# [[随机算法 (Fall 2011)/Chernoff bounds| Chernoff bounds]]

Revision as of 13:32, 18 July 2011

Lecture Notes

  1. Introduction
  2. Probability basics
  3. Balls and bins
  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=4435"