cnt = 0; M = ; for i = 1 to n { xi = rand() ; Comment: returns a random float nu
ID: 3748629 • Letter: C
Question
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 < n. Suggest an O(m log( n m )) time algorithm for computing which key(s) of X appear in L. You could assume that X is sorted. You could not assume that the keys of X are equally spaced in L. Yet understanding this special case could shed some intuition.
Explanation / Answer
ANS 7:
given: cnt=0 and M = -
Inside the for loop(iterating from i=1 to i=n): FOR i=1 1. rand() funtion generates a float value between 0 to 1. This value is then assigned to the variable xi . 2. Inside the if statement checking if the value of xi>M. Since any value between 0 and 1 is always greater than -, therefore the condition is true and the code inside the for loop will be executed. That is: a) M=xi , cnt=cnt+1; ie; 1
FOR i=2 1. {SAME AS ABOVE} 2. Now as M is containing a value between 0 and 1 and xi is also a value between 0 and 1, So, the condition inside if statement could be true or could be false.
Therefore, the expected value of cnt is greater than or equal to 1.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.