Problem 1:
1. 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 ≤ i ≤ b such that A[i] ≥ A[j] for all a ≤ j ≤ 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, let t1 = [a+b/3] be the point one third of the distance from a to b, and let t2 = [2(a+b)/3] be the point two thirds of the distance from a to b.
1. Below is a self-reduction for the MAX problem. State a recursive algorithm using pseudocode for finding the maximum element based on this self-reduction.
M (A[a . . . b]) = A(a) if a =b
max(A[a], M (A[a + 1 . . . b])) if a < b
2. Using the same reduction as part 1 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).
3. Below is a self-reduction for the MAX problem. State a recursive algorithm using pseu- docode for finding the maximum element based on this self-reduction.
M (A[a . . . b]) = -∞ if a > b
A[a] if a = b
max(M (A[a . . . t1]), max(M (A[t1 + 1 . . . t2]), M (A[t2 + 1 . . . b]))) if a < b
4. Using the same reduction as part 3 now state a recurrence T (n) that expresses the worst case run time of the recursive algorithm. You do not need to formally prove your recurrence, but you have to show that it is a reasonable guess by using a recursion tree or by the repeated substitution method. Hint: assume that n is a power of 3.
Problem 2:
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 = i=a∑b A[i].
Let S(A[a . . . b]) represent the output of the SUM problem on input A[a . . . b].
1. State two different self-reductions for the SUM problem. Use the self-reduction examples from the lectures as a guide.
2. Give recursive algorithms based on your divide-and-conquer self-reductions to solve the SUM problem.
3. What are the worst-case runtimes of the solutions you have generated. (Just state the runtimes. You do not need to show your work.)
Problem 3:
Consider the following recurrence T (n):
T(n) = c if n = 1
T [n/2] + T(|n/4|) + 4n if n > 1
1. Use the recursion tree or repeated substitution method to come up with a good guess for a bound g (n) on the recurrence T (n).
2. State and prove by induction a theorem showing T (n) ∈ O(g (n)).
3. State and prove by induction a theorem showing T (n) ∈ ?(g (n)).
Consider the following recurrence T (n):
T (n) = c if n = 1
T ([n/2]) + T ([n/4]) + 4n if n > 1
1. Draw the first six levels of the recursion tree by drawing all recursive calls of the same size on the same level. Make sure on each level you indicate the size of the recursive call and the number of recursive calls.
2. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion tree.
3. Give a function g (n) and show it is an upper bound on the sum.
4. State and prove by induction a theorem showing T (n) ∈ O(g (n)).
5. State and prove by induction a theorem showing T (n) ∈ ?(g (n)).
Problem 4:
CHALLENGE
Consider the following observation on the randomized Quicksort algorithm. Because the pivot is chosen uniformly at random among the n input element, with probability 1/2 the chosen pivot's position on the sorted list will be between n/4 and 3n/4 (i.e. a good pivot), and with probability 1/2 the chosen pivot's position on the sorted list will be between 1 and n/4 or between 3n/4 and n (i.e. a bad pivot).
1. State a recurrence that expresses the worst case for bad pivots.
2. State a recurrence that expresses the worst case for good pivots.
3. State a recurrence that expresses the expected worst case by combining the first two recurrences.
4. Prove by induction that your recurrence is Θ(n log n).