CS141: Intermediate Data Structures and Algorithms

Dynamic
Programming
Yan Gu
Minimum Edit Distance
• How to measure the similarity of words or strings?
• Auto corrections: “rationg” -> {“rating”, “ration”}
• Alignment of DNA sequences
• How many edits we need (at least) to transform a sequence X to Y?
• Insertion
• Deletion
• Replace
• rationg -> rating
• Delete o, edit distance 1
• rationg -> action
• Delete r, add c, delete g
• Edit distance 3
Recurrence of Edit Distance
• Similar to LCS, consider the cost to transform 𝑿 𝟏. . 𝒊 to 𝒀[𝟏. . 𝒋]
• Look at the last character 𝑿[𝒊] and 𝒀[𝒋]
• What happens if 𝑿 𝒊 = 𝒀[𝒋]?
Index : 1 2 3 4 5 6 7
X= A B C B D A B

Y= B D C A B A

• Keep 𝑋[𝑖] and 𝑌[𝑗] – no edit needed

• Need to transform ABC to BDCA
• →s[i-1,j-1]

6
Recurrence of Edit Distance
• Similar to LCS, consider the cost to transform 𝑿 𝟏. . 𝒊 to 𝒀[𝟏. . 𝒋]
• Look at the last character 𝑿[𝒊] and 𝒀[𝒋]
• What happens if 𝑿 𝒊 ≠ 𝒀[𝒋]?
Index : 1 2 3 4 5 6 7
X= A B C B D A B

Y= B D C A B A

• Delete C. Cost = (cost of transforming AB => BDCAB) + 1 → s[i-1, j] + 1

• Adding B. Cost = (cost of transforming ABC => BDCA) + 1 → s[i, j-1] + 1
• Editing C to B. Cost = (cost of transforming AB => BDCA) + 1 → s[i-1, j-1] + 1
• Use the min of the above three!
7
Recurrence Relation
• 𝑠[𝑖, 𝑗]: The cost of transforming 𝑋[1. . 𝑖] to 𝑌[1. . 𝑗]

max 𝑖, 𝑗 ;𝑖 = 0 ∨ 𝑗 = 0
𝑠[𝑖 − 1, 𝑗 − 1] ; 𝑖 > 0 ∧ 𝑗 > 0 ∧ 𝑥𝑖 = 𝑦𝑗
𝑠[𝑖, 𝑗] = 𝑠[𝑖, 𝑗 − 1] + 1
min 𝑠[𝑖 − 1, 𝑗] + 1 ; 𝑖 > 0 ∧ 𝑗 > 0 ∧ 𝑥𝑖 ≠ 𝑥𝑗
𝑠[𝑖 − 1, 𝑗 − 1] + 1
Recursive Algorithm
• ED(i, j)
• If computed or base case then return the value
• if X[i] == Y[j] max 𝑖, 𝑗 ;𝑖 = 0 ∨𝑗 = 0
𝑠[𝑖 − 1, 𝑗 − 1] ; 𝑖 > 0 ∧ 𝑗 > 0 ∧ 𝑥𝑖 = 𝑦𝑗
• return ED(i-1, j-1) 𝑠[𝑖, 𝑗] = 𝑠[𝑖, 𝑗 − 1] + 1
min 𝑠[𝑖 − 1, 𝑗] + 1 ; 𝑖 > 0 ∧ 𝑗 > 0 ∧ 𝑥𝑖 ≠ 𝑥𝑗

• if X[i] != Y[j]
𝑠[𝑖 − 1, 𝑗 − 1] + 1

• return min(ED(i, j-1)+1,

ED(i-1, j)+1,
ED(i-1,j-1)+1)
Designing a DP algorithm / recurrence
• Step 1: find the correct (appropriate) subproblems (a polynomial number
of the states/subproblems)
• Step 2: find the relationships between the subproblems

• Particular goals for CS 141 (Intermediate Data Structures and Algorithms)

• Understand the high-level ideas for dynamic programming
• Understand the DP algorithms for three specific problems (knapsack, LCS, LIS)
• Use the variance of these algorithms to solve some related questions
• More related practice will be given in CS 218 (Spring 2021)
• More algorithm design practice
• Optimizing dynamic programming algorithms
• DP on trees, graphs, games, etc.
10
Longest Increasing Subsequence (LIS)
and Other Similar Problems
What is an increasing subsequence?

4 2 7 0 1 6 3 8 5 9
• Increasing subsequence:

2 6 8 9

• Longest increasing subsequence (LIS):

0 1 3 8 9

12
What is an increasing subsequence?

4 2 7 0 1 6 3 8 5 9

13
Why studying LIS?
• The length of LIS reflect some intrinsic properties of the sequence
• Consider the length of LIS as the “eigenvalue” of a sequence (LIS as the “eigenvector”)
• Applications in many algorithms and quantum computing

• Many similar DP algorithms are similar to the DP algorithm for LIS

• More examples are given later in this lecture

