Welcome

In Algorithms (2ILC0), you learn that many computational problems are NP-hard. It is widely believed that for such problems, no algorithm exists that always finds the optimal solution efficiently (in polynomial time). One way to deal with NP-hard problems is to use approximation algorithms, as discussed in Advanced Algorithms (2IMA10), or to apply heuristics (2ILH0). However, it is of great practical and theoretical relevance to investigate under which circumstances computing exact solutions is still feasible. This leads to the concept of parameterized algorithms and the corresponding parameterized complexity theory, which are explored in this course.

MODULES ➔

SCHEDULE ➔

☵ Course structure

The course has weekly lectures and an office hour. The material is tested through weekly homework sets, each covering two lectures. The weekly schedule for this course is:

Tuesday 7+8 (15:30 - 17:15): lecture in Atlas -1.822.
Thursday 3+4 (10:45 - 12:30): lecture in Auditorium 11.
Friday 12:30 - 13:30: office hours in MF 7.071a.
Tuesday 23:59: homework set deadline.
Wednesday 23:59: peer grading deadline.

During the office hours you can ask for help on the homework sets. You can even show your solutions (including typeset solutions that you are planning to hand in), and ask for feedback e.g. about the level of detail of your solution, or about whether the general idea of your solution is correct.

Lectures are given live, on-campus. The final exam is on-campus using ANS Delft on paper. You are allowed to bring one handwritten A4 sheet of notes (covered on both sides) to the exam.

⚐ Prerequisites

In order to take this course, you must have completed and passed Algorithms (2ILC0) or a similar course. Thus, you should know the following:

O-notation, Ω-notation, Θ-notation; how to analyze algorithms;
Basic graph algorithms: depth/breadth first search, topological sort, computing minimum spanning trees, computing maximum flows and minimum cuts
Algorithm design techniques such as greedy algorithms, dynamic programming, backtracking
Graph terminology, representations of graphs (adjacency lists and adjacency matrix), and basic graph algorithms (BFS, DFS, topological sort)
The definition of an NP-hard problem and the use of reductions to prove problems are NP-hard

⚐ Learning Goals

After completing the course, the successful student:

Knows the definitions of the complexity classes FPT and W[1], of a parameterized problem, of the Exponential Time Hypothesis and its Strong variant, of kernelization, and of various types of reductions.
Can design parameterized reductions to prove the W[1]-hardness of parameterized problems.
Can apply the algorithmic design techniques of kernelization, bounded-depth search trees, iterative compression, dynamic programming over subsets, and important separators to create exact fixed-parameter tractable algorithms for NP-hard problems.
Can prove the correctness of such algorithms.
Can analyze the running time of parameterized algorithms using branching vectors, recurrences, and the binomial theorem to estimate the size of recursion trees.

✐ Examination

The final grade will be based on two components: homework exercises and an exam.

There are 6 sets of homework exercises, which together determine 50% of your final grade. The grade for each homework set consists of some points for manually graded exercises, some points for automatically graded exercises, and some points based on peer-reviewing exercises from fellow students. Some details will be discussed during the first lecture. Based on the six resulting scores, the homework score is calculated as follows:

take the sum all 6 homework scores, subtract the lowest score among sets 1 - 5, and divide the result by 5.

In other words, the worst-scoring grade out of the first 5 does not count, and the 6th score always counts. Note that there is no opportunity to improve your homework grade after all 6 sets have been submitted.

On the exam you can score up to 10 points.

The final grade is then determined as follows:

If your exam grade is at least 5.0, your final grade is the rounded average of your homework grade and your exam grade. In other words: if your exam grade is at least 5.0, you pass if your homework grade is at least 11 minus your exam grade.
If your exam grade is less than 5.0, your final grade is the minimum of a 5 and the rounded average of your homework grade and your exam grade. Therefore, if your exam grade is less than 5.0, you fail the course in any case.

📖 Literature

The course is based on the following book:

Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh: Parameterized Algorithms, Springer, 2015. ISBN 978-3-319-21274-6

When logged into the university network or VPN, you can download the PDF of the book for free.

✉ Lecturers & Contact

Thekla Hamm
Lecturer
t.l.s.hamm@tue.nl
MF 7.071a

Thomas Buschman
Student assistant

⚠ This Canvas course is carefully filled with all necessary information. When unexpected differences occur between Canvas and Osiris, the information provided in Osiris is leading.