Randomized Algorithms

  • Course level: Intermediate


Randomized Algorithms.

Algorithms are required to be “correct” and “fast”. In a wide variety of applications, these twin objectives are in conflict with each other. Fortunately, neither of these ideals is sacrosanct. Therefore we can often try to optimize one of these goals by incurring a small penalty on the other. This takes us to the field of Randomized Algorithms. Often, the randomized variants, in addition to being faster than their deterministic counterpart, are simpler to understand and implement. In this course, we will study the tradeoff between correctness and speed. We will be learning a number of methods to design and analyze randomized algorithms.

INTENDED AUDIENCE: Senior UG students, PG students, and Ph.D. candidates interested in computer science, combinatorics, etc.

What Will I Learn?

  • Week 1 : Introduction to Randomized Algorithms
  • Week 2 : Probability Review
  • Week 3 : Moments and Deviation
  • Week 4 : The Probabilistic Method
  • Week 5 : Markov Chains - I
  • Week 6 : Markov Chain - II
  • Week 7 : Number Theoretic Algorithms
  • Week 8 : Graph Algorithms
  • Week 9 : Approximate Counting
  • Week 10: Data Structures
  • Week 11: Computational Complexity
  • Week 12: Review of the course

Topics for this course

41 Lessons

Randomized Algorithms

Randomized Algorithms [Intro Video]00:00:00
Lecture 1: Introduction to Randomized Algorithms00:00:00
Lecture 2: Randomized Mincut Algorithm00:00:00
Lecture 3: Randomized Find00:00:00
Lecture 4: Probability Review00:00:00
Lecture 5: Expectation of Random Variables00:00:00
Lec 6: Conditional Probability and Conditional Expectation200:00:00
Lec 7: Birthday Paradox00:00:00
Lecture 8: Markov and Chebychev’s Inequalities00:00:00
Lecture 9: Median Algorithm00:00:00
Lecture 10: Chernoff Bound00:00:00
Lec 11: Permutation Routing on a Hypercube00:00:00
Lec 12: Permutation Routing on a Hypercube(Analysis)00:00:00
Lec 13: Introduction to Probabilistic Method00:00:00
Lec 14: More Examples on Probabilistic Method00:00:00
Lec 15: Lovasz Local Lemma00:00:00
Lec 16: Introduction to Markov Chains00:00:00
Lec 17: 2-SAT and Markov Chains00:00:00
Lec 18: 3-SAT and Markov Chains00:00:00
Lec 19: Electrical Networks00:00:00
Lec 20: Cover Time00:00:00
Lec 21: Rapid Mixing00:00:00
Lec 22: Introduction to Computational Complexity00:00:00
Lec 23: Pratt’s Certificate00:00:00
Lec 24: Primality Testing00:00:00
Lec 25: Miller Rabin Algorithm00:00:00
Lec 26: All pair shortest path-I00:00:00
Lec 27: All pair shortest path-II00:00:00
Lec 28: Randomized MST00:00:00
Lec 29: Introduction to approximate counting00:00:00
Lec 30: DNF counting00:00:00
Lec 31: Perfect Matching-I00:00:00
Lec 32: Perfect Matching-II00:00:00
Lec 33: Perfect Matching-III00:00:00
Lec 34: Treaps00:00:00
Lec 35: Hashing00:00:00
Lec 36: Probabilistically checkable proofs – I00:00:00
Lec 37: Probabilistically checkable proofs – II00:00:00
Lec 38: Probabilistically checkable proofs – III00:00:00
Lec 39: LFKN Protocol00:00:00
Lec 40: Summary00:00:00
Randomized Algorithms

Enrolment validity: Lifetime


  • Basic Understanding of Algorithms and Probability