Lecture 31 of 41Approximate Counting
Perfect Matching-I
Prof. Benny George K · IIT Guwahati
Credits and licence
- From
- Randomized Algorithms, IIT Guwahati (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- 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
- Chernoff Bound
- Permutation Routing on a Hypercube
- Permutation Routing on a Hypercube(Analysis)
- Introduction to Probabilistic Method
- More Examples on Probabilistic Method
- Lovasz Local Lemma
- Introduction to Markov Chains
- 2-SAT and Markov Chains
- 3-SAT and Markov Chains
- Electrical Networks
- Cover Time
- Rapid Mixing
- Introduction to Computational Complexity
- Pratt's Certificate
- Primality Testing
- Miller Rabin Algorithm
- All pair shortest path-I
- All pair shortest path-II
- Randomized MST
- Introduction to approximate counting
- DNF counting
- Perfect Matching-I
- Perfect Matching-II
- Perfect Matching-III
- Treaps
- Hashing
- Probabilistically checkable proofs - I
- Probabilistically checkable proofs - II
- Probabilistically checkable proofs - III
- LFKN Protocol
- summary
- Live Session 12-03-2020