1. Prove that, given a memory capacity, request sequence, and replacement
algorithm (not necessarily using demand paging), another replacement
algorithm exists that uses demand paging and causes the same or a fewer
total number of pages to be loaded into fast memory.

2. Consider the k-server problem on a line. Show that the potential function
I used in my lecture (see page 16 of my slides) really has the properties
required. That is, give the missing details I failed to give in my lecture.

3. Define formally the minimum weighted matching and minimum-cost maximum-flow
problems referred in our textbook. Give also a brief summary what is known
about the computational complexity of these two problems.

4. What is the complexity of the dynamic programming procedure used for
computing the cost of an optimal offline algorithm for the k-server
problem when the request sequence is of length n. For the special case of
a uniform metric space a faster algorithm exists. What is its complexity?

5. How does the work function algorithm handle the requested sequence for
which the greedy algorithm failed? (See page 12 of my slides.)

6. Exercise 10.8 from our textbook.