Aktuelle Themen in Algorithmen für große Datenmengen 1+2:
Optimization and Uncertainty (Summer 2021)
Topical
- Logbook with detailed information about schedule and content.
- Part I ends with Lecture 14. Part II starts with Lecture 15.
Organization
- Lecturer: Prof. Dr. Martin Hoefer
- Exercises: Tim Koglin, Lisa Wilhelmi
- LSF Entries: Part 1, Part 2, Complete course
- Lectures: Videos (recorded Tue/Thu)
- Exercises: Fridays, 12:15 - 13:45h, live via Zoom
Material
Lecture Notes
Current update: 8 July 2021 (restricted access).
Videos
Videos are available here. (restricted access)
Unlock Features: Click "play" on the video and then "pop-out" (lower right). This opens a separate window with the same video, in which you can see annotations, scroll in the timeline, and speed up/down the video.
Exercises
Each assignment is published on Tuesday and is due the following Tuesday at 10:00h. Your solutions have to be submitted as one PDF-file via e-mail to Lisa Wilhelmi. Exercise sessions are scheduled on Friday 12:15 - 13:45h via Zoom.
Exercise Sheets
Part 1:
- Exercise Sheet 1. Issued: 20.04.2021. Due: 27.04.2021, 10:00h.
- Exercise Sheet 2. Issued: 27.04.2021. Due: 04.05.2021, 10:00h.
- Exercise Sheet 3. Issued: 04.05.2021. Due: 11.05.2021, 10:00h.
- Exercise Sheet 4. Issued: 11.05.2021. Due: 25.05.2021, 10:00h.
- Exercise Sheet 5. Issued: 25.05.2021. Due: 01.06.2021, 10:00h.
- Exercise Sheet 6. Issued: 01.06.2021. Due: 08.06.2021, 10:00h.
Part 2:
- Exercise Sheet 7. Issued: 08.06.2021. Due: 22.06.2021, 10:00h.
- Exercise Sheet 8. Issued: 22.06.2021. Due: 29.06.2021, 10:00h.
- Exercise Sheet 9. Issued: 29.06.2021. Due: 06.07.2021, 10:00h.
- Exercise Sheet 10. Issued: 06.07.2021. Due: 13.07.2021, 10:00h.
Topic
Suppose you go on a sequence of n dates, after each of which you have to decide if you want to start a relationship or see more people - when is the best time to stop dating to get the best partner? Optimization problems of this type arise frequently in modern computer systems. Often large data sets can be used to infer probabilistic information about the expected benefit of the potential decisions. The course gives an introduction to algorithmic techniques for solving optimization problems with uncertainty. We will start with classic stopping problems as the one sketeched above (i.e., secretary and prophet-inequality problems) and advance to more general online optimization problems in which the input is partly stochastic and partly adversarial. Futher topics of interest are recent developments in online learning, Markov decision processes, testing and probing problems, as well as applications of these techniques in distributed systems and markets.
Literature
- Will be provided during the course.