Question

You are a visitor at a political convention with 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.
Required:
Suppose more than half of the delegates belong to the same political party. Design a divide and conquer algorithm that identifies all member of this majority party and analyze the running time of your algorithm.

Answer 1

Answer:

The algorithm is as follows:

Step 1: Start

Step 2: Parties = [All delegates in the party]

Step 3: Lent = Count(Parties)

Step 4: Individual = 0

Step 5: Index = 1

Step 6: For I in Lent:

Step 6.1: If Parties[Individual] == Parties[I]:

Step 6.1.1: Index = Index + 1

Step 6.2: Else:

Step 6.2.1 If Index == 0:

Step 6.2.2: Individual = I

Step 6.2.3: Index = 1

Step 7: Else

Step 7.1: Index = Index - 1

Step 8: Print(Party[Individual])

Step 9: Stop

Explanation:

The algorithm begins here

Step 1: Start

This gets the political parties as a list

Step 2: Parties = [All delegates in the party]

This counts the number of delegates i.e. the length of the list

Step 3: Lent = Count(Parties)

This initializes the first individual you come in contact with, to delegate 0 [list index begins from 0]

Step 4: Individual = 0

The next person on the list is set to index 1

Step 5: Index = 1

This begins an iteration

Step 6: For I in Lent:

If Parties[Individual] greets, shakes or smile to Party[i]

Step 6.1: If Parties[Individual] == Parties[I]:

Then they belong to the same party. Increment count by 1

Step 6.1.1: Index = Index + 1

If otherwise

Step 6.2: Else:

This checks if the first person is still in check

Step 6.2.1 If Index == 0:

If yes, the iteration is shifted up

Step 6.2.2: Individual = I

Step 6.2.3: Index = 1

If the first person is not being checked

Step 7: Else

The index is reduced by 1

Step 7.1: Index = Index - 1

This prints the highest occurrence party

Step 8: Print(Party[Individual])

This ends the algorithm

Step 9: Stop

The algorithm, implemented in Python is added as an attachment

Because there is an iteration which performs repetitive operation, the algorithm running time is: O(n)

Download txt