(a) Let d > 2 be a fixed positive integer. consider a perfect SkipList construct

Question

(a) Let d > 2 be a fixed positive integer. consider a perfect SkipList constructed as follows: In order to create the ith level Li of the SkipList, we scan the keys of level Li1, and promote to Li every d’th key. So for example, the perfect SkipList discussed in class uses the value d = 2. The case d = 3 implies that every third key is promoted, and so on. Express your answer as a function of n and d

i. What is the number of levels, as a function of n and k?

ii. What is the worst case time for performing find(x) operation ? For delete(x), For insert(x) ?

iii. Assume n = 109 . Compare the case d = 2 vs. d = d = 10 vs. d = 1000. When will the search time be optimal.

(b) Assume that we re-create a SkipList by inserting n keys, in the same order, but this time we are using the randomized insertion algorithm shown on the slides. However a key that appears in level i is promoted to level i+ 1 with probability p = 0.1 (rather than p = 0.5 that was discussed on the slides). Will the expected time to perform find(x) operation increase or decrease, compared to the expected time for the same operation in the original SkipList created with p = 0.5.

(c) Repeat the question, but now assume p = 0.9.

Explanation / Answer

(a)

(i)              Scan the keys of Level , create   (i th level) and promote to every 2nd key. It means (Number of key in  = (1/2) Number of key )

Now calculate the number of level (for d =2) will be

                                                  (for d =3) =>

Now write the function of n and k :        f (n,k) =

              where n = Total number of key

                         k = The number of key to be promoted in next Level

(ii)           Time complexity in worst case in a SkipList is given below for different cases:

find (x) :      f(n, d) = Time complexity (Worst): O(n)

delete (x) :   f(n, d) = Time complexity (Worst): O(n)

insert (x) :    f(n, d) = Time complexity (Worst): O(n)

(iii)        Average time to search in a skip List is : f(n, d) = Time complexity (Average) : O()

Now calculate time complexity for different cases:

Case 1: If d=2 and n=109,

time complexity -     log2n, means 9*- log210

Case 2: If d=10 , and n=109,

time complexity -     log10n, means 9*- log10109 =9 + 10(for linear search)

Case 3: If d=1000 , and n=109,

time complexity -     log1000n, means 9*- log1000109 =3 + 1000(for linear search)

It is clear that (d=10) has the optimal best solution for n= 109

Although 1000 is biggest number and give best solution (for ).

But for finding a particular key we also need search the remaining part (linearly)

So For n =  , (d=10) gives the optimal Solution

(b)

The probability of all keys being in second level and none in third level is  . For all the keys being promoted to the second level is 0.5*0.5*0.5... times so the probability for n times would be.. Similarly the probability of keys not being promoted to the third level would be the same as 1-0.5=0.5. So the final result would be *=.

(c)

Now, assume the probability of all keys in second level and none in third level is (0.9n) * 0.1n . For all the keys being promoted to the second level is 0.9 * 0.9 * 0.9... times so the probability for n times would be. 0.9n. Similarly the probability of keys not being promoted to the third level would be the same as 1-0.9=0.1. So the final result would be 0.9n * 0.1n .

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.