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

From TCS Wiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
imported>WikiSysop
Line 16: Line 16:
# [[随机算法 (Fall 2011)/Randomized approximation algorithms|Randomized approximation algorithms]]
# [[随机算法 (Fall 2011)/Randomized approximation algorithms|Randomized approximation algorithms]]
# [[随机算法 (Fall 2011)/Distributed algorithms, data streams|Distributed algorithms, data streams]]
# [[随机算法 (Fall 2011)/Distributed algorithms, data streams|Distributed algorithms, data streams]]
=== Future plan ===
Topics that I'm considering to cover at next time when I teach this class (perhaps):
* Janson's inequality,
* Talagrand's inequality
* The Poisson Approximation
* Fourier analysis
* Random graphs
* Entropy and randomness
* Derandomization
* Color-coding
* On-line algorithms
* Property testing
* Compressed sensing
* Locality sensitive hashing

Revision as of 13:02, 18 July 2011

Lecture Notes

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