Learn · NPTEL

Course10610570460 lectures

Second Level Algorithms

Prof. Palash Dey · IIT Kharagpur

Start with lecture 1 At NPTEL

About

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

Week 1

  1. Lecture 1: Amortized Complexity: What and Why? YouTube
  2. Lecture 2: Aggregate Method and Its Use in Multi-Stack 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 YouTube
  4. Lecture 4: Potential Method and Its Use in the Amortized Analysis of Multi-stack and Binary Counter YouTube
  5. Lecture 5: Dynamic Table YouTube

Week 2

  1. Lecture 6: Dynamic Table Cont. YouTube
  2. Lecture 7: Fibonacci Heap: Creation, Insertion YouTube
  3. Lecture 8: Fibonacci Heap: Extract Min YouTube
  4. Lecture 9: Fibonacci Heap: Pseudocode of Insertion, Extract Min YouTube
  5. Lecture 10: Fibonacci Heap: Decrease Key, Amortized Analysis of Insertion, Extract Min YouTube

Week 3

  1. Lecture 11: Fibonacci Heap: Amortized Analysis of Decrease Key YouTube
  2. Lecture 12: Fibonacci Heap: Amortized Analysis Cont. YouTube
  3. Lecture 13: Fibonacci Heap: Amortized Analysis Cont., Introduction to Maximum Flow YouTube
  4. Lecture 14: Maximum Flow: Naive Greedy Approach YouTube
  5. Lecture 15: Maximum Flow: Residual Graph YouTube

Week 4

  1. Lecture 16: Maximum Flow: Ford Fulkerson Method YouTube
  2. Lecture 17: Integrality of Maximum Flow YouTube
  3. Lecture 18: Maximum Flow, Layered Residual Graph YouTube
  4. Lecture 19: Maximum Flow, Edmond-Karp Algorithm YouTube
  5. Lecture 20: Maximum Flow, Dinic's Algorithm YouTube

Week 5

  1. Lecture 21: Maximum Flow, Dinic's Algorithm Cont. YouTube
  2. Lecture 22: Dry Run of Ford-Fulkerson Method, Edmond-Karp Algorithm, and Dinic's Algorithm YouTube
  3. Lecture 23: Overview of Push Relabel Algorithm YouTube
  4. Lecture 24: Pseudocode and Dry Run of Push Relabel Algorithm YouTube
  5. Lecture 25: Invariants Maintained by Push Relabel Algorithm YouTube

Week 6

  1. Lecture 26: Proof of Correctness of Push Relabel Algorithm: A Key Lemma YouTube
  2. Lecture 27: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Relabel and Saturating Push Operations YouTube
  3. Lecture 28: Proof of Correctness of Push Relabel Algorithm: Bounding Number of Non-Saturating Push Operations YouTube
  4. Lecture 29: Generalization of Maximum Flow YouTube
  5. Lecture 30: Generalization of Maximum Flow Cont. Max Flow Min Cut Theorem YouTube

Week 7

  1. Lecture 31: Maximum Flow Minimum Cut Cont., Maximum Bipartite Matching YouTube
  2. Lecture 32: Maximum Bipartite Matching YouTube
  3. Lecture 33: Hall's Marriage Theorem YouTube
  4. Lecture 34: Flow Path Decomposition YouTube
  5. Lecture 35: Stable Matching YouTube

Week 8

  1. Lecture 36: Gale Shapley Algorithm YouTube
  2. Lecture 37: Gale Shapley Algorithm Cont. YouTube
  3. Lecture 38: Maximum Flow Based Minimum Cut Algorithm YouTube
  4. Lecture 39: Karger's Minimum Cut Algorithm YouTube
  5. Lecture 40: Karger-Stein Algorithm YouTube

Week 9

  1. Lecture 41: Karger-Stein Algorithm Cont. YouTube
  2. Lecture 42: Maximum Cut in General Graph YouTube
  3. Lecture 43: Edmond's Blossom Algorithm YouTube
  4. Lecture 44: Edmond's Blossom Algorithm Cont. YouTube
  5. Lecture 45: Edmond's Blossom Algorithm Cont. YouTube

Week 10

  1. Lecture 46: Edmond's Blossom Algorithm Cont. YouTube
  2. Lecture 47: Edmond's Blossom Algorithm Cont. YouTube
  3. Lecture 48: Edmond's Blossom Algorithm Cont., Order Statistics YouTube
  4. Lecture 49: Order Statistics YouTube
  5. Lecture 50: Order Statistics Cont. YouTube

Week 11

  1. Lecture 51: Linear Time Selection YouTube
  2. Lecture 52: Linear Time Selection Cont. YouTube
  3. Lecture 53: String Matching: KMP Algorithm YouTube
  4. Lecture 54: String Matching: KMP Algorithm Cont. YouTube
  5. Lecture 55: Introduction to NP YouTube

Week 12

  1. Lecture 56: Self Reduction YouTube
  2. Lecture 57: NP Completeness YouTube
  3. Lecture 58: NP Completeness of 3 SAT YouTube
  4. Lecture 59: NP Completeness of Clique and Independent Set YouTube
  5. Lecture 60: NP Completeness of Vertex Cover and Subset Sum YouTube

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
Graduate
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