Advanced Algorithms (in English)

Lecturer: Prof. Dr. Christian Scheideler

Module information:

• 6 ECTS Credits

For those students that just want to take the 4 ECTS variant of the course: only the contents taught till the June 22 will be relevant for the exam. Please inform the lecturer if you want to make use of this option.

Time and Location:

• Lectures: Fr 11-14, F1.110
• Tutorials: Fr 14-16, F1.110

On July 6, the tutorial will not take place, but the lecture will take place.

Examination:

To be announced. There might be a written exam if by the end of May there are still more than 30 attendees, but the default would be an oral exam.

Contents:

The course will cover advanced topics on randomized algorithms.

• Chapter 1: Introduction
• Chapter 2: Introductory Examples
• Chapter 3: Online Algorithms
• Chapter 4: Randomized Rounding
• Chapter 5: Probability Amplification
• Chapter 6: Randomized Metric Reduction
• Chapter 7: Lowdimensional Optimization
• Chapter 8: Approximate Counting

Homework assignments:

• Assignment 1 (due April 20)
• Assignment 2 (due April 27)
• Assignment 3 (due May 4)
• Assignment 4 (due May 11)
• Assignment 5 (due May 18)
• Assignment 6 (due May 25)
• Assignment 7 (due June 1)
• Assignment 8 (due June 15)
• Assignment 9 (due June 29)
• Assignment 10 (due June 13)

A bonus of 0.3 points can be obtained if a solution to a homework problem is presented in one of the tutorials. The bonus only applies if the exam is passed.