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