A visitor at a political convention with n delegates So I have been asked to specifically construct a divide and conquer algorithm for the question:
&quot;You  are  a  visitor  at  a  political  convention  with n delegates;  each  delegate  is  a  member  of exactly one political party.  It is impossible to tell which political party any delegate belongs to;  in  particular,  you  will  be  summarily  ejected  from  the  convention  if  you  ask.   However,you can determine whether any pair of delegates belong to the same party or not simply by introducing  them  to  each  other—members  of  the  same  party  always  greet  each  other  with smiles  and  friendly  handshakes;  members  of  different  parties  always  greet  each  other  with angry stares and insults.
Suppose more than half of the delegates belong to the same political party.  Describe an  efficient  algorithm  that  identifies  all  members  of  this  majority  party.   How  many introductions do you need?
So I came up with the pseudocode:
AMajorityPolitician(set of politicians S):

 if |S| == 1 :
  return S
 L = AMajorityPolitician(half of S)
 R = AMajorityPolitician(other half of S)

 if party[first item in L] == party[first item in R]:
  return L U R
 else
  return max(|L|,|R|)

AllMajorityPolititians(set S of n politicians):

 M = AMajorityPolitician(S)

 first = first item of M

 ans = {first}
 for each p in S:
   if first smiles to p:
     ans = ans U {p}

 return ans

But I don't think this works because if I have a list of politicians parties such as: 2,2,1,1,1 and it is split s.t. L=2,2,1 and R=1,1 then majority of L is party 2 of size 2 and majority of R is party 1 of size 2 so algorithm could pick 2 as the majority.
But I don't really know where to go from here to fix it. Do you guys have any suggestions?
You need to make sure what is returned from AMajorityPolitician(set of politicians S) is indeed a politician from the majority in S if there is a majority.
To ensure majority, we need to count the number of politicians who are in the same party as the chosen one. Here is the simple routine.
def number_of_friendly_politicians(person, all_people):
    count = 0
    for p in all_people:
        if smiles_between(person, p):
            count ++;
    return count


Now refactor AMajorityPolitician to the following function, which returns a majority politician in politicians whenever there is a majority.
def a_majority_politician(politicians):
    if size(politician) is 1:
        return that person

    L = a_majority_politician(half of politicians)
    R = a_majority_politician(other half of politicians)

    if number_of_friendly_politicians(L, politicians) * 2 &gt; size(politicians):
       return L
    else:
       return R    # R may or may not in a majority.