Question

You are a visitor at a political convention (or perhaps a faculty meeting) 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 and analyze an efficient algorithm that identifies a member of this majority party

Answer 1

Algorithm

Step 1: Start

Step 2: create function handshake(delegate 1, delegate 2, array1, array2)

if smile then

push( delegate 1) in array1

else

push(delegate 2) in array2

Step 3: for i < n do

handshake(delegate[0], delegate[ i+1], array1, array2)

  i <- i + 1

end of foor loop

Step 4: check  size of array1

if size of array1 > n/2

then print values of array 1 as "members of majority party"

else

discard array1

and repeat Step 3 with array2 as the input array

for i < size of array2 do

handshake(array2[0], array2[i+1], array1, array2)

i <- i + 1

end of foor loop

repeat Step 4

Step 5: End