Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Modern Algorithm Theory

Purpose

For a successful Master's Thesis as a research level work, a student needs the following three ingredients.

  1. Knowledge of the field.
  2. Ability to solve problems in uncertain and changing environments.
  3. Ability to analyze and understand the relevant literature.

The first ingredient is taught in lectures; the second in project seminars and bachelor/master projects. The third is covered by seminars. In this seminar the students can chose from a wide variety of topics offered by various members of the group. Each topic comes with a small number of papers (typically one) which then have to be read, understood and presented.

Requirements

There are no formal requirements for taking this seminar. You should be comfortable with reading and understanding also elaborate proofs (any lecture offered by the Algorithm Engeneering group covers this).

Structure of the Seminar

We meet weekly on Mondays at 15:15h in H-2.57. In the first meeting on October 15 we will offer an overview over the course covering the different topics. Later weeks without presentation will be skipped.

At the first meeting, each interested student can chose a topic to present about and a date for presentation. Each student prepares the following three items.

  1. An 80-minutes lecture on her topic, where half the time introduces the material and the other half is reserved for exercises for the other participants.
  2. A one-page handout/summary of the talk, which is provided to all other participants at the beginning of the lecture.
  3. A summary of 3-5 pages of all details presented, submitted to the advisor of the talk, due two weeks after the presentation.

Two weeks before the presentation of a topic there is a personal meeting with the advisor for the topic in order to clarify any questions (including regarding the material) and for discussing a possible structure for the talk. At another meeting about one week before the presentation a first draft of the talk can be discussed with the advisor. After the talk there will be a feedback meeting with the advisor. Two weeks after the talk the written summary is due.

A preliminary grade is assigned based on the oral presentation and the handout. The written summary can change this grade a little.

Topics

The topics include

  • Parameterized Complexity Analysis;
  • Counting Complexity;
  • Game Theory;
  • Drift Theory;
  • Network Theory;
  • Graph Drawing;
  • Approximation Algorithms;
  • Randomized Algorithms and Processes.