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 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];
}