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.
