You have a collection of n objects and you want to determine if there is a majority value among them -- a value that appears (strictly) more than n/2 times among the input. You have the ability to determine if two items are equal or not: Given two items a and b, ARE_EQUAL(a,b) evaluates to true or false accordingly (and takes constant time). You cannot test if one is less than the other (unlike comparison-based sorting).. QUESTION A (10 points): Devise a (nlogn) time divide-and-conquer algorithm to determine if a given collection of n such items and determines if there is indeed a majority among them (and if so reports the majority element) Framework: think of your algorithm in terms of a function which takes a collection of items and: returns the majority element x if there is a majority returns NULL (1.e., a value that can be distinguished from all given "items") if there is no majority. As always, you must argue/explain the correctness of your approach. Suggestions: think in terms of the merge-sort framework. Consider the possible cases. In the recursive case, let c be the given collection and split it into ci and c2 (of equal size - or as close as possible). Think of the different possibilities with respect to c, ci and c2: Collection Has a majority Does not have a majority let x be the majority element (we return x) no such x exists (we return NULL) let y be the majority element of ci (y returned from recursive call) no such y exists (recursive call returns NULL) let z be the majority element of C2 (returned from recursive call) no such z exists (recursive call returns NULL) Think carefully about the different possibilities. For example, here are some interesting questions "Suppose c does have a majority element x; is it possible that neither ci nor c2 have majority elements?" Suppose both ci and c2 have majority elements, does that imply that c must also have a majority element?" Now that you hopefully have figured out an O(nlog n) time algorithm, can we do even better? Below is an idea for the start of) an algorithm to determine if there is a majority element and if so, what that element is. ASSUMPTION: Let us assume that n is even: n = 2k for some integer k] Initialize two "piles" DISCARD and CANDIDATES to be empty. Pair up the n objects and make = k equality tests. For each such test: If the items are equal, place one of them in the CANDIDATES pile and the other in the DISCARD pile If the items are not equal, put both of them in the DISCARD pile. (B-G: 20 points) [For B-F, you assume (as above) that n is even and also that the number of candidates after the process above is also even] QUESTION B: After this process, what is the largest the CANDIDATES pile can be? Give your rationale. QUESTION C: Argue that if x is a majority element among the given n objects then x is also a majority element among CANDIDATES after the above process. Note that there can be only one majority element since it must occur strictly more than n/2 NOTE: once you have shown this property, you also know its contrapositive: If there is no majority element among CANDIDATES, then there is no majority element among the given n items. QUESTION D: (the converse of C) suppose there is a majority element y among CANDIDATES, does this necessarily imply that y must also be a majority of the given n elements? QUESTION E: Now, put all of this together by describing an alternate divide-and-conquer algorithm for the problem. The algorithm/function (as previously) returns the majority element x if there is one and NULL if there is no majority You may assume the process described above is available to you as a subroutine populating the DISCARD and CANDIDATES piles. ASSUMPTION: in addition to assuming that n is even, also assume that the resulting number of candidates is also even (presumably as the input to a recursive subproblem). Yes, this is an unrealistic assumption and results in a useless algorithm... but we will try to fix it in the end. QUESTION F: Show that your resulting algorithm is linear time. QUESTION G: Can you "patch" the algorithm so that we don't have to assume that the number of elements is always even (both initially and in sub-problems)? Some thoughts: notice that in the odd case, one of the elements will not participate in a pairwise equality test; as a result, the implication in QUESTION C above no longer holds in general: figure out why and analyze the different possible cases. You have a collection of n objects and you want to determine if there is a majority value among them -- a value that appears (strictly) more than n/2 times among the input. You have the ability to determine if two items are equal or not: Given two items a and b, ARE_EQUAL(a,b) evaluates to true or false accordingly (and takes constant time). You cannot test if one is less than the other (unlike comparison-based sorting).. QUESTION A (10 points): Devise a (nlogn) time divide-and-conquer algorithm to determine if a given collection of n such items and determines if there is indeed a majority among them (and if so reports the majority element) Framework: think of your algorithm in terms of a function which takes a collection of items and: returns the majority element x if there is a majority returns NULL (1.e., a value that can be distinguished from all given "items") if there is no majority. As always, you must argue/explain the correctness of your approach. Suggestions: think in terms of the merge-sort framework. Consider the possible cases. In the recursive case, let c be the given collection and split it into ci and c2 (of equal size - or as close as possible). Think of the different possibilities with respect to c, ci and c2: Collection Has a majority Does not have a majority let x be the majority element (we return x) no such x exists (we return NULL) let y be the majority element of ci (y returned from recursive call) no such y exists (recursive call returns NULL) let z be the majority element of C2 (returned from recursive call) no such z exists (recursive call returns NULL) Think carefully about the different possibilities. For example, here are some interesting questions "Suppose c does have a majority element x; is it possible that neither ci nor c2 have majority elements?" Suppose both ci and c2 have majority elements, does that imply that c must also have a majority element?" Now that you hopefully have figured out an O(nlog n) time algorithm, can we do even better? Below is an idea for the start of) an algorithm to determine if there is a majority element and if so, what that element is. ASSUMPTION: Let us assume that n is even: n = 2k for some integer k] Initialize two "piles" DISCARD and CANDIDATES to be empty. Pair up the n objects and make = k equality tests. For each such test: If the items are equal, place one of them in the CANDIDATES pile and the other in the DISCARD pile If the items are not equal, put both of them in the DISCARD pile. (B-G: 20 points) [For B-F, you assume (as above) that n is even and also that the number of candidates after the process above is also even] QUESTION B: After this process, what is the largest the CANDIDATES pile can be? Give your rationale. QUESTION C: Argue that if x is a majority element among the given n objects then x is also a majority element among CANDIDATES after the above process. Note that there can be only one majority element since it must occur strictly more than n/2 NOTE: once you have shown this property, you also know its contrapositive: If there is no majority element among CANDIDATES, then there is no majority element among the given n items. QUESTION D: (the converse of C) suppose there is a majority element y among CANDIDATES, does this necessarily imply that y must also be a majority of the given n elements? QUESTION E: Now, put all of this together by describing an alternate divide-and-conquer algorithm for the problem. The algorithm/function (as previously) returns the majority element x if there is one and NULL if there is no majority You may assume the process described above is available to you as a subroutine populating the DISCARD and CANDIDATES piles. ASSUMPTION: in addition to assuming that n is even, also assume that the resulting number of candidates is also even (presumably as the input to a recursive subproblem). Yes, this is an unrealistic assumption and results in a useless algorithm... but we will try to fix it in the end. QUESTION F: Show that your resulting algorithm is linear time. QUESTION G: Can you "patch" the algorithm so that we don't have to assume that the number of elements is always even (both initially and in sub-problems)? Some thoughts: notice that in the odd case, one of the elements will not participate in a pairwise equality test; as a result, the implication in QUESTION C above no longer holds in general: figure out why and analyze the different possible cases