- 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: at 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 will 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.

- The language of instruction is English.

- Organization and Dates: We will teach the course in March 2005.
The course will be taught alternatingly in Kaiserslautern and
Saarbr\"ucken 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.

Kaiserslautern |
Saarbrücken |

Monday, March 7 |
Friday, March 11 |

Monday, March 14 |
Friday, March 18 |

Monday, March 21 |
Thursday, March 24 |

Tuesday, March 29 |
Friday, April 1 |

Monday, April 4 |
Friday, April 8 |

- Location: The lectures take place in room 32/349 in KL and in
room 024, Max-Planck-Institut fürr 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.