Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Palash Dey
NPTEL Co-ordinating Institute : IIT Kharagpur
NPTEL Lecture Count : 60
NPTEL Course Size : 3.6 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
Lecture 1 - Introduction to Maximum Flow
Lecture 2 - Ford - Fulkerson Method
Lecture 3 - Edmond - Karp Algorithm
Lecture 4 - Edmond - Karp Algorithm (Continued...)
Lecture 5 - Flow Decomposition
Lecture 6 - Maximum Bipartite Matching, Fattest Augmenting Path
Lecture 7 - Karger's Algorithm
Lecture 8 - Augmenting Path
Lecture 9 - Edmonds Blossom Algorithm
Lecture 10 - Edmond - Karp Algorithm (Continued...)
Lecture 11 - Introduction to Randomized Algorithm
Lecture 12 - Polynomial Identity Testing
Lecture 13 - Perfect Bipartite Matching, Randomized Quicksort
Lecture 14 - Concentration Inequalities: Markov, Chebyshev, Chernoff
Lecture 15 - Proof of Chernoff Bound
Lecture 16 - Coupon Collector Problem
Lecture 17 - Balls and Bins
Lecture 18 - Balls and Bins (Continued...)
Lecture 19 - Two Point Sampling
Lecture 20 - Randomized Algorithm for 2 SAT
Lecture 21 - Markov Chain, Periodicity, Stationary Distribution
Lecture 22 - Mixing Time, Reversible Markov Chain
Lecture 23 - Metropolis Algorithm, Markov Chain on Independent Sets
Lecture 24 - Random Walk on Cycles
Lecture 25 - Shuffling Cards
Lecture 26 - Monte Carlo Method, Hitting Time, Cover Time
Lecture 27 - DNF Counting
Lecture 28 - DNF Counting (Continued...)
Lecture 29 - Counting Independent Sets of a Graph
Lecture 30 - Counting Independent Sets of a Graph (Continued...)
Lecture 31 - Introduction of NP, co-NP, and P
Lecture 32 - Turing Reduction, Karp Reduction
Lecture 33 - NP - Completeness of 3SAT
Lecture 34 - NP - Completeness of Independent Set
Lecture 35 - NP - Completeness of vertex cover and clique
Lecture 36 - NP - Completeness of 3-coloring
Lecture 37 - NP - Completeness of Subset sum and Knapsack
Lecture 38 - NP - Completeness of set cover, Weak and Strong NP - completeness
Lecture 39 - Self Reduction
Lecture 40 - Randomized Approximation Algorithm
Lecture 41 - Derandomization
Lecture 42 - Travelling Salesman Problem
Lecture 43 - 2-Factor Approximation Algorithm for Metric TSP
Lecture 44 - 1.5-Factor Approximation Algorithm for Metric TSP
Lecture 45 - Approximation Algorithm for Set Cover
Lecture 46 - FPTAS for Knapsack
Lecture 47 - Introduction to Linear Program
Lecture 48 - Introduction to Linear Program (Continued...,)
Lecture 49 - Dual Fitting
Lecture 50 - Dual Fitting (Continued...)
Lecture 51 - Dual Fitting
Lecture 52 - Set Cover using LP rounding
Lecture 53 - Vertex Cover using reduction to set cover
Lecture 54 - Vertex Cover LP
Lecture 55 - Randomized Rounding
Lecture 56 - Primal Dual Scheme
Lecture 57 - Introduction to Parameterized Algorithm
Lecture 58 - Faster FPT Algorithm for Vertex Cover
Lecture 59 - Introduction to Kernelization
Lecture 60 - Linear Programming Based Kernels