Question

Certain country in the Caribbean Sea recently held an election to choose its president. Every vote cast was electronic, but unfortunately, a recent power surge caused a malfunction in the system just before votes were counted. The only information saved consists of the following facts: • All the N citizens casted their vote. • Exactly one candidate received more than N/2 votes. • We don’t know how many candidates there were. You are hired to help using your expertise in algorithms. But you can only work with the local resources. As a result, you have access to a function Agree(X, Y ) which returns True if X and Y cast a vote for the same candidate, and returns False otherwise. You are not told the identity of the candidate! Design a Divide and Conquer algorithm that finds a single ballot that voted for the winning candidate. You may assume that every call of Agree(X, Y ) runs in constant time.

Answer 1

Answer:

Certain country in the Caribbean Sea recently held an election to choose its president. Every vote cast was electronic, but unfortunately, a recent power surge caused a malfunction in the system just before votes were counted. The only information saved consists of the following facts:

Explanation:

• All the N citizens casted their vote.

• Exactly one candidate received more than N/2 votes.

• We don’t know how many candidates there were.

You are hired to help using your expertise in algorithms.