You are tallying votes from an election in which n people voted. If any candidat

Question

You are tallying votes from an election in which n people voted. If any candidate gets more than half (at least n/2 + 1 votes), they win. Otherwise a runoff election is needed. For privacy reasons you are not allowed to look at any one ballot, but you have a machine that can take any two ballots and answer the question: “are these two ballots for the same candidate, or no?”

(a) Design and analyze a divide and conquer algorithm that decides whether a runoff is needed after O(n log n) ballot equality tests, assuming that n = 2k for some integer k.

(b) Explain how to modify your algorithm from (1a) to deal with arbitrary n.

(c) Extra Credit (10 points) Give a O(n) algorithm.

Explanation / Answer

a)
Firstly I want to deal with quick sort technique.
Take two ballots randomly and test it. Test with different piles so that no candidate
can have more then n/2 of the votes. If we are lucky all votes end up there we are done.

So while testing we can get that votes are belonging to one candidate or not. So consider one
ballot and divide and compare into same candidate and different pile. So we can get expect one
of these piles are larger than other. In this test.. if result is more than half, then we can
pick up , who was the winner.

b) If we grab an arbitary ballot and then comapring against other ballot a total of (n-1) tests.
Since we are comparing one with other.. so (n-1) .
We can easily found that hoe many voted for same candidate. This takes O(n)
c)
If we take ballots and divide then in half, you can carry with (n/2 -1) tests.
So from both ballots , resultant total = (n/2 -1) + (n/2 -1) +1 = (n-1) tests. This takes O(n)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.