CSC 789 Assignment 3

Due date, October 14, 2003, 5:30 PM.

  1. 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.
  2. Work exercise 4 of Using Potential to Prove Competitiveness.

Back to Course Page