Suppose you have an unsorted array A[1..n] of elements. You can only do equality tests on...

  

Transcribed Image Text:

Suppose you have an unsorted array A[1..n] of elements. You can only do equality tests on the elements (e.g. they are large GIFs). In particular this means that you cannot sort the array. You want to find (if it exists) a majority element, i.e., an element that appears more than half the time. For example in [a, b, a] the majority element is a, but [a,b,c] and [a, a, b, c] have no majority element. Straightforward approach of checking if A[i] is a majority element for all i = 1,...,n will have run-time in O(n) which is too slow. Consider the following approach to finding a majority element: recursively find the majority element y in the first half of the array and the majority element z in the second half of the array, and combine results of recursive calls into the answer to the problem. (a) Prove that if x is a majority element in A then it has to be a majority element in the first half of the array or the second half of the array (or both). (b) Using observation of part (a) give a divide-and-conquer algorithm to find a majority element, that runs in time O(nlogn). Detailed pseudocode is required. Be sure to argue correctness and analyze the run time. If given array has no majority element, return FAIL. Suppose you have an unsorted array A[1..n] of elements. You can only do equality tests on the elements (e.g. they are large GIFs). In particular this means that you cannot sort the array. You want to find (if it exists) a majority element, i.e., an element that appears more than half the time. For example in [a, b, a] the majority element is a, but [a,b,c] and [a, a, b, c] have no majority element. Straightforward approach of checking if A[i] is a majority element for all i = 1,...,n will have run-time in O(n) which is too slow. Consider the following approach to finding a majority element: recursively find the majority element y in the first half of the array and the majority element z in the second half of the array, and combine results of recursive calls into the answer to the problem. (a) Prove that if x is a majority element in A then it has to be a majority element in the first half of the array or the second half of the array (or both). (b) Using observation of part (a) give a divide-and-conquer algorithm to find a majority element, that runs in time O(nlogn). Detailed pseudocode is required. Be sure to argue correctness and analyze the run time. If given array has no majority element, return FAIL.