Algorithm Engineering

March 2005

Instructors: Kurt Mehlhorn, Lutz Kettner, and Uli Meyer

Content

The design and analysis of algorithms is a standard topic of most computer science curricula. Algorithms are typically formulated in pseudo-code or mathematical language and are intended for humans. Programs are formulated in programming languages and are intended for execution by machines. The transition from an algorithm to an efficient and correct program is non-trivial and error-prone. Algorithm Engineering treats programs as first-class citizens. In the course, we cover the following topics: efficiency and optimization of programs, certifying algorithms, implementing geometric algorithms, non-von-Neumann architectures, and ibrary design.

The course is intended for master and PhD-students. I assume knowledge in the design and analysis of algorithms. (as taught in Entwurf und Analyse von Algorithmen in KL and in Algorithms and Data Structures in SB).

Exam

• The examination is oral, duration 30 minutes
• dates: May 19th (Thursday) or May 20th (Friday). The exams in KL will take place on either Thursday or Friday afternoon. In exceptional cases, other times are possible.
• contact: Please contact Ingrid Finkler (infi@mpi-sb.mpg.de, 0681-9325-100, 9:30 -- 12:00)) to sign up for the exam. Indicate your availability. Ingrid will then schedule the exams.

Mailing List

http://lists.unix-ag.uni-kl.de/mailman/listinfo/algen
you can sign up for the mailing list of the course.

Course Material:

• LEDA Book: all chapters of the LEDA book can be downloaded from the homepage. Of course, I would prefer if you would buy the book.

• Certifying Algorithms: this is a survey paper on certifying algorithms.

• Slides for Lectures: Some of the Theory Behind LEDA gives an overview.
• Certifying Algorithms I, Certifying Algorithms II, Certifying Algorithms III discuss certifying algorithms. The paper above is also useful.
• Examples of Non-Robustness in Geometric Computations (and the underlying paper) gives examples on what can go wrong when geometric algorithms are implemented with floating point arithmetic.
• The exact computation paradigm is a general approach to robust geometric computation: it simply asks to evaluate geometric predicates without error. The main technique is exact arithmetic (bigints, rational, ...). Floating point filters add the required speed. Floating point filters are discussed in Section 9.7 of the LEDAbook. A somewhat simplified write-up of the main result can be found here. The write-up assumes some knowledge of Section 9.7. And the corresponding slides are here.
• Controlled Perturbation: the slides and the paper.
• External Memory Computation: Slides
• Algorithm Engineering Guest Lecture by Peter Sanders: Slides Part 1 and Slides Part 2.
• Algorithm Library Design: Slides Part 1, C++ and STL, and Slides Part 2, CGAL.

Exercises:

Sheet 1,  Sheet 2,  Sheet 3,  Sheet 4

Organization and Dates

The language of instruction is English.

We will teach the course in March 2005. The course will be taught alternatingly in Kaiserslautern and Saarbrücken and transmitted to the other site by video-conferencing. There will be six hours of lectures every week, three hours in KL and three hours in SB. In addition, there will be a two hour lab session at each siteevery week. We have lectures from 10am to 11:30am and from 12pm to 12:45pm. The lab session is from 1:30pm to 2:30pm. There will be a total of 30 lectures.

Location

The lectures take place in room 32/349 in KL and in room 024, Max-Planck-Institut für Informatik, in SB, i.e., the lecture either takes place in this room or is transmitted by video into this room.

Credit Hours

For students in KL the course has 2+1 SWS credit hours, for students in SB the course has 5 credit hours. There is the possibility of an exam at the end of the course for the students who want graded credit hours.