Transcript Dynamic Programming - Seidenberg School of Computer Science

Dynamic Programming
Chapter 15 Highlights
Charles Tappert
Seidenberg School of CSIS, Pace University
What is dynamic programming?


Dynamic programming is a method of solving
optimization problems by combining the solutions
of subproblems
Developing these algorithms follows four steps:
1.
2.
3.
4.
Characterize the structure of an optimal solution
Recursively define the value of an optimal solution
Compute the optimal solution, typically bottom-up
Construct the path of an optimal solution (if desired)
Example – Rod Cutting

Problem: Given a rod of length n inches and a table of
prices, determine the maximum revenue obtainable
by cutting up the rod and selling the pieces


Rod cuts are an integral number of inches, cuts are free
Price table for rods
Example – Rod Cutting

Eight possible ways to cut a rod of length 4
(prices shown on top)
Example – Rod Cutting

The recursion tree for a rod of length 4

The subproblem graph (collapsed tree)
Example – Rod Cutting

Recursive equation:

Bottom-up algorithm – O(n2) from double nesting
Example – Rod Cutting

Extended bottom-up algorithm obtains path

Print solution
Example
Longest Common Subsequence



A string over a finite set S is a sequence of
elements of S (Appendix C, p 1184)
Given two sequences X and Y, a sequence Z is
a common subsequence of X and Y if Z is a
subsequence of both X and Y
Problem: Find the maximum length common
subsequence of X and Y
Example
Longest Common Subsequence
Other Examples from Textbook


Matrix-chain multiplication
Optimal binary search trees
Elements of Dynamic Programming

Two key ingredients for dynamic programming
to apply to an optimization problem:
1.
2.

Optimal substructure (also for greedy algorithms)
Overlapping subproblems
Bottom-up algorithms usually outperform topdown ones by a constant factor due to less
overhead
Elements of Dynamic Programming
1.
Optimal substructure




Occurs when the optimal solution contains
within it optimal solutions to subproblems
We build an optimal solution to the problem
from optimal solutions to subproblems
Rod-cutting a rod of size n uses just one
subproblem of size n-i
Matrix-chain multiplication uses two
subproblems, the two sub-chains
Elements of Dynamic Programming
2.
Overlapping subproblems



This occurs when a recursive algorithm revisits
the same problem repeatedly
The dynamic programming algorithm typically
solves each subproblem only once and stores
the result
The rod-cutting dynamic programming solution
reduced an exponential-time recursive algorithm
down to quadratic time
String matching – LCS

Longest-common-subsequence (LCS) problem,
used in biological applications to compare the
DNA of two different organisms

In-class exercise solve problem 15.4-1 (p 396)
finding the string length and the string
String matching – handwriting

Online handwriting recognition (journal article)
In-class Exercise
String matching – spell checking


Textbook chapter-end problem 5 (p 406)
See Speech and Language book chapter

In-class exercise (time permitting)
String matching – speech & language

Various applications



Speech production models
Speech recognition systems
Speech sound alignment for speaker verification
(voiceprint) systems
Speaker Verification: “My name is …”
Speaker Verification: “My name is …”
by two different speakers
Speaker Verification Alignment Problem:
DTW locates the seven sounds
“My name is” divided into seven sound units.
String matching – assignment

Paper (1-3 pages) due last session

See link to assignment on Syllabus page