Contents: We will review the basic tools in probability and then study their applications in algorithms and combinatorics. We will mainly follow the book of Mitzenmacher and Upfal, and cover all the topics there: Hashing, Markov Chains and Random Walks, Counting, Balanced Allocations, the Probabilistic Method, etc.

Expected work: Weekly meeting and homework assignments. The grade will be based on homework assignments.

Texts

Probability and Computing. M Mitzenmacher and E Upfal. Cambridge.

Randomized Algorithms. Rajeev Motwani and Prabhakar Raghavan. Cambridge.

The Probabilistic Method. Noga Alon and Joel Spencer. Wiley.

Duration

Jan 16 to April end.