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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
(Created page with '= Lecture Notes = # Introduction # Complexity classes, lower bounds # […')
 
imported>WikiSysop
Line 4: Line 4:
# [[随机算法 (Fall 2011)/Balls and bins|Balls and bins]]
# [[随机算法 (Fall 2011)/Balls and bins|Balls and bins]]
# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]
# [[随机算法 (Fall 2011)/Tail inequalities|Tail inequalities]]
# [[随机算法 (Fall 2011)/More on Chernoff bounds| Set balancing, packet routing, and metric embedding]]
# [[随机算法 (Fall 2011)/Chernoff bounds| Chernoff bounds]]
# [[随机算法 (Fall 2011)/Martingales | Martingales]]
# [[随机算法 (Fall 2011)/Hashing, limited independence | Hashing, limited independence]]
# [[随机算法 (Fall 2011)/Hashing, limited independence | Hashing, limited independence]]
# [[随机算法 (Fall 2011)/Martingales | Martingales]]
# [[随机算法 (Fall 2011)/Fingerprinting|Fingerprinting]]
# [[随机算法 (Fall 2011)/The probabilistic method | The probabilistic method]]
# [[随机算法 (Fall 2011)/The probabilistic method | The probabilistic method]]
# [[随机算法 (Fall 2011)/Markov chains and random walks | Markov chains and random walks]]
# [[随机算法 (Fall 2011)/Markov chains and random walks | Markov chains and random walks]]
# [[随机算法 (Fall 2011)/Expander graphs and rapid mixing random walks | Expander graphs, rapid mixing random walks]]
# [[随机算法 (Fall 2011)/Expander graphs | Expander graphs]]
# [[随机算法 (Fall 2011)/Rapid mixing random walks | Rapid mixing random walks]]
# [[随机算法 (Fall 2011)/Random sampling | Random sampling, MCMC]]
# [[随机算法 (Fall 2011)/Random sampling | Random sampling, MCMC]]
# [[随机算法 (Fall 2011)/Approximate counting, linear programming|Approximate counting, linear programming]]
# [[随机算法 (Fall 2011)/Approximate counting|Approximate counting]]
# [[随机算法 (Fall 2011)/Randomized approximation algorithms|Randomized approximation algorithms]]
# [[随机算法 (Fall 2011)/Randomized approximation algorithms|Randomized approximation algorithms]]
# [[随机算法 (Fall 2011)/Fingerprinting|Fingerprinting]]
# [[随机算法 (Fall 2011)/Distributed algorithms, data streams|Distributed algorithms, data streams]]
# [[随机算法 (Fall 2011)/Distributed algorithms, data streams|Distributed algorithms, data streams]]


Revision as of 01:03, 22 March 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

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
  • Learning and boosting
  • Compressed sensing
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4431"