Review Problems P1. Let X be an array of N double's, so that the product of the elements in any NONEMPTY, contiguous subarray of X is well-defined. Describe a divide-and- conquer algorithm for finding the largest such product. For example, with I: 0 1 2 3 4 5 6 7 8 9 X[I]: 3 -.1 4 -1 -5 -.9 2 -6 .5 0 the answer is 216 (corresponding to the subarray X[2..7]). Explain why your algorithm works as well as how. (See Chapter 8 from Bentley.) Note: In some cases a problem must be embedded in a larger problem before divide- and-conquer or dynamic programming can be applied. For example: * There is no D&C algorithm for finding the second largest element in an array since you cannot easily find that element given the second largest elements in the left and right halves of the array. However, you can use divide-and-conquer to find both the largest and the second largest. * Bentley's scanning algorithm finds both the largest subset sum and the largest subset sum that includes the last element in the array. When you embed the problem to be solved into a larger one, you must identify the latter explicitly in your solution. P2. Describe a dynamic programming algorithm for solving Problem P1. P3: An upper triangular matrix A = [a(i,j)] is one where a(i,j) = 0 for i < j: [ a(1,1) a(1,2) a(1,3) . . . a(1,n) ] [ a(2,2) a(2,3) . . . a(2,n) ] [ a(3,3) . . . a(3,n) ] A = [ . . ] [ . . ] [ . . ] [ a(n,n) ] Design a scheme for storing such a matrix in a one-dimensional, 0-based array B. To save storage, entries below the diagonal (which are always zero) should not be stored. To facilitate access by rows, entries on and to the right of the diagonal in each row should be stored contiguously. To avoid wasting space, each location in B should contain a unique element in the upper triangle. Your scheme should include an algorithm to compute where a(i,j) is stored given i and j. P4. Consider the problem of determining whether or not there are any duplicates in a collection of N pictures P[0], ..., P[N-1]. Give an adversary argument to show that any method that solves this problem by asking questions of the form "Is P[i] = P[j]?" must ask AT LEAST N(N-1)/2 questions in the worst case. That is, give an algorithm that an adversary can use to answer such questions (in a manner consistent with some problem) that forces any method to ask at least N(N-1)/2 questions before it can determine whether there are any duplicates; and explain why it works. P5. Describe an algorithm for sorting a list of N integers using two stacks and O(1) additional integer variables. Assume that * Initially all of the N integers are in one of the stacks. * After sorting they are all in one of the stacks in sorted order (either increasing or decreasing). * The O(1) additional integer variables can hold any of the integers being sorted and any index value with magnitude at most N. * The only operations on a stack are push(), pop(), and isEmpty(). Full credit for an algorithm that requires at most N + N*(N+1)/2 pushes; 2/3 credit for one requiring more pushes but still only O(N*N); and 1/3 credit for one that requires even more pushes. Explain why your algorithm works as well as how. Hint: N*(N+1)/2 = 1 + 2 + 3 + ... + (N-1) + N. Note: You must pop an item from the stack to compare it. CS-223-02/20/19