I. Two Sample Problems in Analysis A. Maximum contiguous subsequence sum 1. References a. see the Weiss textbook, pages 113-120 2. Getting Weiss' code a. the code from the text is available at the following URL: b. http://www.cs.fiu.edu/~weiss/dsj/code/Chapter05/MaxSumTest.java 3. Problem specification a. Given: a (one-dimensional) array A of integers, of length n c. Find: the start and end indices and sum value for that subsequence A[i] ... A[j] which has the maximum sum relative to all such (contiguous) subsequences 4. Special cases I a. clearly the problem degenerates when there are no negative entries in the array b. why? 5. Special cases II a. Another degenerate case is when all the items in the array are negative b. what should the answer be in this case? B. A naive solution 1. Compute (and store) sum for each subsequence a. we can use an n x n array sum to store the values for the sums of all possible subsequences from A[i] to A[j], putting the value in the cell sum[i,j] b. what part of the array will we fill in? 2. Finding the result a. to return the correct answer, we need only fill in the array,then search it for the maximum value b. what is the asymptotic running time for this approach (in O notation)? 3. Keeping a running maximum a. we can eliminate the search by keeping and updating a "current maximum value" as we fill in the array b. does eliminating this (inefficient) search help our asymptotic running time? 4. Cutting down on space a. once we use a running maximum, we need not actually build the array b. does eliminating the array of maxima help our asymptotic space usage? c. what other "running values" do we need to keep track of? 5. Code for the naive algorithm (cubic) a. example /** * Cubic maximum contiguous subsequence sum algorithm. * seqStart and seqEnd represent the actual best sequence. */ public static int maxSubSum1( int [ ] a ) { int maxSum = 0; for( int i = 0; i < a.length; i++ ) for( int j = i; j < a.length; j++ ) { int thisSum = 0; for( int k = i; k <= j; k++ ) thisSum += a[ k ]; if( thisSum > maxSum ) { maxSum = thisSum; seqStart = i; seqEnd = j; } } return maxSum; } C. A better solution 1. A code-based view of the problem a. the cubic running time for the algorithm results from having three nested loops; if we can eliminate one loop, we can bring the time down to quadratic 2. An intuitive view a. more intuitively, we can just notice that we are needlessly re-computing the values of some subsequences (i.e., those for which we then compute an "extended sum" given one new element) 3. Cutting out the repetition a. rather than compute a separate sum for each new value of j (given a fixed i), we can just update the sum by adding in A[j] b. what is our new asymptotic running time? 4. Code for the quadratic algorithm a. example /** * Quadratic maximum contiguous subsequence sum algorithm. * seqStart and seqEnd represent the actual best sequence. */ public static int maxSubSum2( int [ ] a ) { int maxSum = 0; for( int i = 0; i < a.length; i++ ) { int thisSum = 0; for( int j = i; j < a.length; j++ ) { thisSum += a[ j ]; if( thisSum > maxSum ) { maxSum = thisSum; seqStart = i; seqEnd = j; } } } return maxSum; } D. An even better solution 1. Negative-sum subsequences a. if the sum of a sub-sequence is negative, it cannot contribute to a good solution b. why? 2. Exploiting negative sums a. once we see a negative sum, we can skip the i counter forward, past the end of this subsequence 3. A single loop a. we can use a single loop by starting i out at 0 and updating it (moving it forward) only when necessary b. can we skip i forward "too far"? What information must we keep track of? 4. Best algorithm (linear) a. example /** * Linear-time maximum contiguous subsequence sum algorithm. * seqStart and seqEnd represent the actual best sequence. */ public static int maxSubSum3( int [ ] a ) { int maxSum = 0; int thisSum = 0; for( int i = 0, j = 0; j < a.length; j++ ) { thisSum += a[ j ]; if( thisSum > maxSum ) { maxSum = thisSum; seqStart = i; seqEnd = j; } else if( thisSum < 0 ) { i = j + 1; thisSum = 0; } } return maxSum; } E. Fibonacci numbers 1. References a. see the Weiss text, pages 183-185 2. Definition a. the Fibonacci sequence F is defined inductively as follows: F0 is equal to 0; F1 is equal to 1; Fn is equal to Fn-1 + Fn-2, otherwise 3. Motivations and connections a. Fibonacci originally defined this sequence to characterize the growth in size of rabbit populations; b. But there are enough other applications that a qurterly journal is devoted to the study of Fibonacci (and related) sequences 4. Straight-forward program for Fib(n) a. the value of the Fibonacci number Fn can be computed recrsively as follows: public static long fib(int n) { if (n <= 1) return n else return fib(n-1) + fib(n-2) } 5. Analyzing recursive calls a. the running time of recursive programs can be analyzed using recurrence equations; we will study these techniques in more depth when we develop divide-and-conquer algorithms (see the Weiss text, page 200 and following) 6. Time analysis for fib a. the time consumed in computing fib is clearly proportional to the number of calls made to fib; this turns out to grow exponentially in n, so that for n=40, over 300 million calls are made 7. Space analysis for fib a. the above implementation of Fibonacci never uses much space, since each call uses only a small amount of local memory, and the number of calls pending at any given time is bounded by n F. Improving the Fibonacci computation 1. Wasted effort a. clearly much of the effort in computing fib(n) is wasted for almost all values of n, since much information is being computed redundantly b. if 300 million calls are made for n=40, about how many times is fib(n) computed, on average, for each n between 0 and 40? 2. Filling in an array of results a. imagine that we wish to fill an array F[] with Fibonacci values, rather than just return a single result; now we can compute fib(n) by filling in the array from left to right, and then pluck out the last value b. what is the asymptotic running time of this algorithm for fib(n)? 3. Saving space with the sliding window a. rather than filling in the whole array, we can keep three local variables to maintain the values of the current and last two values, and thus simulate a "sliding window" of width three moving across the array b. what is the asymptotic space usage of this algorithm compared to the last one? 4. Caching the results (memoized version) a. on the other hand, it may be useful to use the array after all: if we will be serving requests for fib(n) for many values of n at different times, we can keep the array as computed so far, and then just look up the values if they have already been computed b. what are the asymptotic time and space usage this algorithm?