The following two lectures were delivered as guest lecture at GWU for graduate CS class on advanced algorithms.
- Online Algorithms – Part I: February 16, 2011. Covers basics of online algorithms, competitive analysis, online job scheduling, ski rental problem, and paging algorithm
- Online Algorithms – Part II: February 23, 2011. Covers example of randomized online algorithm, lower bound against randomization, online algorithms in machine learning (weighted majority algorithms) and a construction to show that no online graph coloring algorithm can have a constant competitive ratio.