随机算法 (Spring 2014)/Course materials

From TCS Wiki
Jump to navigation Jump to search

Course textbook

Rajeev Motwani and Prabhakar Raghavan.
Randomized Algorithms.
Cambridge University Press, 1995.
Michael Mitzenmacher and Eli Upfal.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Cambridge University Press, 2005.

References and further readings

  • Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms, 2nd edition. MIT Press, 2001.
《算法导论》,CLRS。在本课程中作为算法的工具书。
  • William Feller, An Introduction to Probability Theory and Its Applications, volumes 1, 3rd edition. Wiley, 1968.
《概率论及其应用》上卷。本课程的概率论工具书。
  • Noga Alon and Joel Spencer. The Probabilistic Method, 3nd edition. Wiley, 2008.
组合数学的概率法。
  • David Aldous and Jim Fill, Reversible Markov Chains and Random Walks on Graphs, 2002.
http://www.stat.berkeley.edu/~aldous/RWG/book.html
一本从未写完的书,但是对random walk的研究产生了深远的影响,人称"the Aldous-Fill book"。