随机算法 (Fall 2011)/Course materials

From TCS Wiki
Revision as of 06:26, 21 July 2011 by imported>WikiSysop (→‎Course textbook)
Jump to navigation Jump to search

Course textbook

Rajeev Motwani and Prabhakar Raghavan.
Randomized Algorithms.
Cambridge University Press, 1995.
《随机算法》,随机算法的经典教材,主要部分出自作者之一Raghavan在耶鲁大学授课的讲义。选择的topic非常全面且有代表性,集中了随机算法领域最重要的思想,这一点至今无出其右者。
Michael Mitzenmacher and Eli Upfal.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Cambridge University Press, 2005.
《概率与计算:随机算法与概率分析》,成书于随机算法的成熟期。相较Motwani-Raghavan的topic driven的风格,该书的体系性更强。除了作为随机算法教材之外,也是一本面向计算机科学专业的概率论教材。

References and further readings

  • Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms, 2nd edition. MIT Press, 2001.
  • 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.
  • Olle Häggström, Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002.
  • Alistair Sinclair, Markov Chain Monte Carlo: Foundations and Applications.
Lecture Notes: http://www.cs.berkeley.edu/~sinclair/cs294/f09.html
  • Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander Graphs and Their Applications. American Mathematical Society, 2006.
  • Salil Vadhan, Pseudorandomness. draft.
http://people.seas.harvard.edu/~salil/pseudorandomness/