Randomized Algorithms

Wishlist Share
Share Course
Page Link
Share On Social Media

About Course

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.

Show More

What Will You 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

Course Content

Randomized Algorithms

  • Randomized Algorithms [Intro Video]
    00:00
  • Lecture 1: Introduction to Randomized Algorithms
    00:00
  • Lecture 2: Randomized Mincut Algorithm
    00:00
  • Lecture 3: Randomized Find
    00:00
  • Lecture 4: Probability Review
    00:00
  • Lecture 5: Expectation of Random Variables
    00:00
  • Lec 6: Conditional Probability and Conditional Expectation2
    00:00
  • Lec 7: Birthday Paradox
    00:00
  • Lecture 8: Markov and Chebychev’s Inequalities
    00:00
  • Lecture 9: Median Algorithm
    00:00
  • Lecture 10: Chernoff Bound
    00:00
  • Lec 11: Permutation Routing on a Hypercube
    00:00
  • Lec 12: Permutation Routing on a Hypercube(Analysis)
    00:00
  • Lec 13: Introduction to Probabilistic Method
    00:00
  • Lec 14: More Examples on Probabilistic Method
    00:00
  • Lec 15: Lovasz Local Lemma
    00:00
  • Lec 16: Introduction to Markov Chains
    00:00
  • Lec 17: 2-SAT and Markov Chains
    00:00
  • Lec 18: 3-SAT and Markov Chains
    00:00
  • Lec 19: Electrical Networks
    00:00
  • Lec 20: Cover Time
    00:00
  • Lec 21: Rapid Mixing
    00:00
  • Lec 22: Introduction to Computational Complexity
    00:00
  • Lec 23: Pratt’s Certificate
    00:00
  • Lec 24: Primality Testing
    00:00
  • Lec 25: Miller Rabin Algorithm
    00:00
  • Lec 26: All pair shortest path-I
    00:00
  • Lec 27: All pair shortest path-II
    00:00
  • Lec 28: Randomized MST
    00:00
  • Lec 29: Introduction to approximate counting
    00:00
  • Lec 30: DNF counting
    00:00
  • Lec 31: Perfect Matching-I
    00:00
  • Lec 32: Perfect Matching-II
    00:00
  • Lec 33: Perfect Matching-III
    00:00
  • Lec 34: Treaps
    00:00
  • Lec 35: Hashing
    00:00
  • Lec 36: Probabilistically checkable proofs – I
    00:00
  • Lec 37: Probabilistically checkable proofs – II
    00:00
  • Lec 38: Probabilistically checkable proofs – III
    00:00
  • Lec 39: LFKN Protocol
    00:00
  • Lec 40: Summary
    00:00

Student Ratings & Reviews

No Review Yet
No Review Yet
ResearcherStore

Want to receive push notifications for all major on-site activities?