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