CIDEC    
ÜIK
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
Germany

Implementing Algorithms

Abstract

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

URL: http://www.mpi-sb.mpg.de/~mehlhorn

http://www.cs.ioc.ee/yik/schools/win2005/

Modified Mar 09, 2005 15:43 by monika(at)cs.ioc.ee