Dozent: Dr. Davis Issac, Dr. Kirill Simonov, Aikaterini Niklavotis, Dr. Sarel Cohen
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

As the name suggests, we plan to build a team that takes part in the 2023 PACE-Challenge. This competition is held every year by the Parameterized Algorithms community, and the task is always to create fast algorithms for an NP-hard (usually graph) problem.  The problem of  the 2023 challenge is to compute  the twinwidth of a graph, a graph-width parameter that has been studied prominently in the recent times. The challenge consists of an Exact track as well as a heuristic track, that will be ranked seperately.

The PACE contest is not so much about (fast) coding as it is about developing new algorithmic approaches for a notoriously hard problem over many months. Aiming for exact solutions will require theoretical proof that our solver works correctly. A good PACE-participation is therefore usually followed by a scientific publication about the theoretical properties discovered while working towards the contest. 

The submission of the final code is in June 2023. So we plan to offer a second project seminar in Summer Semester 2023 as a continuation of this one. However, it does not mean that you have to join the course next semester. You are free to leave the team after one semester.

The initial few weeks of the current course will be about reading the results about twinwidth and presenting them for the whole team. Then, by December we will aim to start with our first implemenation for the challenge. At the end of the semester you will be required to submit a writeup describing the current state of the implementation(s), the bottlenecks faced, and potential further ideas to strengthen the implementation(s).

We were successfull in last year's PACE challenge (PACE 2022) by securing third place in the exact track, so let us continue the tradition.

We will meet once every week. We will also have a dedicated slack channel for the course for further communication. We can switch between in-person (with hybrid options) and zoom meetings as required. For example for the initial reading and presentation, it might be better to have in-person meetings.

We will have our first meeting on Monday, 24th October at 2 p.m at K-1.03 with also zoom option. 

Join Zoom Meeting
https://uni-potsdam.zoom.us/j/69242831713Meeting ID: 692 4283 1713
Passcode: 44450680

There are no formal requirements. We expect some coding skills and at least a basic understanding of graphs and algorithms.

The grading for the course will be based on the presentations during the reading phase (30%), state of the implementation at the end of the semester (50%), and the writeup (20%).