Algorithm Design In Uncertainty

• Lec 1 (10/11) - Course Motivation: The Online Setup, Models of Uncertainty [Kes20]

• Lec 2 (24/11) - Probability Refresher [BK22]

• Lec 3 (1/12) - The Paging Problem [BK22]

• Lec 4 (8/12) - Design Techniques: Greedy Algorithms, Doubling Trick [BK22]

• Lec 5 (22/12) - Randomized Algorithms: Power of Randomization, Optimal Online Algorithms [BP19, BK22]

• Lec 6 (29/12) - Limits of Randomization: Yao's Minimax Principle and Applications [BP19, Kes20, BK22]

References

[BP19]  Online Algorithms by Allan Bordin and Denis Pankratov

[Kes20] Course on Algorithms and Uncertainty by Thomas Kesselheim

[BK22]  Course on Algorithm Design Under Uncertainty by Siddharth Barman and Arindam Khan in Fall 2022 at IISc