I: Probability tools, with algorithmic applications; II: Data streams; III: Markov chains and random walks, with applications.

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) |

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