IIT Guwahati · Computer Science

Randomized Algorithms

Prof. Benny George K · 41 free video lectures

41 video lectures. Topics: Introduction to Randomized Algorithms; Randomized Mincut Algorithm; Randomized Find; Probability Review; Expectation of Random Variables; Conditional Probability and Conditional Expectation2; Birthday Paradox; Markov and Chebychev's Inequalities; Median Algorithm…

▶ Play on Open Lecture HallCourse page ↗

Lectures

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

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Guwahati.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights