CSC152 2006S, Class 45: Approximate String Matching

Admin:
* Grading of the exam will take a few more days.  Sorry.
* Homework for Wednesday to be announced this afternoon.
* Mini Titular Head tomorrow.

Overview:
* Coin Minimization. Revisited.
* String Matching and String Alignment.
* Dynamic Programming with 2D Arrays.
* Bottom-up vs. Top-down Dynamic Programming.

Problem of Coin Minimization
* Given coin denominations and price, find the smallest number of coins to make that price
  * Choosing the largest coin smaller than price doesn't always work
    * 37, 20, 5, 1, but 40cents is best made by 2x20
* Try each denomination and then recurse on (price-thatdenomination)
  * Limit the expansion of the recursion when you've recursed "too much"
  * Use dynamic programming: Whenever we've computed the minimum number of coins for a price, remember that
* Problem: Need to remember failure, too!
  + Store -1 in the cache
  + Check the cache
* Another problem: Doesn't tell us the coins
  * Add another vector that parallels the cache and that tells us which coin we used at that price
  * Instead of caching number of coins, instead cache an array of each coin used 
  * Use a dictionary in which the key is the "price" and the value is the collection of coins used