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) Give a O(n) algorithm

Explanation / Answer

A (n log n) running time divide and conquer algorithm:

The algorithm begins by splitting the array in half repeatedly and calling itself on each half. This
is similar to what is done in the merge sort algorithm. When we get down to single elements, that
single element is returned as the majority of its (1-element) array. At every other level, it will get
return values from its two recursive calls.
The key to this algorithm is the fact that if there is a majority element in the combined array,
then that element must be the majority element in either the left half of the array, or in the right
half of the array.

There are 4 scenarios:

1. Both return “no majority.” Then neither half of the array has a majority element, and the
combined array cannot have a majority element. Therefore, the call returns “no majority.”
2. The right side is a majority, and the left isn’t. The only possible majority for this level is with
the value that formed a majority on the right half, therefore, just compare every element in
the combined array and count the number of elements that are equal to this value. If it is a
majority element then return that element, else return “no majority.”
3. Same as above, but with the left returning a majority, and the right returning “no majority.”
4. Both sub-calls return a majority element. Count the number of elements equal to both of the
candidates for majority element. If either is a majority element in the combined array, then
return it. Otherwise, return “no majority.”

The top level simply returns either a majority element or that no majority element exists in the same way. To analyze the running time, we can first see that at each level, two calls are made recursively with each call having half the size of the original array. For the non-recursive costs, we can see that at each level, we have to compare each number at most twice (which only happens in the last case described above). Therefore, the non-recursive cost is at most 2n comparisons when the procedure is called with an array of size n. This lets us upper bound the number of comparisons done by T(n) defined by the recurrence

T(1) = 0 and T(n) = 2T(n/2) + 2n.

We can then determine that T(n) (n log n) as desired using Case 2 of the Master Theorem.

A (n) running time algorithm:

We simply sketch the algorithm and analysis here, these are not complete proofs. The following
algorithm is based on two ideas. First, if array A has a majority element, and elements A[i] and A[j]
are different, then the new array created by discarding both A[i] and A[j] has the same majority
element as A. Second, if A has a majority element and every element in A occurs in pairs, then after
deleting one of each pair and keeping the other, we get a new array with the same majority element.
The only tricky part is that if A has an unpaired element, then we must keep it, but weight it less
than the other elements when determining the majority element.

MajGuess(A,n,part) -- returns the majority element of A if one exists
-- could return anything if no majority element exists
-- parameter ‘‘part’’ is a boolean which is true
-- if A[n] has less ‘‘weight’’ than the other elements.
if n=0 then return null; -- there is no majority element
if n=1 then return A[1]; -- it is the majority element
i := 1 -- place in A[]
j := 1 -- first empty position in new array

while i<n-1 do
if A[i]=A[i+1] then
B[j] = A[i]; -- find matching pairs, through out unmatched pairs
j := j+1;
i := i+2; -- move to next pair

-- now i is either n or n-1
if i = n then
B[j] := A[n];
part := true; -- the last element counts for less than the others
else -- i = n-1
if part then
B[j] = A[n-1]
else -- not part
if A[n-1] = A[n] then
B[j] = A[n-1];
else
j = j-1; -- A[n-1] different from A[n] and they cancel
return MajGuess (B, j, part);

Now to determine if array A of n elements has a majority element, we call MajGuess(A, n,false), and get an element (or null). We then check this answer by counting how many times it occurs in the actual array A[1..n].

The total number of tests done by MajGuess is bounded by T(n) having the recurrence:

T(0) = T(1) = 0 and T(n) = T(bn/2c) + n/2.

The master theorem indicates that T(n) (n). Since only an additional n comparisons are done at the end, the entire number of comparisons done by this method is in (n).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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