Problem 2:``Stilgar's Self-Adjusting Structures (24 pts)

Suppose you have a set of $n$ distinct keys or elements stored in a list. Let $f(n)$ be the average number of elements accessed in satisfying a search query for a single element. Assume that each element is equally likely to be the target of a search.

2.1 (6)

Is the following expression for $f(n)$ reasonable?

$$f(n) = \frac{(n+1)} {2}$$

If your answer is yes, explain why. If it is no, explain why not and give a more reasonable value, if one exists.

2.2 (6)

Suppose now that we use a self-adjusting list to store these keys, where the list is modified after each data access. One way to implement a self-adjusting list is to move the key satisfying the search query to the head of the list, giving the method its name ``move to front''. New elements are inserted at the head of the list, following a deletion, the predecessor of a deleted element becomes the new list head. Let $g(n)$ represent the average number of elements accessed by a search query applied to the new list.

Would you expect $g(n)$ be less than $f(n)$ ? If your answer is yes, explain why. Otherwise, explain why not.

Note: you don't need to calculate $g(n)$ or $f(n)$ directly here; you merely need to reason about the effect of the reordering of list elements upon the search process

2.3 (6)

When $n$ exceeds a few hundred, the ``move-to-front'' operation described for problem 2.2 is replaced by a ``transpose'' strategy, which swaps the key targeted by the search with its predecessor in the list. Why might this be preferred for larger data sets?

2.4 (6)

Give conditions under which the self-adjusting list described for this problem might be preferred over a splay tree. Or, if you don't believe such conditions exist, explain why not.