Algorithms and OOD (CSC 207 2013F) : Outlines

# Outline 52: Dynamic Programming

Held: Friday, 6 December 2013

Summary

We consider a new approach to solving certain kinds of complex problems.

Related Pages

Overview

• Fibonacci.
• Generalizing the Idea.
• The Stamps Problem.
• Edit Distance in Strings.

• Upcoming extra credit opportunities:
• Any self-care week activity.
• CS Table Today: Beyond Efficiency.
• Swim meet Friday and Saturday.
• Dance Ensemble, lots of times this weekend.
• One acts, lots of times this weekend.

## Fibonacci

• Recursive formulation
• Improving the solution
• Cache the results in a table!
• Making it iterative
• Fill in the table from left to right
• Making it even better
• Only need two variables

• Tables!

## The Stamps Problem

• Recursive formulation
• Making it iterative
• Use a table and fill it in left-to-right

## The Edit Distance Problem

• What's the fewest number of edits (insertions, deletions) necessary to transform one string to another?
• Once again, there's a nice recursive formulation.
• Can we use similar techniques to make it iterative?
• This time, we need a two-dimensional table.
• Columns: Letters of source string
• Rows: Letters of target string
• Moving left represents deletion
• Moving up represents insertion
• And yes, we should fill it in iteratively

Copyright (c) 2013 Samuel A. Rebelsky.

This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit `http://creativecommons.org/licenses/by/3.0/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.