Algorithm Engineering (WS 2016/2017)

Lecture

Prof. Dr. Ulrich Meyer

Tuesdays 10:00 - 12:00
Thursdays 10:00 - 12:00
SR 11 (R-M-S 11-15)

QIS: AE, AE1, AE2

Tutorials

Manuel Penschuck

Friday, 14:00 - 16:00
SR 11 (R-M-S 11-15)

Organisation of tutorials

We will issue problem sheets weekly on Tuesday; you have one week to complete the assignments and hand them in before Tuesday’s lecture. The solutions will then be discussed in the following tutorial, but there will be no sample solution. We will return your submission after we received your self-assessment - So keep a copy of your solutions.

You are asked to mark your own answers based on the discussions in the tutorial: Just include the points of problem sheet i with the solutions you hand in for assignment i+1. If this is not possible, please write a mail to Manuel. We will mark an arbitrary subset of solutions ourself and compare them to self-assessments. If there are systematic discrepancies we will counteract by scaling all self-assigned points of that student. In case of abuse (e.g., marking or plagiarism), all past and future points can be annulled.

Language

The lecture is held in English.
You can solve the assignments in German or in English.

Content

Algorithm engineering applies development cycles with a close coupling of design, analysis, implementation, and experimental evaluation in order to narrow the gap between theory and practice. A subset of the following topics will be covered in the lecture:

  • Realistic input models including average-case complexity and smoothed analysis.
  • Realistic machine models (e.g., memory hierarchies).
  • Heuristics and experimental evaluation.
  • Robustness, e.g., certifying algorithms, exact arithmetic.
  • Case studies and algorithm libraries.

Exams

There will be a written exam of 90 min (AE1 only, 5CP) or 180 min (AE1+AE2, M-AE1 8/10CP).
Date: 10.04.2017, 8:30
Location: Magnus (Bockenheim), may change: Please check again!
Aids: None (We decided to not allow hand-written notes in favour of simpler questions)
Please, turn off all electrical devices (esp. mobile phones and smart watches) during the exam and do not carry them on you (put them in your bag).

Materials

Lecture notes and extra material

Assignments