This module is taught in English. This module is regularly taught every winter term.
This module was previously offered in the winter term 2022/2023.
Link to official module page
Description
This module provides an introduction to algorithm engineering, a field which combines algorithm theory and experimental algorithmics. One of its key goals is to bridge the observed gap between theoretically predicted and epxerimentally observed run times of algorithms. It achieves this goal by transforming pencil-and-paper algorithms (or textbook algorithms in pseudo-code) to practically efficient, robust and well-documented implementations of these algorithms, together with extensive experimentation on benchmark and real-life data sets.
Recommended prerequisites
We expect attendees to be proficient in the material from the following modules:
- Algorithms and data structures
- Discrete algebraic structures
- Mathematics I
- Mathematics II
We further recommend basic knowledge of the following topics:
- Probability theory (probability spaces, expected value)
- Programming in Python, C++, C# or Java
Learning goals
In this module you will learn
- how to provide a robust and efficient implementation of “pencil-and-paper” algorithms,
- 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.
Topics
- modelling process of computational problems through common frameworks such as SAT and integer programming
- fundamental aspects of algorithm design, including methods used to solve the above
mentioned problems - methods for analysing the performance of an algorithm both experimentally and using reality-inspired models of computation
techniques to efficiently implement algorithms - methods to verify the correctness of implementations
- practices to efficiently handle the application engineering process by software tools (e.g., ortools, Gurobi) and libraries (e.g., LEDA)
Setup
- Weekly lectures (in presence) and weekly tutorial session (in presence).
- Each week an assignment is handed out, which should be solved individually outside the classroom and then be submitted for grading. The assignment and its solutions are then discussed in the subsequent tutorial session. If sufficiently many points are awarded in the grading process (cumulative over all assignments of the term), then a bonus is given for the final exam at the end of the term.
- Final exam (written) for 90 minutes at the end of the term, whose outcome (together with a potential bonus from the assignment) determines the final grade for the module.
Overall module load: 6 ECTS credit points
Recommended literature
- Matthias Müller-Hannemann and Stefan Schirra (Eds.), Algorithm Engineering: Bridging the Gap between Algorithm Theory and Practice, Springer, Latest edition
- David S. Johnson: A Theoretician’s Guide to the Experimental Analysis of Algorithms
