Parameterized Algorithms

By Prof. Neeldhara, Prof. Saket Saurabh | IIT Gandhinagar, Institute of Mathematical Science

Learners enrolled: 864

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, Chennai

INTENDED AUDIENCE : Undergraduate students who have already done a basic data structures/algorithms course.

PREREQUISITES : Data Structures and Algorithms

Summary

Course Status :	Completed
Course Type :	Elective
Duration :	12 weeks
Category :	Computer Science and Engineering Foundations of Computing
Credit Points :	3
Level :	Undergraduate/Postgraduate
Start Date :	26 Jul 2021
End Date :	15 Oct 2021
Enrollment Ends :	09 Aug 2021
Exam Date :	23 Oct 2021 IST

Note: This exam date is subjected to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

Course layout

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

Books and references

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Parameterized Algorithms. Springer-Verlag, 2015.

(Digital version freely available online.)

Optional References:

1. R.G. Downey, M. R. Fellows: Parameterized Complexity Springer-Verlag, 1999.

2. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006.

3. R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.

4. Daniel Lokshtanov, Meirav Zehavi, Saket Saurabh, Fedor V. Fomin. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019

Instructor bio

Prof. Neeldhara

IIT Gandhinagar

Neeldhara Misra is an Assistant Professor of Computer Science and Engineering at the Indian Institute of Technology, Gandhinagar. Her primary research interest involves the design and analysis of efficient algorithms for “hard” problems in general, and parameterized algorithms in particular. The problems considered are typically concerned with combinatorial optimization, frequently in the context of graph theory, social choice, games, geometry, and constraint satisfaction.

Prof. Saket Saurabh

Institute of Mathematical Science

Prof. Saket Saurabh is a Professor of Theoretical Computer Science at the Institute of Mathematical Sciences, Chennai, India. He is also affiliated to the Department of Informatics, University of Bergen, Norway (as a Professor). His other affiliations include Adjunct Professor at Indian Statistical Institute (ISI) Kolkata (2019-2024) and a member of IRL 2000 ReLaX. His work focuses on designing efficient algorithms (or prove that they do not exist) for hard problems arising in every domain. In particular, he has designed algorithms whose running time is analyzed in terms of different input parameters. In particular, he is interested in Multivariate Complexity or its two variable avatar Parameterized Complexity. His other interests include Graph Theory, Matroids, Matching Theory and Approximation Algorithms.

Course certificate

The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.

The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).

Date and Time of Exams: 23 October 2021 Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.

Registration url: Announcements will be made when the registration form is open for registrations.

The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.

Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.

CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of average of best 8 assignments out of the total 12 assignments given in the course.

Exam score = 75% of the proctored certification exam score out of 100

Final score = Average assignment score + Exam score

YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.

Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Madras .It will be e-verifiable at nptel.ac.in/noc.

Only the e-certificate will be made available. Hard copies will not be dispatched.

Once again, thanks for your interest in our online courses and certification. Happy learning.

- NPTEL team