You are at a political convention with n delegates, each one a member of exactly

ID: 3566239 • Letter: Y

Question

You are at a political convention with n delegates, each one a member of exactly one political party. The number of parties may be greater than 2. It is impossible to tell which political party any delegate belongs to; in particular, you will be summarily ejected if you ask. However, you can determine whether any two delegates belong to the same party or not by introducing them to each other - members of the same party always greet each other with smiles and friendly handshakes: members of different parties always greet each other with angry stares and insults. Suppose that a majority (strictly more than half) of the delegates are from the same political party. Describe an algorithm that identifies a member (any member) of the majority party using only 0(n log n) introductions.

Explanation / Answer

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

=> let we have an n members where more than n/2 persons belong to a party, let us consider an array of n persons.split this array in two halves and call the function recursively on these array same as merge sort.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.

Running Time:
To analyze the running time, we can rst 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.
               = O(n log n).

Navigate

You are at a party playing a game of “spin the bottle” when you notice an insect

You are at a race track with special rules. The race is over a distance L, but y

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

You are at a political convention with n delegates, each one a member of exactly

Question

Explanation / Answer

Related Questions

Navigate