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.
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.
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)
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