Overview

• Preliminaries.
  • Admin.
  • Questions on the Homework.
• Fibonacci.
• Generalizing the Idea.
• The Stamps Problem.
• Edit Distance in Strings.

Preliminaries

Admin

• Please behave during pre/post-Waltz parties.
• Upcoming extra credit opportunities:
  • Any self-care week activity.
  • CS Table Today: Beyond Efficiency.
  • Swim meet Friday and Saturday.
  • Dance Ensemble, lots of times this weekend. (Sold out! But some people take tickets that they don't intend to use.)
  • One acts, Saturday night and Sunday afternoon

Questions on the Homework

Fibonacci

The Fibonacci function:

• f(0) = 1
• f(1) = 1
• f(n) = f(n-1) + f(n-2)

Code?

public static int fib(int n) {
    if ((n == 0) || (n == 1)) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    } // else
} // fib(int)

What are the problems with this solution?

• Might waste space, but we're not sure why.
• Not tail recursive, but we don't know how to make it tail recursive. (Concerns about overflowing the stack.)
• No error checking. If we give this a number less than zero, it runs for a long time.
• Looks inefficient as stated. Maybe we're doing double-ish the work.
• Fibonacci grows quickly. Maybe we should use BigInteger.

How inefficient?

$ java Fib 5
fib(5) = 8
   took 15 calls.
$ java Fib 8
fib(8) = 34
   took 67 calls.
$ java Fib 9
fib(9) = 55
   took 109 calls.
$ java Fib 20
fib(20) = 10946
   took 21891 calls.

Problem: Lots of repeated work

fib(16) = fib(15) + fib(14)
        = fib(14) + fib(13) + fib(14)
        = fib(13) + fib(12) + fib(13) + fib(14)

Solution 1: Change the formula

fib(n) = 2*fib(n-2) + fib(n-3)
fib(16) = 2*fib(14) + fib(13)
        = 2*(2*fib(12) + fib(11)) + fib(13)
        = 2*(2*fib(12) + fib(11)) + 2*fib(11) + fib(10)

Whoops! Still likely to be slow.

Solution 2: Remember our old results

// FIB[n] is -1 if we haven't computed it yet, and something else if we
// have computed it.
private static int[] FIB[?]= { 1, 1, -1, -1, -1 .... }
public static int fib(int n) {
    if (FIB[n] != -1) {
       return FIB[n];
    } else
       FIB[n] = fib(n-1) + fib(n-2);
       return FIB[n];
    }
} // fib(int)

Hand waving argument: "This is now O(n)"

Solution 3: Why do we like tail recursion? Because we avoid the stack. So, let's do it by hand: Write it iteratively from left to right.

public static int fib(int n) {
    int values[] = new int[n+1];
    values[0] = 1;
    values[1] = 1;
    for (i = 2; i <= n; i++) {
       values[i] = values[i-1] + values[i-2];
    }
    return values[n];
} // fib(n)

Solution 4: Drop the array

public static int fib(int n) {
    int prev = 1;
    int current = 1;
    int next;
    for (i = 2; i <= n; i++) {
        next = prev+current;
        prev = current;
        current = next;
    }
    return current;
} // fib(n)

Generalizing the Idea

• Caching values in a table is really useful.
• The first time you compute a value, do the work.
• The next time, you can look it up.
• And maybe creating the table can be down bottom-up instead of top-down

The Stamps Problem

• Given multiple values of stamps/currencies (e.g., 2, 7, 11, 23), find the smallest number of stamps/coins for a particular cost

Code

 public static int smallest(n) {  
    if (n == 0)
        return 0;
    else {
        return 1 + "the min of smallest[n-value], for all values"
    }

A better solution:

• Build a table of the minimum number of stamps to make any value
• Fill in the table from left to right using the technique above

Edit Distance in Strings

• Problem: Two strings (source, target): What's the fewest number of insertions/deletions I need to transform source into target
• Hypothetically useful for biologists: Turn one DNA sequence into another.
• Example: acccgtgcca vs cacccgtgcac
• One transformation
  • Start with acccgtgcca
  • Delete the first letter: cccgtgcca
  • Put an a after the first letter: caccgtgcca
  • Put a c after the fourth letter: cacccgtgcca
  • ...
• Alternate transformation
  • Start with acccgtgcca
  • Put a c at the front cacccgtgcca
• Key idea: Make a table, but a more complicated table
• Column labels: Characters in the source string
• Row labels: Characters in the target string
• Cell: Cost of transforming the source substring to the target substring

Terminology

• Caching/memoizing + Smallest-to-largest = Dynamic Programming