Learn · NPTEL

Course10610318741 lectures

Randomized Algorithms

Prof. Benny George K · IIT Guwahati

Start with lecture 1 At NPTEL

Lectures

Introduction to Randomized Algorthms

  1. Introduction to Randomized Algorithms Video
  2. Randomized Mincut Algorithm Video
  3. Randomized Find Video

Probability Review

  1. Probability Review Video
  2. Expectation of Random Variables Video
  3. Conditional Probability and Conditional Expectation2 Video
  4. Birthday Paradox Video

Moments and Deviations

  1. Markov and Chebychev's Inequalities Video
  2. Median Algorithm Video
  3. Chernoff Bound Video
  4. Permutation Routing on a Hypercube Video
  5. Permutation Routing on a Hypercube(Analysis) Video

Probabilistic Method

  1. Introduction to Probabilistic Method Video
  2. More Examples on Probabilistic Method Video
  3. Lovasz Local Lemma Video

Markov Chains

  1. Introduction to Markov Chains Video
  2. 2-SAT and Markov Chains Video
  3. 3-SAT and Markov Chains Video

Markov Chains-II

  1. Electrical Networks Video
  2. Cover Time Video
  3. Rapid Mixing Video

Number Theoretic Algorithms

  1. Introduction to Computational Complexity Video
  2. Pratt's Certificate Video
  3. Primality Testing Video
  4. Miller Rabin Algorithm Video

Graph Theoretic Algorithms

  1. All pair shortest path-I Video
  2. All pair shortest path-II Video
  3. Randomized MST Video

Approximate Counting

  1. Introduction to approximate counting Video
  2. DNF counting Video
  3. Perfect Matching-I Video
  4. Perfect Matching-II Video
  5. Perfect Matching-III Video

Randomization and Data Structures

  1. Treaps Video
  2. Hashing Video

Computational Complexity

  1. Probabilistically checkable proofs - I Video
  2. Probabilistically checkable proofs - II Video
  3. Probabilistically checkable proofs - III Video
  4. LFKN Protocol Video

summary

  1. summary Video

Live Session

  1. Live Session 12-03-2020 Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Guwahati
Department
Computer Science and Engineering
Teacher
Prof. Benny George K
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed