Algorithm Engineering (SS 14)

For many problems, there are several algorithms to choose from. But how to tell which is the best for your application? Rough complexity estimates can be misleading: If constants hidden by the O-class are large, an O(n) algorithm might be much slower than an O(n log n) algorithm for any reasonable size n.

In this course, we study state of the art techniques for the analysis of algorithms for computing precise asymptotics of costs, including constant factors. We will exercise their use on practical algorithms and data structures.
Moreover, we will take additional characteristics of modern computers into account that greatly influence actual running time:

Memory hierarchies and
instruction pipelines.

Finally, we use our new knowledge on the performance of an algorithm to suggest possible optimizations, whose effects we quantify again using analysis techniques. That way, you will learn to engineer the best possible algorithm for solving your real world problem at hand.

This is an 8 ECTS advanced-level master course with accompanying tutorials; find details in the official documents.

Registration

In order to participate in the exercise classes, you are required to register in the OLAT system.

Dates

Lectures and exercise sessions will be held throughout the reading period. Individual sessions will take place weekly on

Lecture: Mondays and Wednesdays, 10:00 - 11:30 in 48-654
Exercise Class: Wednesdays, 15:30 - 17:15 in 48-654
first exercise class on 30.04.2014!

Exercises

Exercises are organized by Sebastian.
Sheet 7 can be handed in until Tuesday, 10.06., 12am. as the Monday is a holiday.

Lecture Notes

(Due to technical problems, the first lecture was only partially recorded. Therefore, we additionally provide the notes from the last iteration.)

Previous Iterations

SS 12