4 2 7 0 1 6 3 8 5 9
14
What are the states for LIS?
• Let 𝒍𝒊 be the longest LIS that ends at the 𝒊-th element

• What is the recurrence of LIS?

1 1 2 1 2 3 3 4 4 5
4 2 7 0 1 6 3 8 5 9
15
What are the states for LIS?
• Let 𝒍𝒊 be the longest LIS that ends at the 𝒊-th element

• What is the recurrence of LIS?

𝟏
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊

• Why is it an optimal substructure?

4 2 7 0 1 6 3 8 5 9
16
Running the example input
𝟏
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊

𝒍𝒊 : 1 1 2 1 2 3 3 4 4 5

4 2 7 0 1 6 3 8 5 9
17
Running the example input
𝟏
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊

𝒍𝒊 : 1 2 3 4 5

0 1 3 5 9
18
What is the time complexity of LIS?
𝟏
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊

• 𝒏 element, each takes 𝑶 𝒏 time to compute, so 𝑶 𝒏𝟐 cost in total

• Answer: max 𝒍𝒋
𝟎<𝒋≤𝒏

• LIS can be computed in 𝑶 𝒏 log 𝒏 time (link)

• Will be covered in CS 218: design and analysis of algorithms

19
LIS and similar problems

𝟏
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊

20
Longest decreasing subsequence?

𝟏
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊
𝒂𝒋 > 𝒂𝒊

4 2 7 0 1 6 3 8 5 9
21
Longest increasing subsequence with gap ≥ 𝟑?

𝟏
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊
𝒂𝒋 ≤ 𝒂𝒊 − 𝟑

4 2 7 0 1 6 3 8 5 9
22
Increasing subsequence with MAX SUM?

𝟏 𝒂𝒊
𝒍𝒊 = max ቐ max 𝒍𝒋 + 𝟏
𝟎<𝒋<𝒊,𝒂𝒋 <𝒂𝒊
𝒂𝒊

4 2 7 0 1 6 3 8 5 9
4 2 11 0 1 10 23
 Revisit: activity selection
A1 [1, 4)
Let 𝐴𝑆𝑖 be the maximum number of activities
A2 [3, 5)
and the last one is the 𝑖-th activity, then
A3 [0, 7) 1
𝐴𝑆𝑖 = max ൝ max {𝐴𝑆𝑗 + 1}
A4 [5, 7) 𝑗<𝑖,𝑒𝑗 ≤𝑠𝑖
A11 [5, 9)

A5 [3, 9)

A7 [6, 10)

A8 [8, 11)

A9 [8, 12)

A10 [2, 14)

A6 [12, 16)

0 5 10 15
 Revisit: activity selection: maximize total time?
A1 [1, 4)
Let 𝐴𝑆𝑖 be the maximum number of activities
A2 [3, 5)
and the last one is the 𝑖-th activity, then
A3 [0, 7) 1
𝐴𝑆𝑖 = max ൝ max {𝐴𝑆𝑗 + 1}
A4 [5, 7) 𝑗<𝑖,𝑒𝑗 ≤𝑠𝑖
A11 [5, 9)

A5 [3, 9)

A7 [6, 10)

A8 [8, 11)

A9 [8, 12)

A10 [2, 14)

A6 [12, 16)

0 5 10 15
 Revisit: activity selection: maximize total time?
A1 [1, 4)
Let 𝐴𝑆𝑖 be the maximum number of activities
A2 [3, 5)
and the last one is the 𝑖-th activity, then
A3 [0, 7) 1
𝐴𝑆𝑖 = max ൝ max {𝐴𝑆𝑗 + 1}
A4 [5, 7) 𝑗<𝑖,𝑒𝑗 ≤𝑠𝑖
A11 [5, 9)
𝒆𝒊 − 𝒔𝒊
(duration of
A5 [3, 9) activity 𝒊)
A7 [6, 10)

A8 [8, 11)

A9 [8, 12)

A10 [2, 14)

A6 [12, 16)

0 5 10 15
Motorcade
• A list of cars each with different weight and speed
• Weight 𝑤𝑖 , time needed to cross bridge 𝑡𝑖
• Cross a bridge with weight limit 𝒌
• They have to go in the original order
• Multiple cars can cross the bridge together, but sum of weight must be within weight
limit 𝒌
• The time needed is the longest time among them
• What is the shorted time needed?

𝑤=5 𝑤=8 𝑤=2 𝑤=4 𝑤=5 𝑤=6 𝑤=2 𝑤=7 𝑤=4

𝑡=2 𝑡=4 𝑡=5 𝑡=1 𝑡=4 𝑡=2 𝑡=8 𝑡=2 𝑡=1

27
Motorcade

Total = 21min
𝑡=4 𝑡=5 𝑡=4 𝑡=8

𝑤=5 𝑤=8 𝑤=2 𝑤=4 𝑤=5 𝑤=6 𝑤=2 𝑤=7 𝑤=4

𝑡=2 𝑡=4 𝑡=5 𝑡=1 𝑡=4 𝑡=2 𝑡=8 𝑡=2 𝑡=1

