7. What is the expected value of cnt after the following function is executed ?

cnt = 0; M = ;

for i = 1 to n {

xi = rand() ; Comment: returns a random float number of between 0 and 1.

if (xi > M) then { M = xi ; cnt + +; } }

Hint: Define the random variable Yi which is 1 if xi > max{x1, x2 . . . xi1} and Yi = 0 otherwise. What is E(Y1 + Y2 + + Yn). 8. Create a SkipList for a set of n keys S = {k1 . . . kn}. The keys are known in advance, and are sorted. The height of the Skiplist is 3. The SkipList should be designed such that max kiS T(ki) is as small as possible, where T(ki) is defined as the time for searching ki , where the search is starting, as usual in the upper leftmost element. 9. Let L be a perfect SkipList constructed on a set of n keys, and let X = {k1 . . . km} be another set of keys. Assume m 7. What is the expected value of cnt after the following function is executed? for i 1 to n i rand Comment: returns a random float number of between 0 and 1 if (>M) then { cnt + + Hint: Define the random variable Y. which is l if i> maxi, x2...^i-i) and Y? = 0 otherwise. What is E(Y + + + Y,.) 8. Create a SkipList for a set of n keys S = {ki . . . knj. The keys are known in advance, and are sorted. The height of the Skiplist is