Certain country in the Caribbean Sea recently held an election to choose its president. Every vote...

 

Transcribed Image Text:

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. 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.