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"