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.
• 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(nm) running time with O(nm) space.

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

The Knapsack problem, revisited