Learn · NPTEL

Course10610524266 lectures

Selected Topics in Algorithms

Prof. Palash Dey · IIT Kharagpur

Start with lecture 1 At NPTEL

Lectures

Week 01

  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

Week 02

  1. Lecture 06 : Maximum Bipartite Matching, Fattest Augmenting Path Video
  2. Lecture 07 : Karger's Algorithm Video
  3. Lecture 08 : Augmenting Path Video
  4. Lecture 09 : Edmonds Blossom Algorithm Video
  5. Lecture 10 : Edmond - Karp Algorithm (Contd.) Video

Week 03

  1. Lecture 11: Introduction to Randomized Algorithm Video
  2. Lecture 12: Polynomial Identity Testing Video
  3. Lecture 13: Perfect Bipartite Matching, Randomized Quicksort Video
  4. Lecture 14: Concentration Inequalities: Markov, Chebyshev, Chernoff Video
  5. Lecture 15: Proof of Chernoff Bound Video

Week 04

  1. Lecture 16: Coupon Collector Problem Video
  2. Lecture 17: Balls and Bins Video
  3. Lecture 18: Balls and Bins Contd. Video
  4. Lecture 19: Two Point Sampling Video
  5. Lecture 20: Randomized Algorithm for 2 SAT Video

Week 05

  1. Lecture 21: Markov Chain, Periodicity, Stationary Distribution Video
  2. Lecture 22: Mixing Time, Reversible Markov Chain Video
  3. Lecture 23: Metropolis Algorithm, Markov Chain on Independent Sets Video
  4. Lecture 24: Random Walk on Cycles Video
  5. Lecture 25: Shuffling Cards Video

Week 06

  1. Lecture 26: Monte Carlo Method, Hitting Time, Cover Time Video
  2. Lecture 27: DNF Counting Video
  3. Lecture 28: DNF Counting (Contd.) Video
  4. Lecture 29: Counting Independent Sets of a Graph Video
  5. Lecture 30: Counting Independent Sets of a Graph (Contd.) Video

Week 07

  1. Lecture 31: Introduction of NP, co-NP, and P Video
  2. Lecture 32: Turing Reduction, Karp Reduction Video
  3. Lecture 33: NP - Completeness of 3SAT Video
  4. Lecture 34: NP - Completeness of Independent Set Video
  5. Lecture 35: NP - Completeness of vertex cover and clique Video

Week 08

  1. Lecture 36: NP - Completeness of 3 - coloring Video
  2. Lecture 37: NP - Completeness of Subset sum and Knapsack Video
  3. Lecture 38: NP - Completeness of set cover, Weak and Strong NP - completeness Video
  4. Lecture 39: Self Reduction Video
  5. Lecture 40: Randomized Approximation Algorithm Video

Week 09

  1. Lecture 41: Derandomization Video
  2. Lecture 42: Travelling Salesman Problem Video
  3. Lecture 43: 2 - Factor Approximation Algorithm for Metric TSP Video
  4. Lecture 44: 1.5 - Factor Approximation Algorithm for Metric TSP Video
  5. Lecture 45: Approximation Algorithm for Set Cover Video

week-10

  1. Lecture 46: FPTAS for Knapsack Video
  2. Lecture 47: Introduction to Linear Program Video
  3. Lecture 48: Introduction to Linear Program (Contd.,) Video
  4. Lecture 49: Dual Fitting Video
  5. Lecture 50: Dual Fitting (Contd.) Video

week-11

  1. Lecture 51 : Dual Fitting Video
  2. Lecture 52 : Set Cover using LP rounding Video
  3. Lecture 53 : Vertex Cover using reduction to set cover Video
  4. Lecture 54 : Vertex Cover LP Video
  5. Lecture 55 : Randomized Rounding Video

week-12

  1. Lecture 56: Primal Dual Scheme Video
  2. Lecture 57: Introduction to Parameterized Algorithm Video
  3. Lecture 58: Faster FPT Algorithm for Vertex Cover Video
  4. Lecture 59: Introduction to Kernelization Video
  5. Lecture 60: Linear Programming Based Kernels Video

Live Session

  1. Live Session 20-02-2024 Video
  2. Live Session 08-03-2024 Video
  3. Live Session 08-04-2024 Video
  4. Live Session 25-02-2025 Video
  5. Live Session 11-03-2025 Video
  6. Live Session 15-04-2025 Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kharagpur
Department
Computer Science and Engineering
Teacher
Prof. Palash Dey
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed