# Academic help online

Competitive analysis of self-organizing lists with move-to-front
A self-organizing list is a linked list of n elements, in which each element has a unique key. When we search for an element in the list, we are given a key, and we want to find an element with that key.
A self-organizing list has two important properties:
1. To find an element in the list, given its key, we must traverse the list from the beginning until we encounter the element with the given key. If that element is the kth element from the start of the list, then the cost to find the element is k.
2. We may reorder the list elements after any operation, according to a given rule with a given cost. We may choose any heuristic we like to decide how to reorder the list.
Assume that we start with a given list of n elements, and we are given an access sequence σ = {σ1, σ2,…, σm}of keys to find, in order. The cost of the sequence is the sum of the costs of the individual accesses in the sequence.
Out of the various possible ways to reorder the list after an operation, this problem focuses on transposing adjacent list elements—switching their positions in the list—with a unit cost for each transpose operation. You will show, by means of a potential function, that a particular heuristic for reordering the list, move-to-front, entails a total cost no worse than 4 times that of any other heuristic for maintaining the list order—even if the other heuristic knows the access sequence in advance! We call this type of analysis a competitive analysis.
For a heuristic H and a given initial ordering of the list, denote the access cost of sequence σ by CH(σ). Let m be the number of accesses in σ.
a. Argue that if heuristic H does not know the access sequence in advance, then the worst-case cost for H on an access sequence σis CH(σ) = ?(mn).
With the move-to-front heuristic, immediately after searching for an element x, we move x to the first position on the list (i.e., the front of the list).
Let rankL(x) denote the rank of element x in list L, that is, the position of x in list L. For example, if x is the fourth element in L, then rankL(x) = 4. Let ci denote the cost of access σiusing the move-to-front heuristic, which includes the cost of finding the element in the list and the cost of moving it to the front of the list by a series of transpositions of adjacent list elements.
b. Show that if i accesses element x in list L using the move-to-front heuristic, then ci = 2.rankL(x) – 1.
Now we compare move-to-front with any other heuristic H that processes an access sequence according to the two properties above. Heuristic H may transpose elements in the list in any way it wants, and it might even know the entire access sequence in advance.
Let Li be the list after access σiusing move-to-front, and let width=be the list after access σiusing heuristic H. We denote the cost of access σiby cifor move-to-to front and by width=for heuristic H. Suppose that heuristic H performs width=transpositions during access σi.
c. In part (b), you showed that ci = 2.rankLi-1(x) – 1. Now show that width== rank width=
We define an inversion in list Li as a pair of elements y and zsuch that y precedes zin Li and zprecedes y in list width=Suppose that list Li has qi inversionsafter processing the access sequenc{σ1, σ2,…,σ1}. Then, we define a potentialfunction Φ that maps Lito a real number by Φ(Li) =2qi. For example, if Lihasthe elements {e, c, a, d, b,} and width=has the elements {c, a, b, d, e}, then Li has 5inversions ((e, c), (e, a), (e, d), (e, b), (d, b)), and so Φ(Li)=10. Observe that Φ(Li) ≥ 0 for all i and that, if move-to-front and heuristic H start with the samelist L0, then Φ(.L0) = 0.
d. Argue that a transposition either increases the potential by 2 or decreases the potential by 2.
Suppose that access σi, finds the element x. To understand how the potential changes due to σi, let us partition the elements other than x into four sets, depending on where they are in the lists just before the ith access:
· Set A consists of elements that precede x in both Li-1and width=
· Set B consists of elements that precede x in Li-1and follow x in width=
· Set C consists of elements that follow x in Li-1and precede x in width=
· Set D consists of elements that follow x in both Li-1and width=
e. Argue that rankLi-1(x)= |A| + |B| + 1 and rank width=(x) = |A| + |C| + 1.
f. Show that access σicauses a change in potential of Φ(Li) -Φ(Li-1)≤2.|A| – |B| + width=), where, as before, heuristic H performs width=transpositions during access σi. Define the amortized cost width= of access σ1 by width=
g. Show that the amortized cost width= of access σiis bounded from above by 4 width=
h. Conclude that the cost CMTF(σ) of access sequence σwith move-to-front is at most 4 times the cost CH(σ) of σwith any other heuristic H, assuming that both heuristics start with the same list.