GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
336 views
A level of a max heap (containing 100 nos) is choosen randomly, on its selection, a node from the same level is choosen randomly. What is the probability that it is the 36th  smallest element
asked in Algorithms by Junior (777 points)  
reshown by | 336 views
...........
what I did is

P = $\frac{1}{7}*0 + \frac{1}{7}*\frac{1}{2} + \frac{1}{7}*\frac{1}{4} + \frac{1}{7}*\frac{1}{8}+ \frac{1}{7}*\frac{1}{16}+ \frac{1}{7}*\frac{1}{32}+ \frac{1}{7}*\frac{1}{37} = 0.087$

Suggestion and correction plz !
@Debashish Deka u r correct...

having one dout ... 36 at level 2 is at fixed location at right end and having only one choice..here u takes probability=1/2 since this level having 2 ele.

now at level 3 having 4 elements ...but at this level 36 can be at any place ... u takes probability=1/4 here having 4 choices...

confusing probability for me! plz explain !
@Debashish , why 36 occurs in any level from 2 to 7.
@debashish, can you make that an answer

1 Answer

0 votes
Its P(65th largest element given that a level is chsen and an elemwnt is chosen from it)

So P= ((1/7)*(1/37))/((1/7)+(1/7)*(1/2)+......+ (1/7)*(1/2^5)+(1/7)*(1/37))

P=0.0135
answered by (219 points)  


Top Users Apr 2017
  1. akash.dinkar12

    3508 Points

  2. Divya Bharti

    2542 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,040 answers
63,230 comments
24,135 users