Microcredential mCOSIB – Algorithm Engineering

Theoretical (worst case) runtimes of algorithms often do not explain their be-havior in practice sufficiently. The input data, the hardware architecture, hidden constants and many other factors influence empirical runtimes. Algorithm Engi-neering tries to bridge this gap between theory and practice. The goal is to design algorithms which work well on real-world data, are simple and easy to implement and take the used hardware into account (e.g. provide good data locality). In the lecture, we will discuss AE approaches for several important applications as sorting, graph partitioning/clustering, route planning and NP-hard problems as TSP, Independent Set and Colouring. We will compare dif-ferent algorithms on real-world benchmarks, try to identify 'hard inputs' and discuss performance measures which can be compared in a hardware-independent way. For full details, please visit the detailed information page.