# Selected Topics in Algorithms

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

## Lectures

1. [Lecture 01 : Introduction to Maximum Flow](https://invisiblenetwork.ai/learn/nptel/106105242/2c183cae5171) (Video)
2. [Lecture 02 : Ford - Fulkerson Method](https://invisiblenetwork.ai/learn/nptel/106105242/46e2307b63ed) (Video)
3. [Lecture 03 : Edmond - Karp Algorithm](https://invisiblenetwork.ai/learn/nptel/106105242/6e6996896106) (Video)
4. [Lecture 04 : Edmond - Karp Algorithm (Contd.)](https://invisiblenetwork.ai/learn/nptel/106105242/0f32c1217ac0) (Video)
5. [Lecture 05 : Flow Decomposition](https://invisiblenetwork.ai/learn/nptel/106105242/9e54f428f566) (Video)
6. [Lecture 06 : Maximum Bipartite Matching, Fattest Augmenting Path](https://invisiblenetwork.ai/learn/nptel/106105242/4da2f13e8596) (Video)
7. [Lecture 07 : Karger's Algorithm](https://invisiblenetwork.ai/learn/nptel/106105242/5da26fdb2192) (Video)
8. [Lecture 08 : Augmenting Path](https://invisiblenetwork.ai/learn/nptel/106105242/6ff7d9c64d54) (Video)
9. [Lecture 09 : Edmonds Blossom Algorithm](https://invisiblenetwork.ai/learn/nptel/106105242/c4353309af34) (Video)
10. [Lecture 10 : Edmond - Karp Algorithm (Contd.)](https://invisiblenetwork.ai/learn/nptel/106105242/7ff108b208b3) (Video)
11. [Lecture 11: Introduction to Randomized Algorithm](https://invisiblenetwork.ai/learn/nptel/106105242/63770b24816d) (Video)
12. [Lecture 12: Polynomial Identity Testing](https://invisiblenetwork.ai/learn/nptel/106105242/32af3f18a82c) (Video)
13. [Lecture 13: Perfect Bipartite Matching, Randomized Quicksort](https://invisiblenetwork.ai/learn/nptel/106105242/34a35df39adb) (Video)
14. [Lecture 14: Concentration Inequalities: Markov, Chebyshev, Chernoff](https://invisiblenetwork.ai/learn/nptel/106105242/5ddb9c2402ce) (Video)
15. [Lecture 15: Proof of Chernoff Bound](https://invisiblenetwork.ai/learn/nptel/106105242/f4ceee0b9a39) (Video)
16. [Lecture 16: Coupon Collector Problem](https://invisiblenetwork.ai/learn/nptel/106105242/d0de863e3941) (Video)
17. [Lecture 17: Balls and Bins](https://invisiblenetwork.ai/learn/nptel/106105242/dd110d86ccf3) (Video)
18. [Lecture 18: Balls and Bins Contd.](https://invisiblenetwork.ai/learn/nptel/106105242/4a373e8c5280) (Video)
19. [Lecture 19: Two Point Sampling](https://invisiblenetwork.ai/learn/nptel/106105242/2267046422f5) (Video)
20. [Lecture 20: Randomized Algorithm for 2 SAT](https://invisiblenetwork.ai/learn/nptel/106105242/e83f69cc60dc) (Video)
21. [Lecture 21: Markov Chain, Periodicity, Stationary Distribution](https://invisiblenetwork.ai/learn/nptel/106105242/51dec2428a87) (Video)
22. [Lecture 22: Mixing Time, Reversible Markov Chain](https://invisiblenetwork.ai/learn/nptel/106105242/9ddb7b015a3f) (Video)
23. [Lecture 23: Metropolis Algorithm, Markov Chain on Independent Sets](https://invisiblenetwork.ai/learn/nptel/106105242/45bc05e19476) (Video)
24. [Lecture 24: Random Walk on Cycles](https://invisiblenetwork.ai/learn/nptel/106105242/3279138f0e94) (Video)
25. [Lecture 25: Shuffling Cards](https://invisiblenetwork.ai/learn/nptel/106105242/ff1292a2d0f8) (Video)
26. [Lecture 26: Monte Carlo Method, Hitting Time, Cover Time](https://invisiblenetwork.ai/learn/nptel/106105242/24151b81cbc5) (Video)
27. [Lecture 27: DNF Counting](https://invisiblenetwork.ai/learn/nptel/106105242/2c4eab49a349) (Video)
28. [Lecture 28: DNF Counting (Contd.)](https://invisiblenetwork.ai/learn/nptel/106105242/24f589af3799) (Video)
29. [Lecture 29: Counting Independent Sets of a Graph](https://invisiblenetwork.ai/learn/nptel/106105242/83eb46746378) (Video)
30. [Lecture 30: Counting Independent Sets of a Graph (Contd.)](https://invisiblenetwork.ai/learn/nptel/106105242/20916d32e8e6) (Video)
31. [Lecture 31: Introduction of NP, co-NP, and P](https://invisiblenetwork.ai/learn/nptel/106105242/15c0e5a7766d) (Video)
32. [Lecture 32: Turing Reduction, Karp Reduction](https://invisiblenetwork.ai/learn/nptel/106105242/890cf35ddf70) (Video)
33. [Lecture 33: NP - Completeness of 3SAT](https://invisiblenetwork.ai/learn/nptel/106105242/9a39a63b05ff) (Video)
34. [Lecture 34: NP - Completeness of Independent Set](https://invisiblenetwork.ai/learn/nptel/106105242/628d1bdaf748) (Video)
35. [Lecture 35: NP - Completeness of vertex cover and clique](https://invisiblenetwork.ai/learn/nptel/106105242/be0e4c76544b) (Video)
36. [Lecture 36: NP - Completeness of 3 - coloring](https://invisiblenetwork.ai/learn/nptel/106105242/8b179f616236) (Video)
37. [Lecture 37: NP - Completeness of Subset sum and Knapsack](https://invisiblenetwork.ai/learn/nptel/106105242/6ad49c7eb3bb) (Video)
38. [Lecture 38: NP - Completeness of set cover, Weak and Strong NP - completeness](https://invisiblenetwork.ai/learn/nptel/106105242/3f79bb1ffa6c) (Video)
39. [Lecture 39: Self Reduction](https://invisiblenetwork.ai/learn/nptel/106105242/26a89de0eadd) (Video)
40. [Lecture 40: Randomized Approximation Algorithm](https://invisiblenetwork.ai/learn/nptel/106105242/d87281d85eb5) (Video)
41. [Lecture 41: Derandomization](https://invisiblenetwork.ai/learn/nptel/106105242/9c3d90022cb6) (Video)
42. [Lecture 42: Travelling Salesman Problem](https://invisiblenetwork.ai/learn/nptel/106105242/52ef9c4d4b46) (Video)
43. [Lecture 43: 2 - Factor Approximation Algorithm for Metric TSP](https://invisiblenetwork.ai/learn/nptel/106105242/59df450c2f29) (Video)
44. [Lecture 44: 1.5 - Factor Approximation Algorithm for Metric TSP](https://invisiblenetwork.ai/learn/nptel/106105242/11a7c1b8b937) (Video)
45. [Lecture 45: Approximation Algorithm for Set Cover](https://invisiblenetwork.ai/learn/nptel/106105242/c5e092940308) (Video)
46. [Lecture 46: FPTAS for Knapsack](https://invisiblenetwork.ai/learn/nptel/106105242/8e75020dfa24) (Video)
47. [Lecture 47: Introduction to Linear Program](https://invisiblenetwork.ai/learn/nptel/106105242/92ad74fc502e) (Video)
48. [Lecture 48: Introduction to Linear Program (Contd.,)](https://invisiblenetwork.ai/learn/nptel/106105242/7b47942c10eb) (Video)
49. [Lecture 49: Dual Fitting](https://invisiblenetwork.ai/learn/nptel/106105242/f39b1dba7d25) (Video)
50. [Lecture 50: Dual Fitting (Contd.)](https://invisiblenetwork.ai/learn/nptel/106105242/0e91760e645b) (Video)
51. [Lecture 51 : Dual Fitting](https://invisiblenetwork.ai/learn/nptel/106105242/26b7f091caeb) (Video)
52. [Lecture 52 : Set Cover using LP rounding](https://invisiblenetwork.ai/learn/nptel/106105242/836bb8af99d8) (Video)
53. [Lecture 53 : Vertex Cover using reduction to set cover](https://invisiblenetwork.ai/learn/nptel/106105242/755871040685) (Video)
54. [Lecture 54 : Vertex Cover LP](https://invisiblenetwork.ai/learn/nptel/106105242/90bd763bf679) (Video)
55. [Lecture 55 : Randomized Rounding](https://invisiblenetwork.ai/learn/nptel/106105242/b399f018a5aa) (Video)
56. [Lecture 56: Primal Dual Scheme](https://invisiblenetwork.ai/learn/nptel/106105242/ebfd17365841) (Video)
57. [Lecture 57: Introduction to Parameterized Algorithm](https://invisiblenetwork.ai/learn/nptel/106105242/ea936718fbe5) (Video)
58. [Lecture 58: Faster FPT Algorithm for Vertex Cover](https://invisiblenetwork.ai/learn/nptel/106105242/3f0c9f1bb50d) (Video)
59. [Lecture 59: Introduction to Kernelization](https://invisiblenetwork.ai/learn/nptel/106105242/8a1355beee3c) (Video)
60. [Lecture 60: Linear Programming Based Kernels](https://invisiblenetwork.ai/learn/nptel/106105242/26054f235f09) (Video)
61. [Live Session 20-02-2024](https://invisiblenetwork.ai/learn/nptel/106105242/2c183cae5171-2) (Video)
62. [Live Session 08-03-2024](https://invisiblenetwork.ai/learn/nptel/106105242/46e2307b63ed-2) (Video)
63. [Live Session 08-04-2024](https://invisiblenetwork.ai/learn/nptel/106105242/6e6996896106-2) (Video)
64. [Live Session 25-02-2025](https://invisiblenetwork.ai/learn/nptel/106105242/0f32c1217ac0-2) (Video)
65. [Live Session 11-03-2025](https://invisiblenetwork.ai/learn/nptel/106105242/9e54f428f566-2) (Video)
66. [Live Session 15-04-2025](https://invisiblenetwork.ai/learn/nptel/106105242/4da2f13e8596-2) (Video)