This course is taught in English. This course will next be offered in the winter term 2022/2023.
Link to official course page
Description
This course provides an introduction to Algorithm Engineering, a field which combines Algorithm Theory and Experimental Algorithmics. The course will cover the key concepts of Algorithm Engineering including modelling of complex problems, algorithm design, analysis of algorithms, implementation techniques and experimental methodology. More specifically, the course will cover the best practical methods to solve classical combinatorial optimisation problems, such as linear/integer programming, SAT, Maximum Independent Set, etc. It will also introduce software tools (e.g. ortools, Gurobi) and libraries (e.g. LEDA) used in practice to solve those optimisation problems.
ECTS-points: 6
Learning goals
In this course you will learn:
- How to provide a robust and efficient implementation of a “pencil-and-paper” algorithm.
- How to empirically analyse and predict the performance of an implemented algorithm.
- How to design experimental evaluation to measure the runtime, the accuracy, and the main properties of the implemented algorithm.
Setup
Weekly lectures (Thursday 9:45-11:15 in room M-2589) and weekly exercise sessions (Friday 8:00-9:30 in room D-0.013)
Recommended Literature
- Matthias Müller-Hannemann and Stefan Schirra (Eds.), Algorithm Engineering: Bridging the Gap between Algorithm Theory and Practice, Springer, Latest edition
- A Theoretician’s Guide to the Experimental Analysis of Algorithms, David S. Johnson
