So I have been asked to specifically construct a divide and conquer algorithm for the question:
"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?