| Part 1 (Seg 12) |
|---|
| Jan 3: Lecture 1
(Karger's algorithm)
Illustration of repeated edge contraction here |
| 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 |
| References for Part 1 |
| Probability and Computing by Mitzenmacher and Upfal |
| Randomized Algorithms by Motwani and Raghavan |
| Randomized Algorithms by Prof. Surendar Baswana, IIT Kanpur |
| Algorithmic Superpower Randomization by Prof. Bernhard Haeupler |
| Part 2 (Seg 34) |
|---|
| Feb 11 (Lec 11): Counting elements in a stream
Note on order statistics |
|
Feb 21 (Lec 13): Mean Estimation from Samples;
Analysis of Morris'algorithm |
|
Feb 25 (Lec 14): AMS algorithm and analysis
BJKST algorithm for counting distinct elements |
| Feb 28 (Lec 15): Misra-Gries algorithm for heavy hitters |
| Mar 3 (Lec 16): Count-Min algorithm |
| Mar 3, 6 (Lec 16-17): Method of conditional expectation: 3-SAT |
| Mar 6,Mar 17 (cancelled) (Lec 17-18): Conditional expectation: Cuts and games |
| References for Part 2 |
| Algorithms for Big Data by Chandra Chekuri |
| Sublinear and streaming algorithms by Paul Beame |
| Part 3 (Seg 56) |
|---|
| Markov Chains: Note 1 & Video 1 |
|
Algorithms for 2-SAT & 3-SAT:
Note 2
Video 2: part A & Video 2: part B |
|
USTCON: randomized logspace
Note 3
Video 3: part A & Video 3: part B |
|
Counting DNF solutions
Note 4
Video 4 |
|
Counting independent sets and Metropolis algorithm
Note 5
Video 5: part A Video 5: part B Video 5: part C |
| References for Part 3 |
| Notes on probability and computing by Ryan O'Donnell (Lec 14-16 for Markov Chains) |
| NPTEL videos by Prof. Benny George (Lec 16 onwards for Markov chains) |