NPTEL : NOC:Randomized Algorithms (Computer Science and Engineering)

Co-ordinators : Prof. Benny George K


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