
CSC 789 Assignment 5
Due date:
Thursday, March 19, 2009
Since this homework assignment is more than twice as difficult (and counts
more than twice as much) as any
previous assignment, I suggest you get started earlier than usual.
-
Work Exercise 6.6, that is,
prove that the Manhattan Plane is isometric to the plane with the
l
metric.
-
Work Exercise 6.10.
You may not assume the result of Exercise 6.9 unless you prove it.
-
Let M={x,y,z} where d(x,y)=6, d(x,z)=7, and d(y,z)=9. Consider the 2-server
problem on M, where the initial position of the servers is {x,y}.
-
Suppose the request sequence is z x.
If we use HARMONIC, what is the probability that we have a server at y
after servicing that sequence?
-
Suppose the request sequence is z x.
If we use Random-Slack, what is the probability that we have a server at y
after servicing that sequence?
-
Suppose the request sequence is z x y x, and
we use the work function algorithm. What is the optimum offline cost
of servicing that sequence?
If we use the work function algorithm, what are our moves, and what
is our cost?
Show the table of work function values (or offset function values) at each
step.
-
Suppose the request sequence is z x y x, and
we use the tight span algorithm. What are our moves, and what is our cost?
Show the positions of the servers and the virtual servers in the tight span
of M at each step.
-
Suppose that the request sequence is z x y x, and
we use BALANCE_2, the Irani-Rubinfeld algorithm.
What is our cost? Show the positions of the servers and the values
of the needed variables at each step.
-
Suppose that the request sequence is z x y x, and
we use BALANCE_SLACK.
What is our cost? Show the positions of the servers and the values
of the needed variables at each step.
-
Suppose someone had a proof that the k-server conjecture holds for
Rn with the l
metric, for every n.
Prove that the k-server conjecture would be true.
-
Work Exercises 9.1, 9.2, 9.3, and 9.4.
-
Compute the competitiveness of EQUITABLE if k=3 and n=5, that is,
there are a total of 5 pages in the universe in main memory.
Your solution should show the graph with the offset functions and
the distributions, the costs and the potentials.
Hint: the anwer is H2 = 11/6.