IIT Madras Advanced Algorithms Lectures
BSCS402147 lectures8 weeks
Weeks
- Week 15 lecturesA generic optimization problem · Definition & examples · Greedy works | understanding matroids & greedy algorithms · Greedy fails on non-matroid structures | subset systems & exchange property · Scheduling with deadlines | greedy algorithms & matroid theory
- Week 27 lecturesMax-flow: an introduction · The ford-fulkerson algorithm · Maxflow-mincut duality · Flow decomposition · Tuple selection · Exam scheduling · IPL elimination
- Week 312 lecturesP, NP, NP-hardness, NP-completeness · Maximum independent set · Graph coloring · 3d matching · Finding the right problem · Longest increasing subsequence (lis) | definition & initial thoughts · A first dynamic programming for longest increasing subsequence · A second dynamic programming for longest increasing subsequence · Subset sum & set cover · Optimal binary search trees (bsts) | part I · Optimal binary search trees (bsts) | part II · Max independent set on trees
- Week 42 lectures1 : Randomized quick sort · Randomized quick sort - analysis
- Week 52 lecturesVertex cover via maximal matchings · Vertex cover via linear programming (LP) rounding
- Week 64 lecturesParameterized algorithms, vertex cover, branching, fixed-parameter tractability · Iterative compression, vertex cover · Iterative compression, feedback vertex set · Subset Sum
- Week 83 lecturesBranch & bound for mis · Principle of inclusion–exclusion for chromatic number (PIE) for chromatic coding | part I · Principle of inclusion–exclusion for chromatic number (PIE) for chromatic coding | part II
- Week 105 lecturesWarm up: mis on thin grids · Pathwidth: definition, examples & separations · Treewidth: definition, examples, and separations · Dynamic programming (dp) for maximum independent set(MIS)on bounded-treewidth graphs · Nice tree decompositions
More lectures
Video 1 · 23:56