CSC152 2006S, Class 44: Dynamic Programming, Revisited: Coin Matching

Admin:
* Almost no one did an acceptable job on HW15.  Try again.
* For those of you becoming Math or CS majors: Join the SEPC.  Schedule Pub night at a reasonable hour.
* Kelly (Pasadena, CA) and Adhiti (Boston, Massachusetts)
  * Howard (DC), Pepperdine (CA), LMU, American U. (DC), Scrips (CA), ...
  * Holy Cross, UMass/Amherst
* Why come to Grinnell rather than (___)?
  * Go to Pepperdine, the weather is better
  * Come to Grinnell, the weather builds character, the air is cleaner
  * Come to Grinnell, our professors are more sarcastic than those in the classes Ian visited at some other schools
  * Come to Grinnell, get further away from your 'rents
* EC for baseball games on Sunday

  * Come to Grinnell, experience the wonder of the "open" curriculum (except that you need 3x3 to get study abroad or double major or ...)

Overview:
* Reminder: Dynamic Programming.
* Simple Example: Coin Minimization.
* Detour: Returning Better Info.
* String Matching and String Alignment.
* Dynamic Programming with 2D Arrays.
* Bottom-up vs. Top-down Dynamic Programming.

/About HW15/

 /**
   * Get the position of the end of the list.
   *
   * @return pos
   *   A position that represents the end of the list.
   * @pre
   *   The list should not be empty.
   * @post
   *   The list is not modified.
   *   pos "belongs to" this list.
   */
  public Position rear();

Need to use the comparator (mentioned in the introductory documentation) to indicate what it means to be the end of the list.  "The largest"

  For all valid positions p, c.compare(this.get(p),this.get(pos)) <= 0

          /**
           * Get the position of the front of this list.
           *
           * @return pos
           *   A position that represents the front of the list.
           *   Returns the first(the smallest) objected of the list in the sorted order.
           * @pre
           *   The list should not be empty.
           *   List should be sorted.
           * @post
           *   The list is not modified.
           *   pos "belongs to" this list.
           *  
           */
          public abstract Position front();

/**
 * Get the element at the end of the list which happens to be the smallest value in the list.
 * @pre
 * The list is not empty.
 */
public Iterator<T> atEnd()

 /**
   * Get the position of the next larger element in the list.
   *
   * @return succ
   *   The position of the next larger value than the value at pos.
   * @pre
   *   pos cannot be the largest position in the list.
   *   pos "belongs to" this list.
   * @post
   *   succ "belongs to" this list.
   *   The list is not modified
   */
  public Position successor(Position pos);

          /**
           * Determine if a position represents the lowest value in
           * the list.
           *
           * @return
           *   True, if pos is the first position.  False, otherwise.
           * @pre
           * @post
           */
          public boolean isFirst(Position pos);

/Dynamic Programming/

* Algorithm improvement technique
* Key idea: When writing a multiply-recursive algorithm, cache intermediate results and check the table before doing the computation
* First example: Fibonacci numbers
  From O(2^n) to O(n)
* Another expensive algorithm: Approximate string matching
  Can we make it better?

/Simpler Dynamic Programming Problem/

* Visiting a country
* Denominations of coins d0,d1,...,dn
* 1, 5, 7, 8, 20, 37
* Goal: Given a price p, find the fewest coins to make that price exactly
* One strategy: 
  * Use as many of the largest denomination first
  * Then as many of the next largest
  * And so on and so forth
* That strategy
  * Relies on a 1-cent coin to ensure that you can make the denomination
  * Fails for some prices 
* For each denomination, di,
  Figure out how many coins it takes to make p-di
  The smallest number of coins is 1 + the smallest of those values
* Correctness: Tries every possible combination of coins and chooses smallest
* Improvement: Stop it from searching stupidly (e.g., if we know we can make the price with 5 coins, don't explore branches that require more than 5)
* This is a *slow* strategy
* It also gives not-very-useful results: Number of coins, not the particular coins
* To make it faster: Cache the values!
  * Create an array, cache, of size (price), which contains ints
    int[] cache = new int[price+1];
    * EC of 1 point to LKH for pointing out the pun
  * Whenever computing,
    if (cache[price] != 0) {
      return cache[price];
    }