Introduction to Algorithms, Third Edition

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
h
r
1
; r
2
; : : : ; r
n
i
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.

---

450
Chapter 16
Greedy Algorithms
Chapter notes
Much more material on greedy algorithms and matroids can be found in Lawler
[224] and Papadimitriou and Steiglitz [271].
The greedy algorithm first appeared in the combinatorial optimization literature
in a 1971 article by Edmonds [101], though the theory of matroids dates back to
a 1935 article by Whitney [355].
Our proof of the correctness of the greedy algorithm for the activity-selection
problem is based on that of Gavril [131]. The task-scheduling problem is studied
in Lawler [224]; Horowitz, Sahni, and Rajasekaran [181]; and Brassard and Bratley
[54].
Huffman codes were invented in 1952 [185]; Lelewer and Hirschberg [231] sur-
veys data-compression techniques known as of 1987.
An extension of matroid theory to greedoid theory was pioneered by Korte and
Lov´asz [216, 217, 218, 219], who greatly generalize the theory presented here.

---