In this problem we are concerned with caching or paging. Unlike the RAM or Turing machine models, actual computers have a hierarchy of memory levels.

The basic model for this is that there are two levels, a large but slow-access main memory, and a small but fast-access memory called the cache.

The cache can hold a fixed number k of "pages". The CPU cannot access a page before it is brought into cache. For the purpose of this problem, we treat CPU accesses to the cache as free, and what we are trying to minimize is M = the number of times that a page is brought from main memory into the cache.

(Since k is fixed, when a page is brought in it must evict something else, which is why we normally can't get M to be 0.)

The sequence of pages to be accessed is not known in advance, so deciding on how to administer the paging to minimize M is an important problem in on-line algorithms mdash algorithms that must make decisions "causally" (meaning, depending only on the past).

However, Computer Systems researchers realized it is useful to consider also the clairvoyant or "off-line" version of the problem, in which the entire sequence of CPU page requests, r_1, ..., r_T, is known in advance. (Think of T as very large.)

The off-line optimum gives a lower bound on the performance of on-line algorithms; moreover, one may hope to combine such an algorithm with heuristic predictions and achieve performance that is not too much worse than the lower bound.

Here is the greedy algorithm that people came up with: at time t, if r_t is not in the cache, bring it in and evict the record in the cache whose next request time is furthest in the future.

More formally, if p_1, ...p_k are the pages in cache at time t, the p_i evicted is that which maximizes min{u: [u > t] wedge (p_i = r_u]}. (If the set is empty, the min equals infinity.)

For example, for k = 2 and for the seven requests 1, 2, 3, 2, 3, 1, 2, the time series of cache contents in this algorithm will be: {}, {1}, {1, 2}, {2, 3}, {2, 3}, {2, 3}, {1, 2}, {1, 2}. The cost is M = 4. Show that this algorithm optimizes M.