# Second Level Algorithms

- Institution: IIT Kharagpur
- Department: Computer Science and Engineering
- Teacher: Prof. Palash Dey
- Level: Graduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106105704)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106105704)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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.

Intended audience: PG students

Prerequisites: A first level course on Algorithms

## Lectures

1. [Lecture 1: Amortized Complexity: What and Why?](https://invisiblenetwork.ai/learn/nptel/106105704/aa41c172a97d) (YouTube)
2. [Lecture 2: Aggregate Method and Its Use in Multi-Stack](https://invisiblenetwork.ai/learn/nptel/106105704/3168720d2441) (YouTube)
3. [Lecture 3: Use of Aggregate Method in Amortized Analysis of Binary Counter, Accounting Method and its Applications in the Amortized Analysis of Multi-stack and Binary Counter](https://invisiblenetwork.ai/learn/nptel/106105704/cf45d98b3874) (YouTube)
4. [Lecture 4: Potential Method and Its Use in the Amortized Analysis of Multi-stack and Binary Counter](https://invisiblenetwork.ai/learn/nptel/106105704/f37c6c21750f) (YouTube)
5. [Lecture 5: Dynamic Table](https://invisiblenetwork.ai/learn/nptel/106105704/4963e174ad85) (YouTube)
6. [Lecture 6: Dynamic Table Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/8987e1b21b66) (YouTube)
7. [Lecture 7: Fibonacci Heap: Creation, Insertion](https://invisiblenetwork.ai/learn/nptel/106105704/38830c679c08) (YouTube)
8. [Lecture 8: Fibonacci Heap: Extract Min](https://invisiblenetwork.ai/learn/nptel/106105704/170f80b30637) (YouTube)
9. [Lecture 9: Fibonacci Heap: Pseudocode of Insertion, Extract Min](https://invisiblenetwork.ai/learn/nptel/106105704/b318bad481d0) (YouTube)
10. [Lecture 10: Fibonacci Heap: Decrease Key, Amortized Analysis of Insertion, Extract Min](https://invisiblenetwork.ai/learn/nptel/106105704/4e895540dd70) (YouTube)
11. [Lecture 11: Fibonacci Heap: Amortized Analysis of Decrease Key](https://invisiblenetwork.ai/learn/nptel/106105704/bbb14ff7ace6) (YouTube)
12. [Lecture 12: Fibonacci Heap: Amortized Analysis Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/5fff8ba36c8f) (YouTube)
13. [Lecture 13: Fibonacci Heap: Amortized Analysis Cont., Introduction to Maximum Flow](https://invisiblenetwork.ai/learn/nptel/106105704/0b1f2533d1e3) (YouTube)
14. [Lecture 14: Maximum Flow: Naive Greedy Approach](https://invisiblenetwork.ai/learn/nptel/106105704/16c64c9200d6) (YouTube)
15. [Lecture 15: Maximum Flow: Residual Graph](https://invisiblenetwork.ai/learn/nptel/106105704/bfbeeeb695c7) (YouTube)
16. [Lecture 16: Maximum Flow: Ford Fulkerson Method](https://invisiblenetwork.ai/learn/nptel/106105704/262cdf850ecf) (YouTube)
17. [Lecture 17: Integrality of Maximum Flow](https://invisiblenetwork.ai/learn/nptel/106105704/afdcd550fbf4) (YouTube)
18. [Lecture 18: Maximum Flow, Layered Residual Graph](https://invisiblenetwork.ai/learn/nptel/106105704/d4b3b52d55e3) (YouTube)
19. [Lecture 19: Maximum Flow, Edmond-Karp Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/29ac10cac966) (YouTube)
20. [Lecture 20: Maximum Flow, Dinic's Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/099383662d09) (YouTube)
21. [Lecture 21: Maximum Flow, Dinic's Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/b7c2755d4654) (YouTube)
22. [Lecture 22: Dry Run of Ford-Fulkerson Method, Edmond-Karp Algorithm, and Dinic's Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/d6321324c6cc) (YouTube)
23. [Lecture 23: Overview of Push Relabel Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/c6521b2bb6c6) (YouTube)
24. [Lecture 24: Pseudocode and Dry Run of Push Relabel Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/9edfec827bfa) (YouTube)
25. [Lecture 25: Invariants Maintained by Push Relabel Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/b441647f4f30) (YouTube)
26. [Lecture 26: Proof of Correctness of Push Relabel Algorithm: A Key Lemma](https://invisiblenetwork.ai/learn/nptel/106105704/72e8d3ebbaf0) (YouTube)
27. [Lecture 27: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Relabel and Saturating Push Operations](https://invisiblenetwork.ai/learn/nptel/106105704/7ee1d61a5646) (YouTube)
28. [Lecture 28: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Non-Saturating Push Operations](https://invisiblenetwork.ai/learn/nptel/106105704/ff48bdcaf44b) (YouTube)
29. [Lecture 29: Generalization of Maximum Flow](https://invisiblenetwork.ai/learn/nptel/106105704/9cabebe86a19) (YouTube)
30. [Lecture 30: Generalization of Maximum Flow Cont. Max Flow Min Cut Theorem](https://invisiblenetwork.ai/learn/nptel/106105704/0facb7b41f74) (YouTube)
31. [Lecture 31: Maximum Flow Minimum Cut Cont., Maximum Bipartite Matching](https://invisiblenetwork.ai/learn/nptel/106105704/66d3441a482e) (YouTube)
32. [Lecture 32: Maximum Bipartite Matching](https://invisiblenetwork.ai/learn/nptel/106105704/59aca23405a3) (YouTube)
33. [Lecture 33: Hall's Marriage Theorem](https://invisiblenetwork.ai/learn/nptel/106105704/4bfdcf32b6fa) (YouTube)
34. [Lecture 34: Flow Path Decomposition](https://invisiblenetwork.ai/learn/nptel/106105704/67c93f4ed41d) (YouTube)
35. [Lecture 35: Stable Matching](https://invisiblenetwork.ai/learn/nptel/106105704/961dad8859fa) (YouTube)
36. [Lecture 36: Gale Shapley Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/bcf47836c48e) (YouTube)
37. [Lecture 37: Gale Shapley Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/ea2af5dc388a) (YouTube)
38. [Lecture 38: Maximum Flow Based Minimum Cut Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/e9459d18037f) (YouTube)
39. [Lecture 39: Karger's Minimum Cut Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/5f91609fe3e1) (YouTube)
40. [Lecture 40: Karger-Stein Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/43bde0052c34) (YouTube)
41. [Lecture 41: Karger-Stein Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/2cbdb2059b03) (YouTube)
42. [Lecture 42: Maximum Cut in General Graph](https://invisiblenetwork.ai/learn/nptel/106105704/eb2f0db744a2) (YouTube)
43. [Lecture 43: Edmond's Blossom Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/67d0355ffc38) (YouTube)
44. [Lecture 44: Edmond's Blossom Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/230f3d6c2b51) (YouTube)
45. [Lecture 45: Edmond's Blossom Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/f50e48027e44) (YouTube)
46. [Lecture 46: Edmond's Blossom Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/776c6d05e339) (YouTube)
47. [Lecture 47: Edmond's Blossom Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/1559992e8ea2) (YouTube)
48. [Lecture 48: Edmond's Blossom Algorithm Cont., Order Statistics](https://invisiblenetwork.ai/learn/nptel/106105704/1fb2889d76c3) (YouTube)
49. [Lecture 49: Order Statistics](https://invisiblenetwork.ai/learn/nptel/106105704/36223dbee6bb) (YouTube)
50. [Lecture 50: Order Statistics Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/5d3aeeb93c40) (YouTube)
51. [Lecture 51: Linear Time Selection](https://invisiblenetwork.ai/learn/nptel/106105704/70c977f6e1a8) (YouTube)
52. [Lecture 52: Linear Time Selection Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/3fd5875bfa5e) (YouTube)
53. [Lecture 53: String Matching: KMP Algorithm](https://invisiblenetwork.ai/learn/nptel/106105704/20e9551b763a) (YouTube)
54. [Lecture 54: String Matching: KMP Algorithm Cont.](https://invisiblenetwork.ai/learn/nptel/106105704/4a22cdbb62a8) (YouTube)
55. [Lecture 55: Introduction to NP](https://invisiblenetwork.ai/learn/nptel/106105704/3fdcb0800a3c) (YouTube)
56. [Lecture 56: Self Reduction](https://invisiblenetwork.ai/learn/nptel/106105704/33b95db2e828) (YouTube)
57. [Lecture 57: NP Completeness](https://invisiblenetwork.ai/learn/nptel/106105704/c5c63a21025f) (YouTube)
58. [Lecture 58: NP Completeness of 3 SAT](https://invisiblenetwork.ai/learn/nptel/106105704/3eeaf8cede3a) (YouTube)
59. [Lecture 59: NP Completeness of Clique and Independent Set](https://invisiblenetwork.ai/learn/nptel/106105704/f9a6583f61a7) (YouTube)
60. [Lecture 60: NP Completeness of Vertex Cover and Subset Sum](https://invisiblenetwork.ai/learn/nptel/106105704/ef8d9ef1a34c) (YouTube)