@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 <[email protected]> wrote:
> 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%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 [email protected].
> >>> To unsubscribe from this group, send email to
> >>> [email protected]<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 [email protected].
> >> To unsubscribe from this group, send email to
> >> [email protected]<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 [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.- 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 [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.
