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

Related questions

0 votes
0 answers
1
asked ago in Algorithms by vivek9837 Junior (921 points)   | 28 views
0 votes
0 answers
2
asked in Algorithms by Anjana Babu Active (1.2k points)   | 161 views


Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points


25,991 questions
33,561 answers
79,414 comments
31,029 users