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