I: Probability tools, with algorithmic applications.

II: Data streams

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

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

(iii) Algorithms for Big Data by Chandra Chekuri

(iv) Sublinear and streaming algorithms by Paul Beame

Jan 21: Lecture 6 (Randomized Median-find)

Jan 28 (Lec 8): Chernoff Bounds

Jan 31 (Lec 9): Set Balancing and Network Routing

Feb 4 (Lec 10): Network Routing

Feb 11 (Lec 11): Counting elements in a stream ; Note on order statistics

Feb 21 (Lec 13): Coming soon...analysis of Morris'algorithm and median-of-means

Feb 25 (Lec 14): Coming soon...AMS and BJKST algorithms for counting distinct elements

Minimum is 14 classes and carries 5 marks. Every additional 2 classes carries 1 mark, till a max of 10.