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 FIB = new Vector(); 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"