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.