IIT Kharagpur · Computer Science

Selected Topics in Algorithms

Prof. Palash Dey · 2024 · 66 free video lectures

66 video lectures. Topics: Introduction to Maximum Flow; Ford - Fulkerson Method; Edmond - Karp Algorithm; Edmond - Karp Algorithm (Contd.); Flow Decomposition; Maximum Bipartite Matching, Fattest Augmenting Path; Karger's Algorithm; Augmenting Path; Edmonds Blossom Algorithm; Introduction to…

▶ Play on Open Lecture HallCourse page ↗

Lectures

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

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

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