Held: Monday, 23 November 2015

Back to Outline 34 - Dynamic Programming (2). On to Outline 36 - Pause for Breath.

Summary

We conclude our exploration of dynamic programming with one of the traditional dynamic-programming algorithms: String matching.

Related Pages

• examples/knapsack.rkt

Overview

• Dynamic programming, reviewed.
• The Edit Distance problem.
• The Knapsack problem, revisited.

Administrivia

• No class Wednesday.
• 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

Peer

The Knapsack Problem

• What changes did you have to make to the Scheme code to get a working solution?

The Edit Distance Problem

• What's the fewest number of edits (insertions, deletions, transformations) necessary to transform one string to another?
• Once again, there's a nice recursive formulation.
  • We working from one end of the string (usually the back) to the other end of the string.
  • We can transform all-but-the-last-character of the source string to all-but-the-last-character of the target string and then transform the last character of the source string into the last character of the target string.
  • We can delete the last character in the source string and then transform the remainder of the source string into the target string.
  • We can transform the source string into all-but-the-last-character of the target string and then add the last character of the target string.
• Can we use dynamic programming techniques to make it iterative?
• This time, we need a two-dimensional table.
  • Rows: Letters of source string
  • Columns: Letters of target string
  • Moving up represents deletion
  • Moving left represents insertion
  • Moving diagonally represents replacement
• And yes, we should fill it in iteratively