@ankur - Ans-9 how can it be log n. The heap given is Max heap. I think it should be O(n) using array or tree traversal (as heap is implemented) keeping current min at hand. Correct me if m wrong.
On Sat, Oct 15, 2011 at 12:14 PM, shady <[email protected]> wrote: > already been answered... :-/ > but have to say you are damn quick... > > > On Sat, Oct 15, 2011 at 12:03 PM, Bittu Sarkar <[email protected]> wrote: > >> Q7. Correct answer is 12km west and 12km south for sure!! >> >> >> On 21 September 2011 13:28, Nitin Garg <[email protected]> wrote: >> >>> Ohh i totally missed that line. >>> Thanx a lot :) >>> >>> >>> On Wed, Sep 21, 2011 at 10:46 AM, pankaj agarwal < >>> [email protected]> wrote: >>> >>>> @Nitin Garg >>>> >>>> Question 6 - >>>> >>>> i agree that greater the sum is and greater the probability to getting >>>> it. >>>> but in given question if sum>100 then rolling is stopped >>>> so for >>>> >>>> P(106)=P(100)*1/6 >>>> P(105)=P(100)*1/6+P(99)*1/6 >>>> . >>>> . >>>> . >>>> P(101)=P(100)*1/6+P(99)*(1/6)+P(98)*(1/6)+P(97)*(1/6)+..+P(95)*(1/6) >>>> >>>> now P(101) is more >>>> >>>> cleare me if something is wrong. >>>> >>>> >>>> >>>> On Mon, Sep 19, 2011 at 1:35 PM, Nitin Garg >>>> <[email protected]>wrote: >>>> >>>>> Question 6 - >>>>> Intuitively you can see that the greater the sum is, the greater the >>>>> favorable events in sample space. >>>>> >>>>> e.g. - sum = 1 .. cases {(1)} Pr = 1/6 >>>>> sum = 2 cases {(2),(1,1)} Pr = 1/6 + 1/36 >>>>> sum = 3 cases {(3),(2,1)(1,2)(1,1,1)} Pr = 1/6 + 1/36 +1/36 >>>>> + 1/216 >>>>> >>>>> >>>>> for a more formal proof, look at the recursion - >>>>> >>>>> >>>>> P(k) = (P(k-6) + P(k-5) + P(k-4)... P(k-1)))/6 >>>>> >>>>> where P(0) = 1, P(i) = 0 for i<0 >>>>> >>>>> Base case - >>>>> P(2) > P(1) >>>>> >>>>> Hypothesis - >>>>> >>>>> P(i) > P(i-1) for all i <= k >>>>> >>>>> To prove >>>>> P(k+1) > P(k) >>>>> >>>>> Proof >>>>> P(k+1) - P(k) = (P(k) - P(k-6))/6 > 0 >>>>> >>>>> >>>>> >>>> >>>> >>>> >>>>> -- >>>>> Pankaj Agarwal >>>>> Communication and Computer Engineering >>>>> LNMIIT,jaipur >>>>> >>>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Nitin Garg >>> >>> "Personality can open doors, but only Character can keep them open" >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Bittu Sarkar >> 5th Year Dual Degree Student >> Department of Computer Science & Engineering >> Indian Institute of Technology Kharagpur >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Mohit -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
