CS60029 Randomized Algorithm Design

Instructor:

Swagato Sanyal

Teaching Assistant:

Arnab Maiti

Course overview:

This course studies algorithms that use randomness to make decisions. Randomized algorithms are often preferred to their deterministic counterpart because of their simplicity and speed. Randomized quicksort is an example that many students may have seen in a first course on algorithms, in which the difficulty caused to the deterministic quicksort by an unhelpful input (for example, one which is sorted or reverse-sorted) is overcome by making decisions based on the outcomes of random coin tosses. This course will involve mathematically deriving bounds on runtime and proving correctness of probabilistic algorithms. A tentative list of topics to be covered is as follows. Do note, however, that the actual coverage may omit some of these topics and include topics not listed here. The course will be of a theoretical flavour and the emphasis will be on using rigorous mathematics to reason about computation.

Pre–requisites:

The primary pre-requisite is mathematical maturity and a taste for rigorous mathematical arguments. It will also be assumed that the registrants are well-versed with basic notions of discrete probability (random experiment, sample space, events, conditional probability, independence, expectation and its basic properties, etc.). In addition, the UG registrants need to have completed the Algorithms-1 course offered by the CSE department.

Classes:

Venue: Microsoft Teams
Schedule: Monday 10-10 55 am, Wednesday 8-9.55 am.

Evaluation:

2-3 long/short tests (approximately evenly spaced in the semester), 3-4 assignments, presentations, attendance+other class activities (teacher's assessment).

References:
  1. Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan.

  2. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Eli Upfal and Michael Mitzenmacher.

Supplementary materials:

Lecture notes by Prof. Palash Dey: click here.

Lectures:

Lectures Date Class notes Reference Reading
1. Course introduction and logistics, matrix product verification (Frievald's algorithm) and fingerprinting 11/08/21 click here --
2. Fingerprinting (continued) and Polynomial Identity Testing. 16/08/21 --
3. Polynomial Identity Testing (continued), Minimum cut in graphs. 23/08/21 click here --
4. Karger's mincut algorithm, probability basics. 25/08/21 click here --
5. Probability basics continued. 30/08/21 --
6. Probability basics concluded, Randomized Quicksort. 1/9/21 click here --
7. Randomized Quicksort concluded, Markov's inequality, Chebychev's inequality. 6/9/21 --
8. The coupon-collector problem. 8/9/21 click here --
9. The Birthday problem, balls and bins. 13/9/21 click here --
10. Balls and bins continued. 15/9/21 --
11. Chernoff bound: the statement and application to error reduction. 20/9/21 click here --
12. Chernoff bound: proof and application to balanced set partition. 22/9/21 --
13. Markov chain 27/9/21 click here --
14. Randomized algorithm for 2SAT 29/9/21 Counter-example to the Markov property
15-17. Markov chain: stationary distribution, clasification of states. (4,6,11)/10/21 click here --
18. Sampling graph matchings. 18/10/21 Sampling matching (see page 11)
19. s-t reachability. 20/10/21 --
20. Statistical learning: learning intervals. 25/10/21 click here --
21. Statistical learning: learning conjunctions, VC dimension. 27/10/21 click here --
22. VC dimension (contd)., No Free-Lunch Theorem (statement) 01/11/21 video
23. Proof of No Free-Lunch theorem, Sauer's lemma 03/11/21 click here video1
video2
24. Finite VC-dimension implies learnability 08/11/21 --