GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
330 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 (767 points)  
reshown by | 330 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 (217 points)  


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2606 Points

  5. Debashish Deka

    2092 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1318 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1166 Points

  10. Sanjay Sharma

    1004 Points

Monthly Topper: Rs. 500 gift card

21,439 questions
26,753 answers
60,919 comments
22,929 users