CSC152 2006S, Class 36: Dynamic Programming

Admin:
* Exam 2 distributed.
* The exam took much longer than I intended to prepare, so today's outline is much less detailed than I would like.
* EC for participating in some aspect of this weekend's African Student conference (e.g., Dance recital tonight).
* EC for attending baseball 1pm or 3pm Saturday
* EC for attending art/dance collaboration in two weeks
* Joke about Tutorial meeting today.

Overview:
* Multiply-recursive algorithms.
* The Fibonacci Numbers.
* Improving computation with dynamic programming.
* Another example: Efficient computation of prices.

Topic this week:
* Algorithm analysis
* Consider design issues that improve asymptotic running time
* Things we know
  * Reduce number of recursive calls
  * Write well
  * Remove stuff from loops, particularly slower stuff
  * DIVIDE AND CONQUER is a good general technique

f(n) = g(f(n-1), f(n-1))
f(n) = f(n-1) + f(n-1)

(define smallest
  (lambda (lst)
    (cond 
       ((null? (cdr lst)) (car lst))
       ((< (car lst) (smallest (cdr lst))) (car lst))
       (else (smallest (cdr lst))))))

running time is O(2^n)

Algorithms that behave this way need to be improved.
* Don't compute the recursive call twice; instead, assign it to a temp variable


(define smallest
  (lambda (lst)
    (cond 
       ((null? (cdr lst)) (car lst))
       (let ((tmp (smallest (cdr lst))))
         (cond
            ((< (car lst) tmp) (car lst))
            (else tmp))))))

Consider the Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21, ...


0th Fib # is 1
1st Fib # is 1
nth Fib # is (n-1)st Fib # + (n-2)nd Fib #

/**
 * Compute the nth Fibonacci number.
 * @pre
 *   n >= 0
 */
public static BigInteger fib(int n)
{
  // Base case
  if ((n == 0) || (n == 1)) {
    return BigInteger.ONE;
  }
  else {
    return fib(n-1).add(fib(n-2));
  }
} // fib(int)

This is likely to be *very* slow.  However, the two recursive
calls are different, so we can't use the strategy of a temp
variable.

One strategy: Create a table of Fibonacci numbers and look
up something in the table whenever we are asked to compute it

public static Vector<BigInteger> FIB = new Vector<BigInteger>();

public static BigInteger fib(int n)
{
  // Check the table
  if (FIB.get(n) != null) return FIB.get(n);
  // Base case
  if ((n == 0) || (n == 1)) {
    return BigInteger.ONE;
  }
  else {
    FIB.set(n,fib(n-1).add(fib(n-2)));
    return FIB.get(n);
  }
} // fib(int)

Using a table to cache values turns an O(2^n) algorithm into an
O(n) algorithm!  This is called "Dynamic Programming"