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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
Line 47: Line 47:
#* [[随机算法 (Fall 2011)/Markov Chains|Markov Chains]]
#* [[随机算法 (Fall 2011)/Markov Chains|Markov Chains]]
#* [[随机算法 (Fall 2011)/Random Walks on Undirected Graphs|Random Walks on Undirected Graphs]]
#* [[随机算法 (Fall 2011)/Random Walks on Undirected Graphs|Random Walks on Undirected Graphs]]
#* [[随机算法 (Fall 2011)/Electrical Network|Electrical Network]]
#* [[随机算法 (Fall 2011)/Cover Time|Cover Time]]
#* [[随机算法 (Fall 2011)/Graph Connectivity|Graph Connectivity]]
# Random Walk Algorithms
# Random Walk Algorithms
#* [[随机算法 (Fall 2011)/Randomized 2SAT|Randomized 2SAT]]
#* [[随机算法 (Fall 2011)/Randomized 3SAT|Randomized 3SAT]]
#* [[随机算法 (Fall 2011)/Perfect Matching in Regular Bipartite Graph|Perfect Matching in Regular Bipartite Graph]]
#* [[随机算法 (Fall 2011)/The Metropolis Algorithm|The Metropolis Algorithm]]
#* [[随机算法 (Fall 2011)/Spin Systems|Spin Systems]]
# Coupling and Mixing Time
# Coupling and Mixing Time
#* [[随机算法 (Fall 2011)/Mixing Time|Mixing Time]]
#* [[随机算法 (Fall 2011)/Mixing Time|Mixing Time]]

Revision as of 15:02, 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
  1. Rapid mixing random walks
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4452"