Parameterized Algorithms

This is a first course on techniques in parameterized algorithms, a paradigm of algorithm design that analyzes running time in finer detail than classical complexity theory: instead of expressing the running time as a function of the input size only, dependence on one or more parameters of the input instance is taken into account. This is a fast-evolving field and a fundamental approach to coping with NP-hardness, alongside approximation and randomized algorithms. The course will be a natural follow-up to a first course in algorithms and data structures for theoretically-inclined students and those who are curious about approaches to dealing with the theoretical limitations that emerge from the theory of NP-completeness.Remark 1. A companion course might cover topics focused entirely on lower bounds (covering W-hardness, ETH and SETH-based hardness, hardness based on the UGC, and hardness of kernelization). A natural follow-up course might cover topics in the intersection of parameterized and approximation algorithms.Remark 2. Lecture videos indicative of the course content can be found at this playlist from a previous offering of this course at the Institute for Mathematical Sciences, ChennaiINTENDED AUDIENCE : Undergraduate students who have already done a basic data structures/algorithms course.PREREQUISITES : Data Structures and Algorithms

Week-1: Kernelization
Week-2: Bounded Search Trees Week-3: Iterative Compression
Week-4: Randomized Techniques
Week-5: Treewidth - I
Week-6:Treewidth - II
Week-7: Miscellaneous Techniques: ILP and DP over subsets
Week-8: Important Separators
Week-9: Algebraic Techniques
Week-10: Cut and Count
Week-11: Matroids
Week-12: Parameterized Intractability