Kurth Melhorn, Max Plank Institute, Saarbrucken, Germany

The Science behind LEDA and CGAL
Algorithms are problem solving recipes intended for humans; they are usually expressed in a mixture of natural language, mathematical notation, and programming notation. In contrast, programs are intended for machine execution; they are expressed in a programming language.

Algorithmicists design algorithms. The success criteria are correctness, elegance, and small asymptotic running time.

Applications need programs. The success criteria are correctness, versatility, fit into an environment, and actual running time on actual instances.

I will discuss the relationship of algorithms and programs along three axes:

How do we go from a correct algorithm to a correct program? Programming is an error-prone task and it is a highly non-trivial task to convert a correct algorithm into a correct program. We advocate certifying programs as a pragmatic approach to program correctness. On an input x, a certifying algorithm for a function f does not only return y, the alleged function value f(x), but also a certificate (proof, convincing evidence) of the equality ``y = f(x)''. In this way, a user of the program can convince himself that the program worked correctly on the given input x.

The correct implementation of geometric algorithms is particularly difficult, because geometric algorithms are usually designed for inputs in general position and for the Real-RAM model of computation. I give examples, how miserably naive implementations can fail, show how to realize a Real-RAM as needed for computational geometry, discuss approaches to overcome the general position problem, and finally come to exact algorithms for curves and surfaces.

Algorithm engineering is the scientific approach to making algorithms and the corresponding programs fast. It will be the subject of my third lecture.

The background for my lectures is the experience with LEDA, CGAL, and EXACUS.
More information about my lectures can be found at http://www.mpi-inf.mpg.de/~mehlhorn/Lipari2008/Overview.html