Algorithm Engineering (SS 12)
In theory, there is no difference between theory and practice. In practice, there is.

the course wiki
the course mailing list

Additional ressources can be found in the password protected section

Lecturers:

Eric Berberich, Pawel Gawrychowski, and Kurt Mehlhorn

Tutors:

Tomasz, Claudio, and Adrian

Time and Room:

Monday, 16:00 -- 18:00, Building E1 3 - Lecture Hall III (0.03.1)

Thursday, 10:00 -- 12:00, Building E1 3 - Lecture Hall III (0.03.1)

First Lecture on Monday, April 23rd

Exercises: Mo 10-12 (E1.4 R021), Fr 16-18 (E1.4 R023)

Exam: 30.7. 12:00-14:00 HS002 E1.3, Re-Exam: 24.9. 12:00-14:00 HSII E2.5

Overview

Algorithm engineering is a discipline at the intersection of theory and practice. Theoretical computer science supplies us with a rich set of algorithms and data structures that, in principle, enable us to solve complex problems in the real world. It designs algorithms (not!!! programs) for Random Access Machines, a vintage 1950 computer, and analyzes their resource requirements on worst case or average case data.

Algorithm Engineering addresses these issues. It develops more realistic machine models, in particular memory hierarchy, caches, multi-cores, clusters, and designs and analysis algorithms for them. It treats programs as first-class citizens and investigates how algorithms can be turned into reliable and efficient implementations and how these programs can be packaged into easy-to-use software libraries. It experiments with real data and investigates efficient heuristics for them.

At the heart of algorithm engineering lies an interwoven cycle of design, analysis, implementation and experiment. We will design algorithms and prove theorems about them, we will implement our algorithms and experiment with the implementations, and we will learn best practices of experimentation and library design.

More information about the course, in particular about the programming project, can be found on the course wiki.

Prerequesites:

The lecture requires solid foundations in algorithms and data structures (Algorithms and Data Structures) and there will be hands-on programming projects, so experience in one or more programming languages (Programmierung I and Programmierung II) is necessary.

Course Schedule:

Introduction (KM)
Data: Street Maps and Quickest Paths (KM)
Memory Hierarchy (KM)
Multi-Core and Parallel Machines (KM)
Hadoop and Map/Reduce (PG)
Random Numbers and Randomized Algorithms (KM)
Certifying Algs (KM)
Implementation Aspects (EB)
Library Design (EB)
Experimentation (EB)
Pitfalls of floating point arithmetic (EB)
Playing with Bits and the Word-RAM (PG)
Making Graph Algs Fast (KM)
Specifications, Documentation (KM)

The material will not be covered in this order.

Literature/Links:

Geometry Algorithms Library (CGAL): Eric Berberich is one of the key developers of CGAL; Kurt Mehlhorn is one of the initiators of CGAL.
Library of Efficient Data Types and Algorithms (LEDA): Kurt Mehlhorn is one of the initiators of LEDA and he also implemented many of the programs in the library. The book about the library can be found here.
Springer Lecture Notes: Algorithm Engineering
Data Structures and Algorithms: The Basic Toolbox: Each chapter of this book has a section "Implementation Notes".
DFG Priority Programme: Algorithm Engineering (Kurt Mehlhorn is one of the initiators of this programme)
The Stony Brook Algorithm Repository

Algorithm Engineering (SS 12)In theory, there is no difference between theory and practice. In practice, there is.

Algorithm Engineering (SS 12)
In theory, there is no difference between theory and practice. In practice, there is.