CS264: Beyond Worst-Case Analysis Lecture #3: Online Paging and Resource Augmentation∗

This course covers many different methods of analyzing and comparing algorithms. Periodi-cally, as in Section 2, we pause to review the “big picture ” and suggest methods for keeping tracking of the course’s main ideas, their goals, and the problems for which they are most likely to be useful. Section 3 begins our study of the online paging problem — introduced briefly in Lecture #1 — we’ll also study this problem in the next lecture. We’ll see that traditional “competitive analysis ” fails to illuminate the problem in several respects: it does not give accurate performance predictions, it does not give good guidance on how to pick a cache size, and it gives only weak information about which caching policy to use. Section 6 covers “resource augmentation, ” an alternative (but still worst-case) method of analyzing online algorithms that gives more meaningful performance guarantees. The next lecture presents an analysis that more sharply differentiates between different paging algorithms by modeling structure in data. 2 The Big Picture There is a strong analogy between the organization of this course and that of most under-graduate algorithms courses. In an undergrad course like CS161, the primary goal is to develop a toolbox for algorithm design.1 You learn that there is no “silver bullet ” — no single algorithmic idea will solve every computational problem that you’ll ever encounter. There are, however, a handful of powerful design techniques that enjoy wide applicability: divide and conquer, greedy algorithms, dynamic programming, proper use of data structures, ∗ c©2014, Tim Roughgarden