For this problem consider the problem of finding the maximum element in a list of integers. Maximum Integer in a List (MAX) Input: A list of integers A [a...b]. Output: A [i] for some a lessthanorequalto i lessthanorequalto b such that A [i] greaterthanorequalto A [i] for all a lessthanorequalto j lessthanorequalto b. Let M (A [a...b]) represent the output of the MAX problem on input A [a...b]. Let Max (a, b) be a simple function that returns the maximum of two elements. Let m = [a + b/2] be the midpoint between a and b. Using the same reduction as part 3 now state a recurrence T (n) that expresses the worst case run time of the recursive algorithm. Find a similar recurrence in your notes and state the tight bound on T (n) (you do not need to prove this bound). For this problem consider the problem of finding the sum of a list of integers. Sum of All Integers in a List (SUM) Input: A list of integers A [a...b]. Output: s = sigma^b_i = a A [i]. Let S (A |a...b]) represent the output of the SUM problem on input A [a...b]. State two different self-reductions for the SUM problem. Use the self-reduction examples from lecture as a guide. Give recursive algorithms based on your divide and conquer self-reductions to solve the SUM problem. What are the worst case runtimes of the solutions you have generated. (Just state the runtimes. You do not need to show your work.)