Estonian Winter Schools in Computer Science    
Eesti arvutiteaduse talvekoolid
EWSCS 2005
EATTK 2005

10th Estonian Winter School in Computer Science (EWSCS)
X Eesti Arvutiteaduse Talvekool

Palmse, Estonia, February 27 - March 4, 2005

under the auspices of European Educational Forum

Kurt Mehlhorn

Algorithms and Complexity Group
Max-Planck-Institut für Informatik, Saarbrücken

Implementing Algorithms


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.

How do we go from a correct algorithm to a correct program?

The background for my lectures is the experience with LEDA, CGAL, and EXACUS, three algorithm library projects I was involved with.

In the first main part, I discuss certifying algorithms. Certifying algorithms return not only the value they are supposed to compute but also a witness (certificate) which allows the user of the algorithm to convince itself of the correctness of the value returned. I give examples of certifying algorithms and discuss the limits of certification.

In the second main part, I discuss the implementation of geometric algorithms. Their implementation 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.

Course materials

About the Lecturer


Modified Mar 09, 2005 15:43 by monika(at)