How can does the maximum vote algo apply to the above question..?? please explain..
On 11/8/10, cheng lee <[email protected]> wrote: > Where can we see that this algorithm use the divide and conquer techniques? > > > > > 2010/11/7 Pratik Bhadkoliya <[email protected]> > >> 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 >> <[email protected]>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 >>> <[email protected]>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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[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]<algogeeks%[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]<algogeeks%[email protected]> >> . >> 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 [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. > > -- Regards, Ankit Babbar BE-IVth yr, Computer Science, Thapar University, Patiala. -- 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.
