Prof. Dr. Tobias Friedrich

Algorithmic Hits of the 80s and 90s (Winter Term 2016/2017)


While Algorithm Engineering today is a fast moving research field covered by thousands of papers every year, there are also some notable classical results. Most of these breakthroughs date back to the 1980s and 1990s, a time which can in hindsight be labeled as the dawn of modern Algorithmics. Fueled by the vast spread of digital hardware, but also drawing on the unique historic situation accrued by the break-up of the Soviet Union and the resulting internationalization of the Computer Science community, these two decades mark the foundation of Algorithm Engineering as we know it.

This seminar considers algorithmic "hits" that are typically not captured in basic algorithm courses, but have some mathematical beauty. The goal is for the students to be able to read a scientific paper, understand its content and historical significance, and then present these findings to their peers.


There are no formal requirements.

Participants should bring good mathematical skills - most papers will be fairly technical and contain mathematical proofs - as well as the ability to give a good presentation.

The language of this course is English.


At the beginning of the semester each student has to choose one paper from a prescribed list. The paper is then to be presented in a scientific talk and afterwards summarized in writing. For more details see also paragraph Examination.

Most of the work will be done by the student in a self-organized fashion. Each student will, however, receive an advisor from the Algorithm Engineering group whom he or she can consult for questions about the paper, the presentation, and the summary.


Each student is required to give a presentation on his or her topic about 2-3 months into the semester. The presentation should be between 30-40 minutes long.

Additionally, every student must write a summary of the paper of 3-5 pages, in which he or she also points out its historical significance. The latter need not to be too extensive, but should show that the student gained a reasonable grasp on the paper's importance and the research it preceded.


The full list of papers to choose from will be available in the Algorithm Engineering Moodle. Your login credentials are the same as your HPI login.

Besides background literature on your personal topic, we strongly recommend to consult at least one book on how to deliver good presentations since this is a skill computer science students are often lacking. We recommend e.g.

  • Garr Reynolds, Presentation Zen

Dates and Location

The kickoff meeting will be held on Monday October 24 1.30 p.m. in room A-2.2. Note that this is in the second week of lectures.

Check also the Moodle for up-to-date information.