5. 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. You are not allowed to use sorting, because you cannot compare two elements (say GIF files). But, you can ask questions of the form "s AA?". Show how to solve this problem in O(n log n) time. (Hint: Split the array A into two arrays Ai and A2 of half the size. Does knowing the majority elements of A and A2 help you figure out the majority element of A? If so, you can use a divide-and-conquer approach.) 6. Suppose you were to drive from St. Louis to Denver along I-70. Your gas tank, when full, holds enough gas to travel m miles, and you have a map that gives distances between gas stations along the route. Let di