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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
Line 55: Line 55:
#* [[随机算法 (Fall 2011)/Perfect Matching in Regular Bipartite Graph|Perfect Matching in Regular Bipartite Graph]]
#* [[随机算法 (Fall 2011)/Perfect Matching in Regular Bipartite Graph|Perfect Matching in Regular Bipartite Graph]]
#* [[随机算法 (Fall 2011)/The Metropolis Algorithm|The Metropolis Algorithm]]
#* [[随机算法 (Fall 2011)/The Metropolis Algorithm|The Metropolis Algorithm]]
#* [[随机算法 (Fall 2011)/Spin Systems|Spin Systems]]
#* [[随机算法 (Fall 2011)/Dynamics on Spins|Dynamics on Spins]]
# Coupling and Mixing Time
# Coupling and Mixing Time
#* [[随机算法 (Fall 2011)/Mixing Time|Mixing Time]]
#* [[随机算法 (Fall 2011)/Mixing Time|Mixing Time]]
Line 72: Line 72:
#* [[随机算法 (Fall 2011)/USTCON in LOGSPACE|USTCON in LOGSPACE]]
#* [[随机算法 (Fall 2011)/USTCON in LOGSPACE|USTCON in LOGSPACE]]
# Sampling and Counting
# Sampling and Counting
#* [[随机算法 (Fall 2011)/The #P Class and Approximation|The #P Class and Approximation]]
#* [[随机算法 (Fall 2011)/DNF Counting|DNF Counting]]
#* [[随机算法 (Fall 2011)/Sampling and Counting|Sampling and Counting]]
#* [[随机算法 (Fall 2011)/Canonical Paths|Canonical Paths]]
#* [[随机算法 (Fall 2011)/Count Matchings|Count Matchings]]
# MCMC
# MCMC
# On-line Algorithms
#* [[随机算法 (Fall 2011)/Spin Systems|Spin Systems]]
#* [[随机算法 (Fall 2011)/Simulated Annealing|Simulated Annealing]]
#* [[随机算法 (Fall 2011)/Volume Estimation|Volume Estimation]]
# Complexity
# Complexity


# [[随机算法 (Fall 2011)/Rapid mixing random walks | Rapid mixing random walks]]
# [[随机算法 (Fall 2011)/Rapid mixing random walks | Rapid mixing random walks]]

Revision as of 15:44, 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 I
  15. Expander Graphs II
  16. Sampling and Counting
  17. MCMC
  18. Complexity
  1. Rapid mixing random walks
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4454"