Replying to myself, there is an obvious mistake. The statement print "more than half of the students are in the group with student", i near the end should be print "more than half of the students are in the group with student", candidate
Dave On Nov 8, 3:10 pm, Dave <dave_and_da...@juno.com> wrote: > @Ankit: I'm assuming a typo in the original problem statement, such > that a smile means that they are members of the same group while a nod > means that they are members of different groups. Number the students > from 1 to n. Then the algorithm is as follows: > > let candidate = student[1] > let k = 1 > for i = 2 through n > if student[i] knows candidate then > k = k + 1 > else > k = k - 1 > if k equals 0 then > candidate = student[i] > k = 1 > end if > end if > end for > k = 0 > for k = 1 through n > if student[i] knows candidate then > k = k + 1 > end if > end for > if 2*k > n then > print "more than half of the students are in the group with > student", i > else > print "no group has more than half of the students as members." > end if > > This algorithm answers the question in O(n) introductions. > > Dave > > On Nov 8, 9:53 am, Ankit Babbar <ankitbabba...@gmail.com> wrote: > > > > > How can does the maximum vote algo apply to the above question..?? > > please explain.. > > > On 11/8/10, cheng lee <lichenga2...@gmail.com> wrote: > > > > Where can we see that this algorithm use the divide and conquer > > > techniques? > > > > 2010/11/7 Pratik Bhadkoliya <pkbhadkol...@gmail.com> > > > >> A Linear-time Majority Vote Algorithm > > > >> Problem: How to decide, in one pass which element of a sequence is in the > > >> majority, provided there is such an element. > > > >> As we sweep through the sequence, we maintain a pair consisting of a > > >> current candidate and a counter. Initially, the current candidate is > > >> unknown > > >> and the counter is 0. When we move the pointer forward over an element e: > > > >> - If the counter is 0, we set the current candidate to e and we set > > >> the > > >> counter to 1. > > >> - If the counter is not 0, we increment or decrement the counter > > >> according to whether e is the current candidate. When we are done, the > > >> current candidate is the majority element, if there is a majority. > > > >> If you must confirm that the chosen element is indeed the majority > > >> element, > > >> you must take one more linear pass through the data to do it. > > > >> if Counter is greater than 0 at the end then we get the majority element > > >> in > > >> candidate field. > > > >> Now, just count the number of times it occurred in the list using one > > >> more > > >> traversal and if now this count is greater than n/2 then return true or > > >> false otherwise. > > > >> So, total pass = 2n -> order is O(n) > > >> On Sun, Nov 7, 2010 at 11:15 AM, Ashim Kapoor > > >> <ashimkap...@gmail.com>wrote: > > > >>> Is'nt this solvable by the majority vote algorithm already discussed in > > >>> this list? > > > >>> Ashim. > > > >>> On Sun, Nov 7, 2010 at 3:42 AM, lichenga2404 > > >>> <lichenga2...@gmail.com>wrote: > > > >>>> There are many secret groups in College A.Every student at college A > > >>>> is a member or these secret group, though membership in one excludes a > > >>>> student from joining any other group. You wish to determine if any one > > >>>> of these groups contains more than half of the student population. To > > >>>> achieve this , you will introduce 2 students to each other: if they > > >>>> are members of different group , they will smile. If different group , > > >>>> they will nod. How to determine if any one group has more than half of > > >>>> the student population as members in O(n) introductions . And justify > > >>>> the answer. > > > >>>> -- > > >>>> You received this message because you are subscribed to the Google > > >>>> Groups > > >>>> "Algorithm Geeks" group. > > >>>> To post to this group, send email to algoge...@googlegroups.com. > > >>>> To unsubscribe from this group, send email to > > >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > >>>> . > > >>>> 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 algoge...@googlegroups.com. > > >>> To unsubscribe from this group, send email to > > >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > >>> . > > >>> 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 algoge...@googlegroups.com. > > >> To unsubscribe from this group, send email to > > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > >> . > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > > licheng > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > Regards, > > Ankit Babbar > > BE-IVth yr, > > Computer Science, > > Thapar University, > > Patiala.- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
