### Course Information

The course will focus on tools from probability and their applications to algorithms.

**Topics to be covered: **
I: Review of basic probability, random variables, expectation, concentration inequalities,
with algorithmic applications.

II: More applications: data streams, geometric algorithms, randomized rounding.

III: Markov chains, random walks, applications to sampling and approximate counting.

IV: Pairwise independence & derandomization.

** References: **
1. Probability and Computing by Mitzenmacher and Upfal

2. Randomized Algorithms by Motwani and Raghavan

3. Courses elsewhere with similar or related content:

(i)

Randomized Algorithms by Prof. Surendar Baswana, IIT Kanpur

(ii)

Algorithmic Superpower Randomization by Prof. Bernhard Haeupler