Modern computers use a cache to store a small amount of data in a fast memory. Even though a program may access large amounts of data, by storing a small subset of the main memory in the cache-a small but faster memory-overall access time can greatly decrease. When a computer program executes, it makes a sequence 〈r₁, r₂, . . . , r_n〉 of n memory requests, where each request is for a particular data element. For example, a program that accesses 4 distinct elements {a, b, c, d} might make the sequence of requests 〈d, b, d, b, d, a, c, d, b, a, c, b〉. Let k be the size of the cache. When the cache contains k elements and the program requests the (k + 1)st element, the system must decide, for this and each subsequent request, which k elements to keep in the cache. More precisely, for each request ri, the cache-management algorithm checks whether element r_i is already in the cache. If it is, then we have a cache hit, otherwise, we have a cache miss. Upon a cache miss, the system retrieves r_i from the main memory, and the cache-management algorithm must decide whether to keep r_i in the cache. If it decides to keep r_i and the cache already holds k elements, then it must evict one element to make room for r_i. The cache-management algorithm evicts data with the goal of minimizing the number of cache misses over the entire sequence of requests.

Typically, caching is an on-line problem. That is, we have to make decisions about which data to keep in the cache without knowing the future requests. Here, however, we consider the off-line version of this problem, in which we are given in advance the entire sequence of n requests and the cache size k, and we wish to minimize the total number of cache misses.

We can solve this off-line problem by a greedy strategy called furthest-in-future, which chooses to evict the item in the cache whose next access in the request sequence comes furthest in the future.

a. Write pseudocode for a cache manager that uses the furthest-in-future strategy. The input should be a sequence 〈r₁, r₂, . . . , r_n〉 of requests and a cache size k, and the output should be a sequence of decisions about which data element (if any) to evict upon each request. What is the running time of your algorithm?

b. Show that the off-line caching problem exhibits optimal substructure.

c. Prove that furthest-in-future produces the minimum possible number of cache misses.