Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

NPTEL

Parameterized Algorithms

NPTEL and Indian Institute of Technology Gandhinagar via Swayam

Overview

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

Syllabus

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

Taught by

Prof. Neeldhara, Prof. Saket Saurabh

Related Courses

Reviews

Start your review of Parameterized Algorithms

Never Stop Learning!

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free