Lecture 18: Dynamic Programming III: Previously

Introduction to Algorithms: 6.
006
Massachusetts Institute of Technology November 13, 2018
Instructors: Zachary Abel, Erik Demaine, Jason Ku Lecture 18: Dynamic Programming III
Lecture 18: Dynamic Programming III
Previously
• Recurrence: Fibonacci, DAG Relaxation, Rod cutting
• Prefix/Suffix: Text Just, LIS, LCS
• Subsequence: Optimal Play
• Extra state: Bellman-Ford
• Applications: counting, optimization, string processing
Dynamic Programming Steps (SR. BST)

1. Define Subproblems subproblem x ∈ X
• Describe the meaning of a subproblem in words, in terms of parameters

• Often subsets of input: prefixes, suffixes, contiguous subsequences
• Often record partial state: add subproblems by incrementing some auxiliary vari-
ables
2. Relate Subproblems x(i) = f (x(j), . . .) for one or more j < i
• State topological order to argue relations are acyclic and form a DAG
3. Identify Base Cases
• State solutions for all reachable independent subproblems
4. Compute Solution from Subproblems
• Compute subproblems via top-down memoized recursion or bottom-up

• State how to compute solution from subproblems (possibly via parent pointers)
5. Analyze Running Time

P
• x∈X work(x), or if work(x) = W for all x ∈ X, then |X| × W
2 Lecture 18: Dynamic Programming III
Edit Distance
• Can modify a string using single character edit operations:
– Delete a character
– Replace a character with another character
– Insert a character between two characters
• Can transform A into B in O(max(|A|, |B|)) edit operations. What is fewest?
• Input: two strings A and B, Output: minimum number of edit operations to change A to B
• Example: A = "dog", B = "dingo" minimum is 3 edits
1. Subproblems
• Modify A until its last character matches last in B (A[i] is ith letter in A, from 1 to |A|)
• x(i, j): minimum number of edits to transform prefix ending at A[i] into prefix ending at B[j]
2. Relate
• If A[i] = B[j], then match!
• Otherwise, need to edit to make last element from A equal to B[j]
• Edit is either an insertion, replace, or deletion (Guess!)
• Deletion removes A[i]
• Insertion adds B[j] to start of prefix ending at A[i], then removes it and B[j]
• Replace changes A[i] to B[j] and removes both A[i] and B[j]

x(i − 1, j − 1) if A[i] = B[i]
• x(i, j) =
1 + min(x(i − 1, j), x(i, j − 1), x(i − 1, j − 1)) otherwise
• Subproblems x(i, j) only depend on strictly smaller i and j, so acyclic
3. Base
• x(i, 0) = i, x(0, j) = j (need many insertions or deletions)
4. Solution
• Solve subproblems via recursive top down or iterative bottom up
• Solution to original problem is x(|A|, |B|)
• (Can store parent pointers to reconstruct edits transforming A to B)
5. Time
• # subproblems: (|A| + 1)(|B| + 1)
• work per subproblem: O(1)
• O(|A||B|) running time
Lecture 18: Dynamic Programming III 3
Arithmetic Parenthesization
• Input: arithmetic expression containing n integers, with integers ai and ai+1 separated by
binary operator oi (a, b) from {+, ×}
• Start with positive integers!
• Output: Where to place parentheses to maximize the evaluated expression
• Example: 7 + 4 × 3 + 5 → ((7) + (4)) × ((3) + (5)) = 88
1. Subproblems
• Observation: Parentheses form nested structure (order of operations)

• Idea: Use contiguous subsets of expression
• x(i, j): maximum parenthesized evaluation of subsequence from integer i to j
2. Relate
• Guess location of outer-most parenthesis, last operation evaluated

• x(i, j) = max {ok (x(i, k), x(k + 1, j)) | k ∈ {i, . . . , j − 1}}
• Subproblems x(i, j) only depend on strictly smaller j − i, so acyclic
3. Base
• x(i, i) = ai
4. Solution

