• Next semester, we will offer a seminar and a lab on topics in the area of Algorithms and Uncertainty. You will also be able to propose your own topic ideas. Please contact Thomas Kesselheim if you are interested in participating in either or both.
• There will also be the lecture Algorithmic Game Theory and the Internet, which has some similarities to this semester's lecture.

To schedule the exam, please send an e-mail to Thomas Kesselheim.

In many application scenarios, algorithms have to make decisions under some kind of uncertainty. This affects different kinds of problems. For example, when planing a route, a navigation system should take into consideration the traffic. Also, any machine-learning problem is about some kind of uncertainty. A random sample of data is used as a representative for the entire world.

In this course, we will get to know different techniques to model uncertainty and what approaches algorithms can use to cope with it. We will cover topics such as

• Online Algorithms
• Online Learning Algorithms and Online Convex Optimization
• Sample Complexity
• Markov Decisions Processes
• Stochastic and Robust Optimization

You should bring a solid background in algorithms, calculus, and probability theory. Specialized knowledge about certain algorithms is not necessary.

• Lecture Notes Oct 9, 2018 (Ski Rental)
• Lecture Notes Oct 11, 2018 (Online Set Cover 1)
• Lecture Notes Oct 16, 2018 (Online Set Cover 2)
• Lecture Notes Oct 23, 2018 (Online Set Cover 3)
• Lecture Notes Oct 25, 2018 (Yao's Principle)
• Lecture Notes Oct 30, 2018 (Markov Decision Processes) (change of indices in comparison to lecture, hopefully less confusing now)
• Lecture Notes Nov 6, 2018 (Optimal Stopping)
• Lecture Notes Nov 8, 2018 (Adaptivity Gap)
• Lecture Notes Nov 13, 2018 (Stochastic Vertex Cover)
• Lecture Notes Nov 15, 2018 (Stochastic Set Cover)
• Lecture Notes Nov 20, 2018 (Stochastic Steiner Tree)
• Lecture Notes Nov 22, 2018 (Demand-Robust Optimization) (changed the exposition in the proof of key lemma; the definitions are equivalent)
• Lecture Notes Nov 27, 2018 (Markov Decision Processes with Infinite Time Horizon)
• Lecture Notes Nov 29, 2018 (Gittins Index Theorem)
• Lecture Notes Dec 4, 2018 (Stochastic Multi-Armed Bandits)
• Lecture Notes Dec 6, 2018 (No-Regret Learning: Experts)
• Lecture Notes Dec 11, 2018 (No-Regret Learning: Bandits 1)
• Lecture Notes Dec 13, 2018 (No-Regret Learning: Bandits 2)
• Lecture Notes Dec 18, 2018 (Basics of Online Convex Optimization 1)
• Lecture Notes Dec 20, 2018 (Basics of Online Convex Optimization 2) (Update Jan 8: Changed Section 4)
• Lecture Notes Jan 8, 2019 (PAC Learning)
• Lecture Notes Jan 10, 2019 (VC Dimension)
• Lecture Notes Jan 15, 2019 (Agnostic PAC Learning)
• Lecture Notes Jan 17, 2019 (Boosting)
• Lecture Notes Jan 22, 2019 (Efficient Empirical Risk Minimization)
• Lecture Notes Jan 24, 2019 (Overfitting, Stability, and Regularization)
• Lecture Notes Jan 29, 2019 (Max-Flow via Experts)
• Lecture Notes Jan 31, 2019 (No-Regret Learning and Zero-Sum Games)

• Exercise Set 1, due October 23
• Exercise Set 2, due November 6
• Exercise Set 3, due November 13 (updated Nov 8: Added a missing negation)
• Exercise Set 4, due November 20 (updated Nov 15: Changed Exercise 2)
• Exercise Set 5, due November 27 (updated Nov 22: Changes in red)
• Exercise Set 6, due December 11 (updated Dec 4: Changed labels in Exercise 2)
• Exercise Set 7, due December 18
• Exercise Set 8, due January 8
• Exercise Set 9, due January 15
• Exercise Set 10, due January 22
• Exercise Set 11, due January 29