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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
Line 41: Line 41:
#* [[随机算法 (Fall 2011)/Lovász Local Lemma|Lovász Local Lemma]]
#* [[随机算法 (Fall 2011)/Lovász Local Lemma|Lovász Local Lemma]]
#* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]]  
#* [[随机算法 (Fall 2011)/Derandomization: Conditional Expectation|Derandomization: Conditional Expectation]]  
#* [[随机算法 (Fall 2011)/Derandomization: Color Coding|Derandomization: Color Coding]]  
#* [[随机算法 (Fall 2011)/Derandomization: Color-coding|Derandomization: Color-coding]]  
# Approximation Algorithms, On-line Algorithms
# Approximation Algorithms, On-line Algorithms
#* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]]
#* [[随机算法 (Fall 2011)/Max-SAT|Max-SAT]]

Revision as of 16:08, 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, On-line Algorithms
  11. Markov Chain and Random Walk
  12. Random Walk Algorithms
  13. Coupling and Mixing Time
  14. Expander Graphs I
  15. Expander Graphs II
  16. Sampling and Counting
  17. MCMC
  18. Complexity
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4461"