MA-INF 1317 Lab Parameterized Complexity

General Information

When Where Lecturer
Thursday 14:30 - 18:00LBH / E.08Fafianie, Kratsch

The first meeting will be on Thursday, 22th October, 2015, at 14:30. A second startup meeting will be on Thursday, 29th October, at 14:30. You can also send an email to fafianie@cs.uni-bonn.de if you would like to participate but cannot make it to either time slot.

Prior attendance of the lecture „Parameterized Complexity“ is helpful but not required. The considered problems will be presented in a self-contained way. Furthermore, the topic of parameterized complexity will be interpreted rather loosely and contain anything that is deemed interesting. Typically, questions will motivated by current research interests.

We will consider problems related to enumeration of candidate solutions for certain NP-hard problems. You will be able to start with a simple enumeration algorithm and then engineer and tweak it to obtain the results faster. The initial algorithm can then be used to check your improved versions. You can work alone or in teams of two. It is intended to meet every two weeks to discuss progress, and there are certain milestones of getting an initial and later an improved algorithm. Weekly meetings are possible as well, if desired.

Towards the end of the term you should submit a short report detailing problem definitions, some technical background, your implementation, and some experimental results. Additionally, there should be a short presentation about your work.