Question 1 (2 points) Use substitution method to prove that T (n) = 87 () + n2 = 0(n?) Hint: You can minus a lower order term if the usual mathematical induction does not work. Question 2 (4 points) Consider the searching problem: Input: A sequence of n numbers A = (a1, A2,.., an) and a value v. Output: An index i such that v = A[i] or the special value NIL if v does not appear in A. a) Write the pseudocode for linear search, which scans through the sequence, looking for v. State the asymptotic bound of its running time, and briefly explain why. b) If the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write the pseudocode for binary search, either iterative or recursive. c) Write the recurrence of binary search algorithm, and then use master theorem to find its solution. Question 3 (3 points) Observe the following recurrences, use master theorem to solve those that can be solved. For those that cannot be solved directly, try to devise some guess of the solution, and then use substitution method to prove your guess. a) T(n) = 4T () + n lg n. b) T(n) = 4T (%) + n1n. c) T(n) = T (%) + T 1 (5) + +7 (3) + n. Question 4 (3 point) Draw a recursion tree for the recurrence T(n) = T(n a) +T(a) + cn. Assume T(a) = T(1) = (1). Observe the per-level cost of the tree, and then come up with a guess for the solution of the total cost. Prove the solution using substitution method. Question 5 (3 point) In fact, we can do better than the divide-and-conquer approach for the maximum subarray problem. User the following ideas to develop a non-recursive, linear-time algorithm for the maximum- subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j], extend the answer to find a maximum subarray ending at index j + 1 using the following observation: a maximum subarray of A[i..j + 1] is either a maximum subarray of A[1..j] or a subarray A[i..j +1], for some 1 sisj + 1. Finding a maximum subarray of A[i.. j + 1] can be done in constant time, because we already know the maximum subarray of A[1..j]. Please write down the pseudocode