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