max planck institut
informatik

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

Register for

Lecturers:
Tutors:

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.

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)
• 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.