Problem
Consider the page caching problem where the memory cache can hold m pages, and we are given a sequence P of n requests taken from a pool of m + 1 possible pages. Describe the optimal strategy for the offline algorithm and show that it causes at most m + n/m page misses in total, starting from an empty cache.