Answer any 7 of the given 8 questions. Each problem carries 20 points. Thus, the total points is 140 1. i Give a tight (00) bound for the function T(n) 5n34log10n10. Explain why your bound is tight (prove the upper O0 and the lower 20 bound) (in3 log n)? Explain why 2. Find out a good guess (a good upper bound) for the solution of the following recurrence relation using the recursion tree method. Draw the recursion tree and show how the total cost over all levels is bounded by your guess. T(n) 5T(n/4) +n, T(1)-1 Verify that your guess is correct using the substitution method. 3. Solve the following recurrence relations using the Master's method if possible. If not possible mention why the method cannot be applied. (i) T(n) 9T(n/3) + n2 () T(n) - 4T(n/2)g 4. You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Write an algorithm to remove all duplicates from the array in time O (n log n) Example: For the array 14,7,9,7, 1,9,1,13], the output should be 14,7,9,1, 13] 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