1. You are tallying votes from an election in which n people voted. If any candi
ID: 3663339 • Letter: 1
Question
1. You are tallying votes from an election in which n people voted. If any candidate gets more than half (at least bn/2c + 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) Give a O(n) algorithm
2. You are a gambler who’s finally figured out how to make it big! You’ve discovered that the local bar turns off its slot machine at night, thus reseting its random number generator. The machine can be played at most n times in a single day and after showing up at the bar several times you have finally figured out completely the pattern of payouts. That is, for each integer k {1, 2, . . . , n} you know the payout A[k] of the k-th pull (which can be negative, reflecting the cost of playing). You have one shot to pull this off - you’ve watched enough movies to know that if you do this more than once you’ll get caught. So, you want to figure out the maximum amount of money you can earn in a single sitting. That is, you you want to find 1 i j n that maximize X j k=i A[k] . (1) Example: If A = [4, 5, 6, 7, 8, 10, 5], the solution is i = 3 and j = 5 (as 6 + 7 + 8 = 21). To design an efficient algorithm, we consider two related problems. For a given integer l, the l-LGAIN problem asks for j {l, l + 1, . . . , n} maximizing X j k=l A[k] . (2) Similarly, for a given integer r, the r-RGAIN problem asks for i {1, 2, . . . , r} maximizing Xr k=i A[k] . (3) Example: If A = [4, 5, 6, 7, 8, 10, 5], the solution of 4-LGAIN is j = 5 (as 7+8=15) and the solution of 7-RGAIN is i = 3 (as 6 + 7 + 8 10 + 5 = 16).
(a) Describe O(n) time algorithms for solving l-LGAIN and r-RGAIN (for given l and r). 1
(b) Given a O(n) time algorithm for l-LGAIN describe a simple O(n 2 ) algorithm for the gambler’s problem.
(c) Given O(n) time algorithms for l-LGAIN and r-RGAIN describe an O(n log n) divide-andconquer algorithm for the gambler’s problem.
Explanation / Answer
Use the Quick Sort technique
Take two ballots randomly and test it. Test it with different piles so that no candidate
can have more then n/2 of the votes. Sometimes 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 expected one of these piles are larger than other. Therefore in this test if result is more than half, then we can pick who was the winner.
b) If we grab an arbitrary ballot and then compare it against other ballot a total of (n-1) tests.
Since we are comparing one with other so it will be (n-1) .
We can easily find how many people voted for the 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 the ballots
resultant total = (n/2 -1) + (n/2 -1) +1
= (n-1) tests.
This takes O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.