• Maximum evaluated expression is given by x(1, n)
• Store parent pointers (two!) to find parenthesization, (forms binary tree!)
5. Time
• # subproblems: less than n × n × 2 = O(n2 )

• work per subproblem O(n) × 2 × 2 = O(n)
• O(n3 ) running time
4 Lecture 18: Dynamic Programming III
Arithmetic Parenthesization (Negative)

• Input: arithmetic expression containing n integers, with integers ai and ai+1 separated by
binary operator oi (a, b) from {+, ×}
• Now allow negative integers!
• Output: Where to place parentheses to maximize the evaluated expression
• Example: 7 + (−4) × 3 + (−5) → ((7) + ((−4) × ((3) + (−5)))) = 15
1. Subproblems
• Old problems sufficient? (−3) × (−3) = 9 > (−2) × (−2) = 4

• x(i, j, +1): maximum parenthesized evaluation of subsequence from integer i to j
• x(i, j, −1): minimum parenthesized evaluation of subsequence from integer i to j
2. Relate
• Guess location of outer-most parenthesis, last operation evaluated

• x(i, j, +1) = max {ok (x(i, k, s1 ), x(k + 1, j, s2 )) | k ∈ {i, . . . , j − 1}, s1 , s2 ∈ {−1, +1}}
• x(i, j, −1) = min {ok (x(i, k, s1 ), x(k + 1, j, s2 )) | k ∈ {i, . . . , j − 1}, s1 , s2 ∈ {−1, +1}}
• Subproblems x(i, j, s) only depend on strictly smaller j − i, so acyclic
3. Base
• x(i, i, s) = ai
4. Solution

• Maximum evaluated expression is given by x(1, n, +1)
• Store parent pointers (two!) to find parenthesization, (forms binary tree!)
5. Time
• # subproblems: less than n × n × 2 = O(n2 )

• work per subproblem O(n) × 2 × 2 = O(n)
• O(n3 ) running time

Lecture 18: Dynamic Programming III: Previously

Uploaded by

Copyright:

Available Formats

Lecture 18: Dynamic Programming III: Previously

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 18: Dynamic Programming III: Previously

Uploaded by

Copyright:

Available Formats

Introduction to Algorithms: 6.

Lecture 18: Dynamic Programming III

• Prefix/Suffix: Text Just, LIS, LCS

• Subsequence: Optimal Play

• Extra state: Bellman-Ford

• Applications: counting, optimization, string processing

Dynamic Programming Steps (SR. BST)

• Describe the meaning of a subproblem in words, in terms of parameters

2. Relate Subproblems x(i) = f (x(j), . . .) for one or more j < i

3. Identify Base Cases

• State solutions for all reachable independent subproblems

4. Compute Solution from Subproblems

• Compute subproblems via top-down memoized recursion or bottom-up

5. Analyze Running Time

• Start with positive integers!

• Output: Where to place parentheses to maximize the evaluated expression

• Example: 7 + 4 × 3 + 5 → ((7) + (4)) × ((3) + (5)) = 88

• Observation: Parentheses form nested structure (order of operations)

• Guess location of outer-most parenthesis, last operation evaluated

• Solve subproblems via recursive top down or iterative bottom up

• # subproblems: less than n × n × 2 = O(n2 )

Arithmetic Parenthesization (Negative)

• Now allow negative integers!

• Output: Where to place parentheses to maximize the evaluated expression

• Example: 7 + (−4) × 3 + (−5) → ((7) + ((−4) × ((3) + (−5)))) = 15

• Old problems sufficient? (−3) × (−3) = 9 > (−2) × (−2) = 4

• x(i, j, −1): minimum parenthesized evaluation of subsequence from integer i to j

• Guess location of outer-most parenthesis, last operation evaluated

• Solve subproblems via recursive top down or iterative bottom up

• # subproblems: less than n × n × 2 = O(n2 )

You might also like