Fine-Grained Algorithm Design and Engineering

• 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.

coming soon

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.