1 Move to Front Amortized analysis can be used not just to give absolute bounds on running times, but also bounds compared to other algorithms. In this problem we'll see an example of this. Suppose we have n items x1 , x2 , . . . , xn that we wish to store in a linked list. The cost of a lookup operation is the position in the list, i.e. if we lookup some element xi we pay 1 if it is the first element, 2 if it is the second element, 3 if it is the third element, etc. This models the time it takes to scan through the list to find the element. For example, suppose there are four items and we lookup x1 twice, x2 three times, x3 once, and x4 four times. Then if we store them in the list (x1 , x2 , x3 , x4 ) the total cost is 1(2) + 2(3) + 3(1) + 4(4) = 27. On the other hand, if we stored them in the list (x4 , x2 , x1 , x3 ) the cost would be 1(4) + 2(3) + 3(2) + 4(1) = 20. It is easy to see that if we knew the number of times each element was looked up, the optimal list is simply sorting by the number of lookups, i.e. the first element is the one looked up most often, then the element looked up next most often, etc. But what if we do not know how many times each element will be looked up? It turns out that a good strategy is Move-to-Front (MTF): when we lookup an item, we also move it to the head of the list. Let's say that moving an element is free (it is easy enough to implement with a constant number of pointer switches, in any case). So if, for example, we start with the list (x1 , x2 , . . . , xn ) and then lookup x4 , we pay a cost of 4 and afterwards the list will be (x4 , x1 , x2 , x3 , x5 , x6 , . . . , xn ). Then if we lookup x4 again we only have to pay a cost of 1. (a) Consider a sequence of m operations (think of m as being much larger than n). Let Cinit be the cost of these operations if we used the original list (x1 , x2 , . . . , xn ) the entire time (i.e. we do not use MTF). Let CM T F be the cost if we use MTF on the same operations starting from the original list. Prove that CM T F 2Cinit . Hint: Think of each item xi as having a \"piggy bank\" in which the number of tokens is the number of elements before it in the current list that come after it in the initial list, or a potential function equal to the number of reversals. (b) Now let Cstatic be the smallest possible cost among all fixed lists. In other words, given the same sequence of lookups, each fixed list (without MTF) has some cost, and let Cstatic be the minimum of those costs. Note that this will correspond to the list that is sorted by the number of accesses, like in the first example. Prove that CM T F 2Cstatic + n2 . Hint: think of a new bank or potential function which is relative to the unknown static best fixed list, rather than relative to the initial list. What does this imply about the initial amount of money in the bank / potential? 1