@Nithin: Sorry I did not understand your logic!! If a person looses a match he should be knocked out of the tournament. Could you please explain why 2 matches to knock out a person??
On Mon, Sep 19, 2011 at 2:47 PM, praveen raj <[email protected]> wrote: > For question 2 see ashima link. > > On 19-Sep-2011 1:43 PM, "Nitin Garg" <[email protected]> wrote: > > > > Can someone tell answers to question 2 and 5 with explanation?? > > > > > > > > > > On Mon, Sep 19, 2011 at 1:40 PM, Nitin Garg <[email protected]> > wrote: > >> > >> In Question 4 i just kept counting new processes that are being added in > every iteration. > >> No. of new processes being created is equal to the already running no. > of even pid processes. > >> > >> Time - PId > >> 0 - 0 1 > >> 1 - 0,1 2 > >> 2, - 0,1,2 3 > >> 3, - 0,1,2,3,4 5 > >> 4 - 0,1,2,3,4,5,6,7 8 > >> . > >> . > >> . > >> > >> > >> > >> 1,2,3,5,8,11,17,25,38,57,86,129,194 > >> > >> I kept counting, got 194. > >> Don't know of any shortcut. > >> > >> > >> > >> > >> > >> 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 > >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> On Mon, Sep 19, 2011 at 1:04 PM, Nitin Garg <[email protected]> > wrote: > >>>> > >>>> Question 3 - > >>>> To eliminate one player, you need to host atleast 2 matches and make > him loose in both 2. These 2 matches can not contribute to elimination of > any other player. > >>>> So, min 2 matches for every player who is to be eliminated, hence 100. > >>>> > >>>> > >>>> On Mon, Sep 19, 2011 at 11:54 AM, Bhanu Chowdary < > [email protected]> wrote: > >>>>> > >>>>> @Nitin: Answer to question 3 is 50. > >>>>> > >>>>> > >>>>> On Mon, Sep 19, 2011 at 11:44 AM, praveen raj <[email protected]> > wrote: > >>>>>> > >>>>>> @nitin Plz explain how u have reached answer of question no. 4 and 6 > >>>>>> > >>>>>> > >>>>>> On 19-Sep-2011 12:26 AM, "Nitin Garg" <[email protected]> > wrote: > >>>>>> > > >>>>>> > Answer 3 - 100 > >>>>>> > Answer 6 - 103 > >>>>>> > Answer 4 - 194 total processes including the parent > >>>>>> > Answer 7 - 12 km south, 12 km east > >>>>>> > > >>>>>> > > >>>>>> > On Sun, Sep 18, 2011 at 11:53 PM, Ashima . <[email protected]> > wrote: > >>>>>> >> > >>>>>> >> @malay: how cm n+logn-2? > >>>>>> >> cn u explain the logic ? > >>>>>> >> > >>>>>> >> Ashima > >>>>>> >> M.Sc.(Tech)Information Systems > >>>>>> >> 4th year > >>>>>> >> BITS Pilani > >>>>>> >> Rajasthan > >>>>>> >> > >>>>>> >> > >>>>>> >> > >>>>>> >> > >>>>>> >> On Sun, Sep 18, 2011 at 11:07 AM, Ashima . < > [email protected]> wrote: > >>>>>> >>> > >>>>>> >>> rite! 62.5% > >>>>>> >>> > >>>>>> >>> Ashima > >>>>>> >>> M.Sc.(Tech)Information Systems > >>>>>> >>> 4th year > >>>>>> >>> BITS Pilani > >>>>>> >>> Rajasthan > >>>>>> >>> > >>>>>> >>> > >>>>>> >>> > >>>>>> >>> > >>>>>> >>> On Sat, Sep 17, 2011 at 9:04 PM, malay chakrabarti < > [email protected]> wrote: > >>>>>> >>>> > >>>>>> >>>> create a tournament tree.in each round one value is eliminated > to obtain in the process the winner or the highest value in n-1 comparisons. > Then check the queue of the winner which contains log(n) entries of the > values beaten by the winner which implicitly will contain the runners > up.Then log(n)-1 comparisons to find the highest among all the losers whom > the winner had beaten. So all over complexity will be n-1 +log(n) -1 = > n+log(n)-2. Hp that answers ur query. nice question btw :) > >>>>>> >>>> > >>>>>> >>>> > >>>>>> >>>> On Sun, Sep 18, 2011 at 8:02 AM, VIHARRI < > [email protected]> wrote: > >>>>>> >>>>> > >>>>>> >>>>> hey i'm also thinking n + logn -2.. but couldnt able to figure > out > >>>>>> >>>>> how??? can you please explain the logic > >>>>>> >>>>> > >>>>>> >>>>> -- > >>>>>> >>>>> 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. > >>>>>> >>> > >>>>>> >>> > >>>>>> >> > >>>>>> >> -- > >>>>>> >> 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. > >>>>>> > >>>>>> -- > >>>>>> 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. > >>>>> > >>>>> > >>>>> > >>>>> > >>>>> -- > >>>>> Bhanu Chowdary > >>>>> > >>>>> -- > >>>>> 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" > >>> > >>> > >>> > >>> > >>> -- > >>> Nitin Garg > >>> > >>> "Personality can open doors... but only Character can keep them open" > >> > >> > >> > >> > >> -- > >> Nitin Garg > >> > >> "Personality can open doors... but only Character can keep them open" > > > > > > > > > > -- > > 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. > > -- > 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. > -- Bhanu Chowdary -- 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.
