
CSC 789 Assignment 3
Due date, October 14, 2003, 5:30 PM.
-
Use the ``randomized cruel adversary" to prove Theorem 6 of
Using Potential to Prove Competitiveness.
The randomized cruel adversary uses only $k+1$ pages. It always
requests the page which the algorithm does not have in cache, and
then, if it does not have the page in cache itself, ejects a page
at random.
-
Work exercise 4 of
Using Potential to Prove Competitiveness.

Back to
Course Page