Fine-grained Algorithm Design and Engineering

Each group of 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). In some cases, the proposed topic is the subject of an ongoing algorithmic contest (e.g., the PACE challenge), 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.

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 recommended.
• Knowledge of fine-grained complexity is helpful, but not required.

• Language: English
• Number of students: At most 8
• First meeting: Friday, 25.10.2024, 09:45; Building 50.34 Room 236

(You are welcome to join the first meeting even if you are not yet registered and only want to learn more about the course)

• Registration: (still open) Send an email to: mirza.redzic@kit.edu