Master Course in Summer 2020
03-ME-602.99c, 6 ETCS points
A key assumption of all basic algorithm design classes is that all the data is fully accessible at the start of the computation.
However, from the point of view of many real-world applications of computer science (such as the stock market, cloud scheduling, network design), this assumption is simply not true. In the above examples, our knowledge of the current data is only partial or based on historical estimates.
The class Algorithms and Uncertainty will teach students about the most common models of such uncertain data and how to design and analyze efficient algorithms in these models.
Specifically, we will cover the theory of online algorithms, where the input arrives without any prior information (such as network packets arriving to a router) and also needs to be processed immediately, before the next piece of input arrives. This model is best suited for analyzing critical networking and scheduling systems where devices and algorithms must perform well even in the worst-case scenario.
In the cases where previous history can be used to model the upcoming data, we often employ stochastic optimization. There, the algorithms work with the assumption that data is drawn from some probability distribution known ahead of time.
Nowadays, another source of information is often available: machine learning algorithms can generate predictions which are accurate most of the time. However, there is no guarantee on the quality of the prediction, as the current instance may not be covered by the training set. This statement motivated a very recent research domain that will be covered in this course: how to use untrusted predictions in order to improve guaranteed algorithms.
The course will be taught in English. The course is accessible to any student with basic algorithm classes and basic knowledge of graph theory.
Dr. Martin Böhm
Prof. Dr. Nicole Megow
Dr. Bertrand Simon
Stud-IP Link: Algorithms and Uncertainty
First lecture: Lecture times and location will be specified in April (The summer semester starts on April 14.)