This course is taught in English.
Description
There are many computational problems for which theoretically efficient algorithms are known, but those do not work well for practical applications "in the wild", because, e.g., the problems are too abstracted, the algorithms do not take into account the specifics of real-life data, or their analysis hides large constants in their actual run time. Since the adoption of theoretical algorithms 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 algorithm theory and practice. In the course of this seminar you will seek insights into those algorithms which you then harness to narrow that gap by implementing fundamental algorithmic primitives efficiently and in an accessible, contemporary fashion using modern programming languages such as C++, Rust, or Python. You will deploy the methods of Algorithm Engineering to expedite the algorithms behind real-world use cases in, e.g., traffic routing, matching markets, and task scheduling.
Tasks
The seminar offers five topics of real-world algorithm applications. Each topic will be covered by two students, who will design and implement a library solving their problem based on existing algorithm descriptions in the literature. At the end of the seminar, each student team will present their library, demonstrating its performance on a real-life data set, and submit a documentation detailing their work. Fulfilling the deliverables will give 3 ECTS points, corresponding to 90 hours per student.
Requirements
We are looking for students with an interest in theoretical computer science and applied algorithm design. The topics offered require knowledge from at least two of (i) algorithm design and analysis, (ii) data structures, (iii) complexity theory, and (iv) graph theory. Solid programming skills in C++, Rust or Python are essential to achieve actual gains over existing implementations. The seminar is open to students in CS, DS, IIW, and TM.
