Learn · Selected Topics in Algorithms

Lecture 22 of 66Week 05

Lecture 22: Mixing Time, Reversible Markov Chain

Prof. Palash Dey · IIT Kharagpur

Credits and licence

From
Selected Topics in Algorithms, IIT Kharagpur (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

  1. Lecture 01 : Introduction to Maximum Flow Video
  2. Lecture 02 : Ford - Fulkerson Method Video
  3. Lecture 03 : Edmond - Karp Algorithm Video
  4. Lecture 04 : Edmond - Karp Algorithm (Contd.) Video
  5. Lecture 05 : Flow Decomposition Video
  6. Lecture 06 : Maximum Bipartite Matching, Fattest Augmenting Path Video
  7. Lecture 07 : Karger's Algorithm Video
  8. Lecture 08 : Augmenting Path Video
  9. Lecture 09 : Edmonds Blossom Algorithm Video
  10. Lecture 10 : Edmond - Karp Algorithm (Contd.) Video
  11. Lecture 11: Introduction to Randomized Algorithm Video
  12. Lecture 12: Polynomial Identity Testing Video
  13. Lecture 13: Perfect Bipartite Matching, Randomized Quicksort Video
  14. Lecture 14: Concentration Inequalities: Markov, Chebyshev, Chernoff Video
  15. Lecture 15: Proof of Chernoff Bound Video
  16. Lecture 16: Coupon Collector Problem Video
  17. Lecture 17: Balls and Bins Video
  18. Lecture 18: Balls and Bins Contd. Video
  19. Lecture 19: Two Point Sampling Video
  20. Lecture 20: Randomized Algorithm for 2 SAT Video
  21. Lecture 21: Markov Chain, Periodicity, Stationary Distribution Video
  22. Lecture 22: Mixing Time, Reversible Markov Chain Video
  23. Lecture 23: Metropolis Algorithm, Markov Chain on Independent Sets Video
  24. Lecture 24: Random Walk on Cycles Video
  25. Lecture 25: Shuffling Cards Video
  26. Lecture 26: Monte Carlo Method, Hitting Time, Cover Time Video
  27. Lecture 27: DNF Counting Video
  28. Lecture 28: DNF Counting (Contd.) Video
  29. Lecture 29: Counting Independent Sets of a Graph Video
  30. Lecture 30: Counting Independent Sets of a Graph (Contd.) Video
  31. Lecture 31: Introduction of NP, co-NP, and P Video
  32. Lecture 32: Turing Reduction, Karp Reduction Video
  33. Lecture 33: NP - Completeness of 3SAT Video
  34. Lecture 34: NP - Completeness of Independent Set Video
  35. Lecture 35: NP - Completeness of vertex cover and clique Video
  36. Lecture 36: NP - Completeness of 3 - coloring Video
  37. Lecture 37: NP - Completeness of Subset sum and Knapsack Video
  38. Lecture 38: NP - Completeness of set cover, Weak and Strong NP - completeness Video
  39. Lecture 39: Self Reduction Video
  40. Lecture 40: Randomized Approximation Algorithm Video
  41. Lecture 41: Derandomization Video
  42. Lecture 42: Travelling Salesman Problem Video
  43. Lecture 43: 2 - Factor Approximation Algorithm for Metric TSP Video
  44. Lecture 44: 1.5 - Factor Approximation Algorithm for Metric TSP Video
  45. Lecture 45: Approximation Algorithm for Set Cover Video
  46. Lecture 46: FPTAS for Knapsack Video
  47. Lecture 47: Introduction to Linear Program Video
  48. Lecture 48: Introduction to Linear Program (Contd.,) Video
  49. Lecture 49: Dual Fitting Video
  50. Lecture 50: Dual Fitting (Contd.) Video
  51. Lecture 51 : Dual Fitting Video
  52. Lecture 52 : Set Cover using LP rounding Video
  53. Lecture 53 : Vertex Cover using reduction to set cover Video
  54. Lecture 54 : Vertex Cover LP Video
  55. Lecture 55 : Randomized Rounding Video
  56. Lecture 56: Primal Dual Scheme Video
  57. Lecture 57: Introduction to Parameterized Algorithm Video
  58. Lecture 58: Faster FPT Algorithm for Vertex Cover Video
  59. Lecture 59: Introduction to Kernelization Video
  60. Lecture 60: Linear Programming Based Kernels Video
  61. Live Session 20-02-2024 Video
  62. Live Session 08-03-2024 Video
  63. Live Session 08-04-2024 Video
  64. Live Session 25-02-2025 Video
  65. Live Session 11-03-2025 Video
  66. Live Session 15-04-2025 Video