NOC:Randomized Algorithms


Lecture 1 - Introduction to Randomized Algorithms


Lecture 2 - Randomized Mincut Algorithm


Lecture 3 - Randomized Find


Lecture 4 - Probability Review


Lecture 5 - Expectation of Random Variables


Lecture 6 - Conditional Probability and Conditional Expectation2


Lecture 7 - Birthday Paradox


Lecture 8 - Markov and Chebychev's Inequalities


Lecture 9 - Median Algorithm


Lecture 10 - Chernoff Bound


Lecture 11 - Permutation Routing on a Hypercube


Lecture 12 - Permutation Routing on a Hypercube (Analysis)


Lecture 13 - Introduction to Probabilistic Method


Lecture 14 - More Examples on Probabilistic Method


Lecture 15 - Lovasz Local Lemma


Lecture 16 - Introduction to Markov Chains


Lecture 17 - 2-SAT and Markov Chains


Lecture 18 - 3-SAT and Markov Chains


Lecture 19 - Electrical Networks


Lecture 20 - Cover Time


Lecture 21 - Rapid Mixing


Lecture 22 - Introduction to Computational Complexity


Lecture 23 - Pratt's Certificate


Lecture 24 - Primality Testing


Lecture 25 - Miller Rabin Algorithm


Lecture 26 - All pair shortest path - I


Lecture 27 - All pair shortest path - II


Lecture 28 - Randomized MST


Lecture 29 - Introduction to approximate counting


Lecture 30 - DNF counting


Lecture 31 - Perfect Matching - I


Lecture 32 - Perfect Matching - II


Lecture 33 - Perfect Matching - III


Lecture 34 - Treaps


Lecture 35 - Hashing


Lecture 36 - Probabilistically checkable proofs - I


Lecture 37 - Probabilistically checkable proofs - II


Lecture 38 - Probabilistically checkable proofs - III


Lecture 39 - LFKN Protocol


Lecture 40 - summary