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 ??=????₁,??₂, . . . ,??_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 rank_L(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 rank_L(x)?=?4. Let?c_i denote the cost of access i using 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 c_i = 2 ? rank_L(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?L_i be the list after access ?_i using move-to-front, and let L^*_i be the list after access i using heuristic H. We denote the cost of access i by c_i for move-to-front and by c^*_i for heuristic H. Suppose that heuristic H performs t^*_i transpositions during access ?i.

c.?In part (b), you showed that?c_i = 2 ? rank_{Li_1}(x)??1. Now show that?c^*_i = rank_L^*_i-1 (x) + t^*_i.

We define an?inversion?in list?L_i as a pair of elements y and z such that y precedes z in L_i and z precedes y in list L^*_i. Suppose that list?L_i has q_i inversions after processing the access sequence ??₁,??₂,.. .,??_i?. Then, we define a potential function ? that maps Li to a real number by ?(L_i)?=?2q_i. For example, if?L_i has the elements ?e, c, a, d, b? and L^*_i has the elements ?c, a, b, d, e?, then L_i has 5 inversions ((e, c), (e, a), (e, d), (e, b), (d, b)), and so ?(L_i) = 10. Observe that ?(L_i) ??0?for all?i?and that, if move-to-front and heuristic H start with the same list?L₀, then??(L₀)?=?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 i th access.

• Set A consists of elements that precede x in both L_i-1 and L^*_i-1.
• Set?B?consists of elements that precede?x?in?L_i-1 and follow x in L^*_i-1.
• Set?C?consists of elements that follow?x?in?L_i-1 and precede x in L^*_i-1.
• Set?D?consists of elements that follow?x?in both?L_i-1 and L^*_i-1.

e. Argue that rank_Li-1(x) = |A| + |B| + 1 and rank_L^*_i-1(x) = |A| + |C| + 1.

f. Show that access i causes a change in potential of

where, as before, heuristic H performs t^*_i transpositions during access ?_i.

Define the amortized cost c ?_i of access ?i by c ?_i = c_i + ?(L_i)-??(L_i-1).

g. Show that the amortized cost c ?_i of access i is bounded from above by 4c^*_i.

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.

Transcribed Image Text:

¤(L;) – ¤(L¡-1) < 2([A| – |B| + tỷ).