Parameterized complexity seeks a better understanding of NP-hard problems. In particular, one is interested in finding algorithms that are sufficiently fast despite (exponential) hardness in the worst case. To this end, one studies the influence of problem-specific parameters such as the solution size or certain structural input measures on the time complexity.

In addition to signing up via basis please send an email to kratsch@cs.uni-bonn.de to provide your email address (using „[Parameterized Complexity]“ as the subject). You will receive occasional notifications, (updates to) the lecture notes, and the exercise sheets via email/dropbox. Note that sending an email is not equivalent to signing up on basis and comes with no obligations.

There will be an oral exam at the end of the term. The tentative dates are August 1 and September 11, 2017. There are no requirements for admittance and the final grade is determined solely by the exam.

In the tutorials you will be given time and support to solve exercises in teams of two. Eva-Maria Hols will be present in tutorials and answer your questions or give hints. There will be essentially no presentation of solved exercises since the focus is on solving things yourself. In particular, being able to explain a solution to your neighbor is highly beneficial, and being told that „this is actually quite easy“ is much more believable coming from your neighbor. We also found that (unsurprisingly?) students are much more apt at understanding one anothers problems with a task.

Exercise sets will focus on the current chapter in the lecture and you may have more than one meeting to work one the same set. Working at home is of course encouraged too. We will not grade or proof-read your solutions, but you can verify your ideas by asking Eva-Maria during the tutorial.