IIT Kharagpur · Computer Science

Second Level Algorithms

Prof. Palash Dey · 60 free video lectures

This is a second level algorithms course. We will cover the following topics: amortized analysis, Fibonacci heap, network flow, computational geometry, NP-completeness, approximation algorithms, randomized algorithms, and parameterized algorithms.

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 1: Amortized Complexity: What and Why?
  2. Lecture 2: Aggregate Method and Its Use in Multi-Stack
  3. Lecture 3: Use of Aggregate Method in Amortized Analysis of Binary Counter, Accounting Method and its Applications in the Amortized Analysi…
  4. Lecture 4: Potential Method and Its Use in the Amortized Analysis of Multi-stack and Binary Counter
  5. Lecture 5: Dynamic Table
  6. Lecture 6: Dynamic Table Cont.
  7. Lecture 7: Fibonacci Heap: Creation, Insertion
  8. Lecture 8: Fibonacci Heap: Extract Min
  9. Lecture 9: Fibonacci Heap: Pseudocode of Insertion, Extract Min
  10. Lecture 10: Fibonacci Heap: Decrease Key, Amortized Analysis of Insertion, Extract Min
  11. Lecture 11: Fibonacci Heap: Amortized Analysis of Decrease Key
  12. Lecture 12: Fibonacci Heap: Amortized Analysis Cont.
  13. Lecture 13: Fibonacci Heap: Amortized Analysis Cont., Introduction to Maximum Flow
  14. Lecture 14: Maximum Flow: Naive Greedy Approach
  15. Lecture 15: Maximum Flow: Residual Graph
  16. Lecture 16: Maximum Flow: Ford Fulkerson Method
  17. Lecture 17: Integrality of Maximum Flow
  18. Lecture 18: Maximum Flow, Layered Residual Graph
  19. Lecture 19: Maximum Flow, Edmond-Karp Algorithm
  20. Lecture 20: Maximum Flow, Dinic's Algorithm
  21. Lecture 21: Maximum Flow, Dinic's Algorithm Cont.
  22. Lecture 22: Dry Run of Ford-Fulkerson Method, Edmond-Karp Algorithm, and Dinic's Algorithm
  23. Lecture 23: Overview of Push Relabel Algorithm
  24. Lecture 24: Pseudocode and Dry Run of Push Relabel Algorithm
  25. Lecture 25: Invariants Maintained by Push Relabel Algorithm
  26. Lecture 26: Proof of Correctness of Push Relabel Algorithm: A Key Lemma
  27. Lecture 27: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Relabel and Saturating Push Operations
  28. Lecture 28: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Non-Saturating Push Operations
  29. Lecture 29: Generalization of Maximum Flow
  30. Lecture 30: Generalization of Maximum Flow Cont. Max Flow Min Cut Theorem
  31. Lecture 31: Maximum Flow Minimum Cut Cont., Maximum Bipartite Matching
  32. Lecture 32: Maximum Bipartite Matching
  33. Lecture 33: Hall's Marriage Theorem
  34. Lecture 34: Flow Path Decomposition
  35. Lecture 35: Stable Matching
  36. Lecture 36: Gale Shapley Algorithm
  37. Lecture 37: Gale Shapley Algorithm Cont.
  38. Lecture 38: Maximum Flow Based Minimum Cut Algorithm
  39. Lecture 39: Karger's Minimum Cut Algorithm
  40. Lecture 40: Karger-Stein Algorithm
  41. Lecture 41: Karger-Stein Algorithm Cont.
  42. Lecture 42: Maximum Cut in General Graph
  43. Lecture 43: Edmond's Blossom Algorithm
  44. Lecture 44: Edmond's Blossom Algorithm Cont.
  45. Lecture 45: Edmond's Blossom Algorithm Cont.
  46. Lecture 46: Edmond's Blossom Algorithm Cont.
  47. Lecture 47: Edmond's Blossom Algorithm Cont.
  48. Lecture 48: Edmond's Blossom Algorithm Cont., Order Statistics
  49. Lecture 49: Order Statistics
  50. Lecture 50: Order Statistics Cont.
  51. Lecture 51: Linear Time Selection
  52. Lecture 52: Linear Time Selection Cont.
  53. Lecture 53: String Matching: KMP Algorithm
  54. Lecture 54: String Matching: KMP Algorithm Cont.
  55. Lecture 55: Introduction to NP
  56. Lecture 56: Self Reduction
  57. Lecture 57: NP Completeness
  58. Lecture 58: NP Completeness of 3 SAT
  59. Lecture 59: NP Completeness of Clique and Independent Set
  60. Lecture 60: NP Completeness of Vertex Cover and Subset Sum

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