Randomized Algorithms

Course description: The primary goal of the course is to learn various techniques used to design randomized algorithms and to analyse them. Randomization is used in almost all areas of computer science. We will study how randomization is used to design efficient algorithms for diverse classes of problems.


Prerequisites: We will assume some familiarity with probability, algorithms.


Timing (Tentative): Tuesdays and Fridays from 3 PM to 4:30 PM.


Grading: The course will be theoretical in nature. You will be assigned homeworks, one in every two weeks or so. Grading components: HW (20%), Mid-sem (20%), End-sem (40%), Project (20%).


Textbooks:

  • For a significant portion of the course, we will follow the following two books. Probability and Computing by Mitzenmacher, Michael, and Eli Upfal (MU) and Randomized algorithms by Motwani and Raghavan (MR).

  • You will be provided the references on other topics covered in class.


  1. Lecture 1 (10/08/2021): Introduction, Randomized Quicksort (Section 2.5 of MU, Notes: Part 1, Part 2, Recording)

  2. Lecture 2 (13/08/2021): Randomized min-cut (Section 1.1 of MR, Notes, Recording)

  3. Lecture 3 (17/08/2021): Balls into bins, union bound (Section 3.1 of MR, Notes, Recording)

  4. Lecture 4 (20/08/2021): Markov, Chebyshev inequalities, Chernoff bound (Section 3.2, 4.1 of MR, Notes, Recording)

  5. Lecture 5 (24/08/2021): Proof Chernoff bounds, applications (Section 4.1 of MR, Chapter 4 of MU, Notes, Recording)

  6. Lecture 6 (27/08/2021): Estimation using Sampling (Section 4.2.3 of MU, Notes, Recording)

  7. Lecture 7 (31/08/2021): Hashing, Universal hash family (Section 5.5.1, Chapter 15 of MU, Notes, Recording)

  8. Lecture 8 (03/09/2021): Conclude hashing (Chapter 15 of MU, Notes, Recording)

  9. Lecture 9 (07/09/2021): Probabilistic Method (Chapter 6 of MU, Notes, Recording)

  10. Lecture 10 (10/09/2021): Second moment method, LLL (Chapter 6 of MU, Notes, Recording)

  11. Lecture 11 (14/09/2021): Metric embeddings, JL Lemma (Matousek's survey, CMU Notes, Class notes, Recording)

  12. Lecture 12 (17/09/2021): JL Lemma, Nearest Neighbour (Section 2.1,2.2,2.3,2.9 of Matousek's Survey, Class notes, Recording)

  13. Lecture 13 (21/09/2021): Locality Sensitive Hashing (Section 2.9 of Matousek's survey, Class notes, Recording)

  14. Lecture 14 (24/09/2021): Randomized lower bounds for sorting, Yao's lemma (Section 2.2.2 of MR, Class notes, Recording)

  15. Lecture 15 (12/10/2021): Markov chains, Algorithm for 2-SAT (Section 7.1 of MU, Class notes, Recording)

  16. Lecture 16 (19/10/2021): Stationary distribution of Markov chains, Random walks on graphs (Section 7.2, 7.3, 7.4 of MU, Class notes, Recording)

  17. Lecture 17 (21/10/2021): Expanders (Section 5.3, 6.7 of MR, Class notes, Recording)

  18. Lecture 18 (26/10/2021): Monte Carlo Method (Section 11.1, 11.2 in MU, Class notes, Recording)

  19. Lecture 19 (28/10/2021): Martingales (Chapter 14 in MU, Class notes, Recording)

  20. Lecture 20 (02/11/2021): Streaming Algorithms (Chapter 0 and 1 of these notes, Recording)

  21. Lecture 21 (09/11/2021): Streaming: Approximate counting (Chapter 2 and 4 of these notes, Recording)

  22. Lecture 22 (11/11/2021): Streaming: Counting Distinct Elements, Reservoir Sampling (Chapter 2 of these notes, Recording)

  23. Lecture 23 (16/11/2021): Median of Means, Idea of streaming lower bounds (Section 2.4, 4.4, 18.3 of these notes, Class notes, Recording)