0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ An easier but different approach would be adapting the Boyer–Moore majority vote algorithm. Consider each politician actually represents their party. An introduction between two of them will decide whether they represent the same party. $\endgroup$
    – John L.
    Apr 9, 2021 at 18:39
  • $\begingroup$ Please credit the original source of all copied material. $\endgroup$
    – D.W.
    Apr 10, 2021 at 1:54
  • $\begingroup$ the question is from a uni practise sheet and the attempted pseudocode is my own $\endgroup$
    – pk00
    Apr 10, 2021 at 16:26

1 Answer 1

0
$\begingroup$

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 > size(politicians):
       return L
    else:
       return R    # R may or may not in a majority.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.