随机算法 (Fall 2011)/Course materials

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. 《算法导论》，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. 组合数学的概率法。
	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 Sinclair在Berkeley开设的MCMC课程的讲义。
	Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander Graphs and Their Applications. American Mathematical Society, 2006. Linial和Wigderson在以色列的希伯来大学和普林斯顿高等研究所开设的扩展图课程的讲义，后来成书。网上有预印本可以下载。
	Salil Vadhan, Pseudorandomness. draft. http://people.seas.harvard.edu/~salil/pseudorandomness/ Vadhan在Harvard开始的伪随机理论的讲义。