Fine-Grained Algorithm Design and Engineering

• Teaching Team: Sebastian Angrick, Geri Gokaj
• Language: English
• Number of students: At most 8
• First meeting: Friday, 31.10.2025, 09:45; Building 50.34 Room 236
• Registration: Send an email to: sebastian.angrick@kit.edu or geri.gokaj@kit.edu

You are welcome to join the first meeting even if you are not yet registered and only want to learn more about the course. Please send us a mail beforehand if you cannot make it but still want to take the course.

introduction-print.pdf

This course offers the opportunity to design and engineer practically fast solvers for selected algorithmic problems in the setting of an algorithmic challenge.

Algorithmic challenges lie at the intersection of theoretical and practical algorithm research. Given a well-defined problem, contestants have a several months to develop a solver for the stated problem. The solver is subsequently evaluated on secret instances and scored by runtime and/or quality of produced solutions.

In this course, students will receive a topic among a list of possible algorithmic problems with relevance for fine-grained and parameterized complexity (usually from the fields of graph theory, computational geometry or string problems). The topics are often inspired from current algorithmic challenges (e.g., the PACE challenge or CG:SHOP competition), providing an opportunity of participation as part of the course.

Under supervision, each group will:

• research the theoretical state-of-the-art for their algorithmic problem and/or design a novel algorithm,
• implement one or more algorithmic approaches
• evaluate and improve them using appropriate benchmark data sets.

The course aims to investigate the connections between worst-case upper & conditional lower bounds and fast practical implementations.

While we do not expect you to actually participate in any challenges, we encourage you doing so and will assist you with the submission.

6 CP correspond to ~180 h, distributed roughly as follows:

• about 40 h meetings, literature review, etc.
• about 100 h implementation and evaluation
• about 40 h preparation of presentation and report

Students should be able to apply knowledge in the specializations “Algorithmtechnik” and “Theoretische Grundlagen” to derive fast algorithms and their implementations for a given algorithmic problem.

This includes:

• modeling a given problem of interest as a well-defined algorithmic problem as well as identification of reasonable relaxations
• performing a literature search to identify algorithmic ideas previously proposed for a given problem
• researching a given algorithmic or conditional lower bound technique and investigating its applicability on a given problem
• implementing resulting algorithms efficiently
• creating reasonable benchmark data sets (generated randomly, via reductions or from real-world data sources)
• evaluating an implementation on benchmark data and gaining insights on possible improvements of the model, algorithm, or implementation.

Furthermore, the students can constructively engage in a team setting and are able to clearly communicate their ideas and results.

The assessment is carried out as an examination of another type (§ 4 Abs. 2 No. 3 SPO). The overall impression is evaluated. The following partial aspects are included in the grading: Project report and presentation. Students may redraw from the examination during the first two weeks after the topic has been communicated. The assessment can be repeated once.

• Basic knowledge of theoretical computer science and algorithm design is strongly recommended.
• Knowledge of parameterized algorithms or fine-grained complexity is helpful, but not required.