CSC301.01 2015F, Class 35: Dynamic Programming (3)
==================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Dynamic programming, reviewed.
* The Edit Distance problem.
* The Knapsack problem, revisited.

Preliminaries
-------------

### Admin

* No class Wednesday.
* Handout: [Code in progress](../examples/knapsack.rkt).
* End-of-week PSA.

### Upcoming Work

* HW: Due any time Wednesday: 8-1, 8-2, and 8-3. 
* Take-home exam 2 to be distributed later this week; due week 14.

### Extra Credit

#### Academic

* CS Table Tomorrow, we think.

#### Peer

* Release party, Tuesday 8 pm in DLAB (former CCL).
* Submit to Sequence.  Deadline December 123rd.

### Questions

Review: Key Ideas in Dynamic Programming
----------------------------------------

* Improve algorithms by caching information rather than just recalculating
  it every time.
* Information is usually cached in tables, which means that we are
  often working with integers in a small range or something else
  bounded.
* Often used for algorithms that were originally formulated recursively.
* But we make them iterative.
  
The Edit Distance problem
-------------------------

* Given two strings and three cost functions
    * String1 : Source s[1] ... s[n]
    * String2 : Target t[1] ... t[m]
    * Cost1 : Replace
    * Cost2 : Delete
    * Cost3 : Insert
* Goal: Find a sequence of transformations that converts source
  to target with the minimum cost.  We'll call that
  mincost(s[1] ... s[n], t[1] ... t[m])
* Example: Transformat `abbababa` to `bbaababba`
* Recursive formulation using s[1] ... s[n-1], t[1] .. t[m-1], s[n], t[m]

        mincost(s[1]...s[n], t[1]...t[m]) =
          if (s[n] == t[m])
            mincost(s[1]...s[n-1], t[1]...t[m-1])
          else
            min(
              ; Delete the last character in the source and do the
              ; remaining transofrmations
              delCost(s[n]) + mincost(s[1]...s[n-1], t[1]...t[m]),
              ; Insert the last character in the target and do the
              ; remainign transformations
              insCost(t[m]) + mincost(s[1]...s[n], t[1]...t[m-1]),
              ; Replce the last character in the source by the last
              ; character in the target and do the mainreing fortransmations
              trnCost(s[n],t[m]) + mincost(s[1]...s[n-1], t[1]...t[m-1]))

* But we can make this a table!  (See whiteboard.)
* Your goal: Make the table for abba to bbba

What is the cost of this algorithm?  O(n*m) running time with O(n*m)
space.

Is there a better solution?  Not that I know of.


   
The Knapsack problem, revisited
-------------------------------