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/