Algorithm Engineering

Algorithm Engineering has recently emerged as an interesting field of research. Traditionally, an algorithm is regarded efficient whenever its running time is polynomial in its input size (polynomial-time algorithm). Furthermore, when speaking about running times of algorithms, we tend to speak in terms of O-notation — which not only ignores lower-degree terms, but also ignores the constants preceding the terms. This situations tend to produce certain degree of doubt among practitioners as they cannot be sure whether a (theoretical) algorithm is usable at all in practice. This discrepancy produces a gap between theory and practice that Algorithm Engineering tries to bridge by designing algorithms that indeed exhibit fast execution times, but for which theoretical guarantees regarding performance can be proven. That is, Algorithm Engineering lives at the amazing intersection between Theoretical and Practical Computer Science.

In this course we will cover topics regarding:

1. Sorting
2. Hash tables
3. Tree-based searching data structures
4. Geometric optimization
5. Shortest paths in graphs
6. Geometric algorithms

• Kurt Mehlhorn and Peter Sanders: Algorithms and Data Structures: The Basic Toolbox.
• Matthias Müller-Hanneman and Stefan Schirra: Algorithm Engineering: Bridging the Gap Between Algorithm Theory and Practice.

General Information

• Schedule of all lectures, tutorials, and home assignments: PDF [06.04.2016]
• There is a mailinglist. We will distribute the homework sets and other announcements via this list, so, please subscribe!