Advanced Algorithms and Complexity

                                                               online algorithms

Instructor:   Adi Rosén 

Wednesday 12:45-15:45  (October-November 2009)

       Lectures 

• 14/10  - motivation ; introduction to competitive analysis;
               paging - deterministic upper bounds, lower bound (via the k-server problem)
                              randomized algorithms for paging
  
• 21/10  - Metrical Task Systems: traversal algorithms; the Work Function Algorithm; randomized algorithms
• 28/10  - The k-server problem: algorithm for trees; the Work Function Algorithm
• 4/11  - Adversaries against randomized online algorithms and their relative pover; online computation with advice

Assignments