Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• The stamps problem.
• Greedy algorithms.
• The stamps problem, revisited.
• Dynamic programming.

Preliminaries

Admin

• Sit wherever you'd like.

Upcoming Work

• Reading for Tuesday: None

Extra Credit

Academic

• Inside Grinnell Thursday the 11th at noon in JRC 101: Grinnell's Endowment: What Can and Can't it Do?

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music. TONIGHT
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo. (maybe)

Questions

The stamps problem

You go to the post-office and you need to put together the number of stamps to pay for the weight.

Describing more formally

• Input:
  • Positive integer stamp denominations [s1, s2, ..., sk],
  • A target value, t
• Output: Smallest set of stamps that meets t.

Example

• Stamp prices are [1, 2, 7, 12, 25]
• One solution: { 25, 7, 2, 2 }
• Another solution { 12, 12, 12 }
• Another solution { 1, 1, ..., 1 } // 36 of 'em
• How did we come up with the first solution?
  • "Like a computer does" - Start with the largest available proce
  • Others consider this "Like a human does"

Greedy Algorithm

• Make as much process as is possible in 1 step.

  while (haven't reached target)
    add biggest possible stamp
  

• This is fast.

• Unfortunately, it's not correct (in the sense that it does not produce the optimal solution). As we saw above, the best solution of {12,12,12} does not include the largest stamp.
• [The greedy algorithm can also fail to produce any solution. Suppose we didn't have a 1-cent stamp and we wanted to make 26 cents. If we take a 25-cent stamp, we are stuck trying to make 1 cent with our smallest stamp being 2 cents.]
  • Of course, some folks might not care about an exact match.
    My time is valuable enough that I might just buy two 25-cent stamps when I need to make 36 cents, since the extra time/effor spent calculating the optimal solution and keeping more than one kind of stamp on hand is probably worth more to me than 14 cents.

The Stamps Problems, Revisited

Exercise: Take a few minutes with a partner and see if you can come up with a correct algorithm that is not necessarily efficient.

• Suggestion one: See if any of the values are divisors. Then see if there are pairs of values that are divisors. THen ....
• Suggestion two: Decompose the number into two parts, solve the two parts, combine.
• Suggestion three: Try everything, and pick the test
  • Sometimes this is called "Enumerative"
  • Sometimes this is called "Brute Force"

Issues with enumerative algorithms

• Can you actually enumerate? (We can in this problem. There are a finite number of combinations that make a finite value.)

Comparing the two strategies

• Greedy
  • Fast
  • Natural, corresponds to the structure of the problem
  • But doesn't always give the correct answer
• Enumerative
  • Always correct
  • But slow. Really slow. And we still have to figure out how to enumerate.

Dynamic Programming

• We want something fast.
• But we want something that's always correct.
  • We've just seen that we potentially have to look at many combinations to get the next combination.
• We hope to be able to take advantage of the structure of the problem

Fibonacci Numbers

• Sequence

  F0 F1 F2 F3 F4 F5 F6 F7  ... Fn
   0  1  1  2  3  5  8 13      F(n-1)+F(n-2)
  

• We might rephrase this as

  F0 = 0
  F1 = 1
  Fn = Fn = F(n-1) + F(n-2)       Inductive Step
  

• Let's think of this as a function

  fib(0) = 0
  fib(1) = 1
  fib(n) = fib(n-1)+fib(n-2)
  

Code

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

Let's trace it (Sam's attempt to sketch it again on the eboard)

                fib(5)
              /        \
        fib(4)          fib(3)
        /    \           /  \
     fib(3)  fib(2)   fib(2)
     /   \      / \
  fib(2) fib(1)
   /   \
fib(1) fib(0)

Wow! We had to do fifteen or so recursive calls. That seems like a lot. The problem: We repeat a lot of work! fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) again and fib(2). Each of the fib(3)'s also calls fib(2).

Strategy: Memoize! Each time you compute something (e.g., fib(2)), remember it.

So, what did we achieve?

• Fast. Now O(n)
• Always correct (since the original one was correct).
• But perhaps does not match the way that human beings would do it.

Is there is a way that we can do something that's a little more natural?

• Understand the structure of the problem, perhaps the recursive structure.
• Figure out a data structure to keep track of intermediate work.
• Determine the order
• Keep track of invariant

Five minutes with your partner: Think about these issues for another solution for Fibonacci.

Idea: Start with base cases and work your way up.

public static int fib(int n)
{
  // Set up data structure
  if (n == 0) return 0;
  int[] fib = new int[n+1];
  fib[0] = 0;
  fib[1] = 1;
  // Invariant: for j < i, fib[j] is the jth Fibonacci number
  for (int i = 2; i <= n; i++)
    {
      fib[i] = fib[i-1] + fib[i-2];
    } // for
  return fib[n];
} // fib(int)

Can we do better than this?

• We only need to keep track of two values.