CIDEC     ÜIK Estonian Winter Schools in Computer Science     Eesti arvutiteaduse talvekoolid EWSCS 2005EATTK 2005 ## 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

• Web page for this course at MPI

• K. Mehlhorn. Certifying algorithms. Slides. [pdf]
• K. Mehlhorn. Certifying algorithms: an attempt of a theory. Slides. [pdf]
• K. Mehlhorn. Certification of data structures. Slides. [pdf]
• K. Mehlhorn et al. Classroom examples of robustness problems in geometric computations. [ppt]
• K. Mehlhorn et al. A Descartes algorithm for polynomials with approximate coefficients. Slides. [pdf]
• K. Mehlhorn et al. Conic polygons. Slides. [pdf]

• K. Mehlhorn, S. Näher, C. Uhrig. Some of the theory behind LEDA. [pdf]
• K. Mehlhorn, A. Eigenwillig, K. Kanegossi, D. Kratsch, R. McConnel, U. Meyer, J. Spinrad. Certifying algorithms.
• U. Finkler, K. Mehlhorn. Checking priority queues.
• L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, C. Yap. Classroom examples of robustness problems in geometric computations.
• E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, K. Mehlhorn, E. Schömer. A computational basis for conic arcs and Boolean operations on conic polygons.
• A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, N. Wolpert. An exact Descartes algorithm with approximate coefficients.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8804017,"math_prob":0.8585724,"size":1614,"snap":"2021-43-2021-49","text_gpt3_token_len":346,"char_repetition_ratio":0.12608695,"word_repetition_ratio":0.0,"special_character_ratio":0.1889715,"punctuation_ratio":0.12142857,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97306424,"pos_list":[0,1,2],"im_url_duplicate_count":[null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-11-30T17:21:55Z\",\"WARC-Record-ID\":\"<urn:uuid:328bbbaf-8039-4ac0-9aec-5ea076764862>\",\"Content-Length\":\"5164\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9a1564cc-3731-4f3e-be1c-475d466e9064>\",\"WARC-Concurrent-To\":\"<urn:uuid:1adb6d21-5908-41da-a4c9-08e6c9fd5ca6>\",\"WARC-IP-Address\":\"193.40.251.64\",\"WARC-Target-URI\":\"http://www.cs.ioc.ee/yik/schools/win2005/mehlhorn.php\",\"WARC-Payload-Digest\":\"sha1:UVAVYHJWUSGPUVFL3H2CJFAKR4X3P3NL\",\"WARC-Block-Digest\":\"sha1:E63TAIVEAXYSJX5NIOPWI52JYLLS3U2D\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964359065.88_warc_CC-MAIN-20211130171559-20211130201559-00613.warc.gz\"}"}