Due in class Monday, October 1.
Consider the list update problem in the no-free-exchange model (all exchanges cost 1). Prove that the move-to-front algorithm has a competitive factor of 4. (Note: You'll need to adjust the potential function.)
Intutively it appears that moving to the front all the time is "too radical", and the efficiency could be improved if it didn't move to front all the time. One way to do this is to allow the algorithm to incorporate randomization. Now to be competitive, the expected cost (taken over all its random choices) of the algorithm running on the sequence should be within a constant factor of the cost of the off-line adversary on the same sequence.
So the goal of this problem is to prove that the algorithm that flips a coin and moves to front with probability 1/2 is 3-competitive.
Recall the analysis of the splaying algorithm from class in which we defined the the size of node x to be the sum of the weights of the nodes in x's subtree, and defined the rank of x to be the floor of log(size(x)).
Suppose we modify the splaying algorithm so that we only perform the splay step when rank of the current node equals the rank of its grandparent g(x) (assuming g(x) exists), else we simply move up the tree to g(x) and continue the splay from there. So unlike normal splaying, the node accessed does not necessarily end up at the root of the tree.
a. Is the balance theorem still true for this tree?
b. Give and prove an upper bound on the number of rotations that can be performed starting from an initial tree with n nodes, or show that an infinite number of rotations can occur.
Search trees are much more than simply a solution to the dictionary problem (lookups, insertions, deletions). They are useful for dealing with the list implicitely represented by the tree. Show how to use splay trees (augmented appropriately) to efficiently solve the following problem. At any time there's a list of elements, call them x[0], x[1], ... x[n-1]. (Initially the list is empty.) We use the term rank to indicate the index of an element -- that is, x[i] has rank i. Here are the operations:
insert(x, i): Insert item x into the list so that it has rank i. (i < n before the operation)
delete(i): Delete the item of rank i (i < n before the operation)
reverse(i,j): Reverse the elements in the range [i,j]. For example, if the original list were [a,b,c,d,e,f] then reverse(1,3) would result in the list [a,d,c,b,e,f]. It must be the case that (0 ≤ i ≤ j < n).