NOC:Selected Topics in Algorithms

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