2. (16 pts.) Divide-and-Conquer An array A[1...n is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form "is Ali] > Aj}?" (Think of the array elements as GIF files, say.) However you can answer questions of the form: "is Ali = A[y]?" in constant time. Design a dynamic programming algorithm to solve this problem in O(nlogn) time. You may assume that n is a power of two. (Hint: the divide step is simple: just split the array into the left half and right half. How does knowing the majority elements (if they exist) of the two halves help you figure out the majority element in the whole array? Consider all the possibilities.) (a) Describe the algorithm, either in pseudo-code or English. (b) Argue why your algorithm is correct (e) Do a running time analysis of your algorithm. 1. There is a typo in problem 2. Where it says "dynamic programming" it should say "divide and conquer" 2. For problem 2, parts c and d, you can assume that the graph is undirected. We will accept any solution that uses directed graphs though