𝑘 = 13

28
Motorcade

Total = 18min
𝑡=2 𝑡=5 𝑡=1 𝑡=8 𝑡=2

𝑤=5 𝑤=8 𝑤=2 𝑤=4 𝑤=5 𝑤=6 𝑤=2 𝑤=7 𝑤=4

𝑡=2 𝑡=4 𝑡=5 𝑡=1 𝑡=4 𝑡=2 𝑡=8 𝑡=2 𝑡=1

𝑘 = 13

29
Motorcade
• Consider the first 𝒊 cars (a prefix of the entire problem)
• What is the “last move”?
• Which cars are in the last batch?
• What is the subproblem?
• Other than the last batch, what is the best solution?
𝑤=5 𝑤=8 𝑤=2 𝑤=4 𝑤=5 𝑤=6 𝑤=2 𝑤=7 𝑤=4
𝑡=2 𝑡=4 𝑡=5 𝑡=1 𝑡=4 𝑡=2 𝑡=8 𝑡=2 𝑡=1

𝑘 = 13
𝑠𝑖 = min 𝑠 𝑗 − 1 + max 𝑡[𝑗. . 𝑖]
0<𝑗<𝑖
sum 𝑤 𝑗..𝑖 ≤𝑘 Boundary: 𝑠 0 = 0
30
Summary for Dynamic Programming
Dynamic Programming (DP)
• DP is not an algorithm, but an algorithm design idea (methodology)

• DP works on problems with optimal substructure

• A DP recurrence of the states, with boundary cases

• We can convert a DP recurrence to a DP algorithm

• Recursive implementation: straightforward
• Non-recursive implementation: faster, and easy to be optimized

32
A high-level approach to design DP algorithms
• DP is not an algorithm, but an algorithm design idea (methodology)

• Ideas in this lecture

• Subproblems: a prefix of the problem
• Decisions: what is the possible “last move” (second last element)?
• Boundary: what is the end of the recursion?

33
How to prepare midterm exam
• First of all, the midterm exam is a review, not to check who is better than
others (of course, it’s a good chance for you to check if you fully
understand the course materials based on a sample set of problems)
• Problems are similar to homework and quiz problems
• Prepare the cheatsheet well
• Summarize the knowledge that you think are important for you in the midterm exam
• Do the homework problems
• Prog HW 3 and 4, Written HW 3 are all available (for the next 3 weeks)
• Dynamic programming is hard, so we will give you as much exercise as possible
• Try to solve as many problems as possible before the exam, which maximizes your
chances to design the DP algorithms in the exam
• Also alleviate the workload in the second half of this quarter

34
Other similar problem: the famous “post-office problem”
• First proposed by Donald Knuth in vol. 3 of TAOCP (1973)
• Let’s consider the 1d case

• Installing each mailbox has certain cost (installation and maintenance)

• But we also want to minimize the residents’ walking distances

35
Formalize the problem
• Installing each mailbox has certain cost 𝒎
• The residents’ unhappiness is the sum of the longest walking distances
for each mailbox

36
Formalize the problem
• Installing each mailbox has certain cost 𝒎
• The residents’ unhappiness is the sum of the longest walking distances
for each mailbox

37
Solving the problem
• Installing each mailbox has certain cost 𝒎
• The residents’ unhappiness is the sum of the longest walking distances
for each mailbox
• Let 𝒑𝒊 be the optimal solution of the first 𝒊 residents:
𝒑𝒊 = min 𝒑𝒋 + 𝒎 + 𝒄𝒊 − 𝒄𝒋+𝟏 /𝟐
𝒋<𝒊
• Boundary: 𝒑𝟎 = 𝟎
• Answer: 𝒑𝒏

38
The line-breaking problem in LaTeX

39
The line-breaking problem in LaTeX
• You have 𝒏 words in a paragraph with lengths 𝒍𝟏 , … , 𝒍𝒏

• You want to break them into lines so each line should contain 50 characters

• The penalty for each line is the 𝒙 − 𝟓𝟎 when 𝒙 is the number of

characters in that line

• You want to find an optimal line-breaking result

40
The line-breaking problem in LaTeX
• Let 𝒃𝒊 be the optimal penalty for the first 𝒊 words
𝒊

𝒃𝒊 = min 𝒃𝒋 + 𝒊 − 𝒋 − 𝟏 + ෍ 𝒍𝒌 − 𝟓𝟎
𝒋<𝒊
𝒌=𝒋+𝟏
• Boundary: 𝒃𝟎 = 𝟎
• Answer: min {𝒃𝒊 + 𝒘(𝒊)}
𝒊<𝒏
• 𝑤 𝑖 is the penalty for the last line, which is 0 if the last line has no more than 50
letters, or 𝑛 − 𝑖 − 1 + σ𝑛𝑘=𝑖+1 𝑙𝑘 − 50 otherwise
• Can add additional penalty to break the words (states changed to letters)
• How to implement it in 𝑶 𝒏𝟐 time?

41