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.
In order to participate in the exercise classes, you are required to register in the OLAT system.
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 are organized by Sebastian.
Sheet 7 can be handed in until Tuesday, 10.06., 12am. as the Monday is a holiday.
(Due to technical problems, the first lecture was only partially recorded. Therefore, we additionally provide the notes from the last iteration.)
Lecture notes covering all course material are available in print; ask us for it!
Apart from the lecture notes, the following text books cover parts of the course's content (and much more interesting stuff!):
- R. Sedgewick, P. Flajolet: An Introduction to the Analysis of Algorithms
Addison-Wesley Professional, 2nd edition, 2013
- D. Knuth: The Art of Computer Programming: Fundamental Algorithms
Addison-Wesley, 3rd edition, 1997
- D. Knuth: The Art of Computer Programming: Searching and Sorting
Addison-Wesley, 3rd edition, 1998
- P. Flajolet, R. Sedgewick: Analytic Combinatorics
Cambridge University Press, 2009