This course was previously offered in the winter term 2022/23. It will be offered again in the summer term 2023.
There are many computational problems for which good algorithms are known in theory, but no good implementations for them are known. Since the adoption of many theoretical results into practice requires the availability of fast and easy-to-use solvers for basic problems such as graph decomposition tasks, a considerable gap has developed between theory and practice. In the course of this seminar we will attempt to give a deeper insight into the work necessary to close that gap by implementing some of these fundamental algorithmic primitives efficiently and in an accessible, contemporary fashion using modern programming languages such as C++, Rust, or Python.
We are looking for students with an interest in theoretical computer science and applied algorithm design. Some of the topics to be discussed might be fairly technical and experience with graph theory, algorithm analysis, and complexity theory will be beneficial. However, the range of topics is quite wide, so a lack of background in some of these topics should not be an obstacle. The seminar is open to students in CS, DS, IIW, and TM. The initial meeting will be held on the 11.04, attendance is mandatory.
The seminar will comprise up to 10 implementation tasks, depending on the number of participants. Each task will be covered by one student, who will design and implement a small library solving their assigned problem based on some existing algorithm description in the literature. At the end of the seminar, each student will give a short 20 minute presentation on their library, as well as submit a brief 2-3 page documentation detailing their work.