Lecture 4:
Dynamic Programming I
William Umboh
School of Computer Science
The University of Sydney
Page 1
Fast Fourier Transform
Moving completely online
– Lectures
– Held on Zoom and recorded
– Use Mentimeter for anonymous questions
– Participants muted on entry. Press the “Raise Hands” button to ask a question and unmute yourself once I’ve acknowleged you.
– Tutorials
– Online starting from next week
– Your tutors will coordinate with you on Slack
– Final exam
– The final exam will be available online. More
details to follow. The University of Sydney
Page 2
General techniques in this course
The University of Sydney Page 3
General techniques in this course
– Greedy algorithms [5 Mar]
– Divide & Conquer algorithms [12 Mar]
– Dynamic programming algorithms [Today and 26 Mar] – Network flow algorithms [2 and 9 Apr]
The University of Sydney
Page 4
Algorithmic Paradigms
– Greedy. Build up a solution incrementally, myopically optimizing some local criterion.
– Divide-and-conquer. Break up a problem into two sub- problems, solve each sub-problem independently, and combine solution to sub-problems to form solution to original problem.
– Dynamic programming. Break up a problem into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problems.
The University of Sydney Page 5
Dynamic Programming Applications
– Areas.
– Bioinformatics.
– Control theory.
– Information theory.
– Operations research.
– Computer science: theory, graphics, AI, systems, ….
– Some famous dynamic programming algorithms. – Viterbi for hidden Markov models.
– Unix diff for comparing two files.
– Smith-Waterman for sequence alignment.
– Bellman-Ford for shortest path routing in networks.
– Cocke-Kasami-Younger for parsing context free grammars.
The University of Sydney
Page 6
6.1 Weighted Interval Scheduling
The University of Sydney Page 7
Recall Interval Scheduling (Lecture 3)
– Interval scheduling.
– Input: Set of n jobs. Each job i starts at time sj and finishes at time fj.
– Two jobs are compatible if they don’t overlap in time.
– Goal: find maximum subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 8
Recall Interval Scheduling (Lecture 3)
There exists a greedy algorithm [Earliest finish time] that computes the optimal solution in O(n log n) time.
The University of Sydney Page 9
Interval Scheduling: Analysis
– Theorem: Greedy algorithm [Earliest finish time] is optimal. – Proof: (by contradiction)
– Assume greedy is not optimal, and let’s see what happens.
– Let i1, i2, … ik denote the set of jobs selected by greedy.
– Let J1, J2, … Jm denote the set of jobs in an optimal solution with i1 = J1, i2 = J2, …, ir = Jr for the largest possible value of r.
Greedy: OPT:
job ir+1 finishes before Jr+1
i1
i1
ir
ir+1
J1
J2
Jr
Jr+1
…
…
The University of Sydney
Page 10
Why not replace job Jr+1 with job ir+1?
Weighted Interval Scheduling
– Weighted interval scheduling problem.
– Job j starts at sj, finishes at fj, and has weight vj .
– Two jobs compatible if they don’t overlap.
– Goal: find maximum weight subset of mutually compatible jobs.
a b
c
d
e
f
g
h
Time
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Page 11
Unweighted Interval Scheduling Review
– Recall. Greedy algorithm works if all weights are 1.
– Consider jobs in ascending order of finish time.
– Add job to subset if it is compatible with previously chosen jobs.
– Observation. Greedy algorithm can fail if arbitrary weights are allowed.
weight = 999 weight = 1
b
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney
Page 12
a
Time
Key steps: Dynamic programming
1. Define subproblems
2. Find recurrence relating subproblems 3. Solve the base cases
4. Transform recurrence into an efficient algorithm
The University of Sydney Page 13
Weighted Interval Scheduling
Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn .
Def. p(j) = largest index i < j such that job i is compatible with j. Ex: p(8)=5,p(7)=3,p(2)=0.
1
2
3
4
5
6
7
8
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 14
Weighted Interval Scheduling
Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn .
Def. p(j) = largest index i < j such that job i is compatible with j. Step 1: Define subproblems
OPT(j) = value of optimal solution to the subproblem consisting of job requests 1, 2, ..., j.
1
3
2
4
5
6
7
8
p(8)
The University of Sydney
Page 15
0 1 2 3 4 5 6 7 8 9 10 11
Time
Dynamic Programming: Weighted Interval Scheduling
Step 2: Find recurrences
– Case 1: OPT selects job j.
• can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of
remaining compatible jobs 1, 2, ..., p(j)
1
3
2
4
5
6
7
8
TheUniversityofSydney
Time Page16
p(8)
0 1 2 3 4 5 6 7 8 9 10 11
Dynamic Programming: Weighted Interval Scheduling
Step 2: Find recurrences
– Case 1: OPT selects job j.
• can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of
remaining compatible jobs 1, 2, ..., p(j)
The University of Sydney
Page 17
OPT(j) = vj + OPT (p(j)) Case 1
Weighted Interval Scheduling
Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn .
Def. p(j) = largest index i < j such that job i is compatible with j. Solve OPT(8)
1
3
2
4
5
6
7
8
p(8)
The University of Sydney
Page 18
0 1 2 3 4 5 6 7 8 9 10 11
Time
Dynamic Programming: Weighted Interval Scheduling
Step 2: Find recurrences
– Case 1: OPT selects job j.
• can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of
remaining compatible jobs 1, 2, ..., p(j) – Case 2: OPT does not select job j.
• must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., j-1
OPT(j) = vj + OPT (p(j)) Case 1
The University of Sydney
Page 19
Dynamic Programming: Weighted Interval Scheduling
Step 2: Find recurrences
– Case 1: OPT selects job j.
• can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of
remaining compatible jobs 1, 2, ..., p(j) – Case 2: OPT does not select job j.
• must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., j-1
OPT(j) = max {vj + OPT (p(j)), OPT(j-1)} Case 1 Case 2
The University of Sydney
Page 20
Dynamic Programming: Weighted Interval Scheduling Step 3: Solve the base cases
OPT(j)=ìí 0 The University of Sydney
OPT(0) = 0
if j=0 îmax{vj +OPT(p(j)), OPT(j-1)} otherwise
Done...more or less
Page 21
Weighted Interval Scheduling: Naïve Recursion
– Naïve recursion algorithm.
Input: n, s1,...,sn , f1,...,fn , v1,...,vn
Sort jobs by finish times so that f1 £ f2 £ ... £ fn.
Compute p(1), p(2), ..., p(n)
Compute-Opt(j) {
if (j = 0)
return 0 else
return max(vj + Compute-Opt(p(j)), Compute-Opt(j-1)) }
return Compute-Opt(n)
The University of Sydney Page 22
Weighted Interval Scheduling: Naïve Recursion
– Naïve recursion algorithm.
Input: n, s1,...,sn , f1,...,fn , v1,...,vn
Sort jobs by finish times so that f1 £ f2 £ ... £ fn.
Compute p(1), p(2), ..., p(n)
Compute-Opt(j) {
if (j = 0)
return 0 else
return max(vj + Compute-Opt(p(j)), Compute-Opt(j-1)) }
return Compute-Opt(n)
The University of Sydney
Page 24
Running time: T(n) = T(n-1) + T(p(n)) + O(1) = ?
Weighted Interval Scheduling: Naïve Recursion
Observation. Recursive algorithm is slow because of exponential recursive call Þ exponential algorithms.
Example. Number of recursive calls for family of "layered" instances grows like Fibonacci sequence:
T(n) = T(n-1) + T(n-2) + c
1
2
3
4
5
TheUniversityofSydney
p(1) = 0, p(j) = j-2
5 43
3221 211010
10
Exponential recursive calls akamultiplyandsurrender Page25
Not memorization! Weighted Interval Scheduling: Memoization
Memoization. Store results of each sub-problem; lookup when needed.
Input: n, s1,...,sn , f1,...,fn , v1,...,vn
Sort jobs by finish times so that f1 £ f2 £ ... £ fn.
Compute p(1), p(2), ..., p(n)
for j = 1 to n
M[j] = empty
M[0] = 0
Compute-Opt(j) {
if (M[j] is empty)
Preprocessing
M[j] = max(vj + Compute-Opt(p(j)), Compute-Opt(j-1)) return M[j]
}
return Compute-Opt(n)
The University of Sydney
Page 26
Not memorization! Weighted Interval Scheduling: Memoization
Memoization. Store results of each sub-problem; lookup when needed.
Input: n, s1,...,sn , f1,...,fn , v1,...,vn
Sort jobs by finish times so that f1 £ f2 £ ... £ fn.
Compute p(1), p(2), ..., p(n)
for j = 1 to n
M[j] = empty
M[0] = 0
Compute-Opt(j) {
if (M[j] is empty)
Preprocessing
}
M[j] = max(vj + Compute-Opt(p(j)), Compute-Opt(j-1)) return M[j]
return Compute-Opt(n)
The University of Sydney Page 27
Running time: O(n log n)
Weighted Interval Scheduling: Running Time Claim. Memoized version of algorithm takes O(n log n) time.
5 43
3221 211010
1
2
3
4
5
p(1) = 0, p(j) = j-2
10
Remark: O(n) if jobs are pre-sorted by start and finish times. The University of Sydney
Page 29
29
Weighted Interval Scheduling: Memoization Memoization. Store results of each sub-problem; lookup
when needed.
Input: n, s1,...,sn , f1,...,fn , v1,...,vn
Sort jobs by finish times so that f1 £ f2 £ ... £ fn.
Compute p(1), p(2), ..., p(n)
for j = 1 to n
M[j] = empty
M[0] = 0
Compute-Opt(j) {
if (M[j] is empty)
Preprocessing
}
M[j] = max(vj + Compute-Opt(p(j)), Compute-Opt(j-1)) return M[j]
return Compute-Opt(n)
The University of Sydney Page 30
Running time: O(n log n)
Weighted Interval Scheduling: Running Time
Claim. Memoized version of algorithm takes O(n log n) time.
– Sort by finish time: O(n log n).
– Computing p(×) : O(n log n) after sorting by start time.
– Compute-Opt(j): each call takes O(1) time because it either
• (i) returnsanexistingvalueM[j]
• (ii) fills in one new entry M[j] and makes two new recursive calls
– Overall time is O(1) times the number of calls to Compute-Opt(j).
– ProgressmeasureK=#nonemptyentriesofM[].
• initially K = 0 and the number of empty entries is n.
• Case (ii) increases K by 1 Þ at most 2n recursive calls.
– Overall running time of Compute-Opt(n) is O(n). ▪
Remark: O(n) if jobs are pre-sorted by start and finish times. The University of Sydney
Page 31
31
Weighted Interval Scheduling: Bottom-Up
– Bottom-up dynamic programming. Unwind recursion. – This is the style we will use in rest of lectures
Input: n, s1,...,sn , f1,...,fn , v1,...,vn
Sort jobs by finish times so that f1 £ f2 £ ... £ fn.
Compute p(1), p(2), ..., p(n)
Iterative-Compute-Opt {
M[0] = 0
for j = 1 to n
M[j] = max(vj + M[p(j)], M[j-1])
return M[n] }
The University of Sydney Page 32
Weighted Interval Scheduling: Finding a Solution Question. Dynamic programming algorithm computes optimal value.
What if we want the solution itself? Answer. Do some post-processing.
Run Compute-Opt(n)
Run Find-Solution(n)
Find-Solution(j) {
if (j = 0)
output nothing
else if (vj + M[p(j)] > M[j-1])
print j
Find-Solution(p(j))
else
Find-Solution(j-1)
}
picked job j
# of recursive calls £ n Þ O(n). The University of Sydney
Page 33
33
Maximum-sum contiguous subarray
Given an array A[ ] of n numbers, find the maximum sum found in any contiguous subarray
A zero-length subarray has maximum 0
Example:
1
-2
7
5
6
-5
5
8
1
-6
The University of Sydney Page 34
Maximum-sum contiguous subarray
Given an array A[ ] of n numbers, find the maximum sum found in any contiguous subarray
A zero-length subarray has maximum 0
Example:
1
-2
7
5
6
-5
5
8
1
-6
The University of Sydney Page 35
Brute-force algorithm (Lecture 1)
– How many subarrays in total?
– Algorithm: For each subarray, compute the sum. Report
the subarray that has the maximum sum.
The University of Sydney
Page 36
O(n2)
O(n)
Total time: O(n3)
Divide-and-conquer algorithm
Maximum contiguous subarray (MCS) in A[1..n]
– Three cases:
a) MCS in A[1..n/2]
b) MCS in A[n/2+1..n]
c) MCS that spans A[n/2, n/2 + 1]
– (a) & (b) can be found recursively – (c) ?
– Tutorial exercise for next week The University of Sydney
Page 37
Dynamic programming Step 1: Define subproblems
OPT(i) = value of optimal solution ending at i.
=max(max𝐴[𝑗]+𝐴 𝑗+1 …+𝐴[𝑖],0) !”#
The University of Sydney
Page 52
Dynamic programming algorithm
Example 1:
OPT[1] = 6 6
3 -1 2
OPT[2] = 3 OPT[3] = 1 OPT[4] = 4 OPT[5] = 3 OPT[6] = 5
6 -3
6 -3 -2 6 -3 -2 6 -3 -2 6 -3 -2
3
3 -1
3 -1 2
6 -3 -2
The University of Sydney
Page 53
OPT[i] – optimal solution ending at i
Dynamic programming algorithm
Example 2:
OPT[1] = 0 -2
OPT[2] = 5 OPT[3] = 4 OPT[4] = 0 OPT[5] = 3 OPT[6] = 2 OPT[7] = 4
-2 5
-1 -5 -2 5 -1
3 -1 2
-2 5
-2 5 -2 5 -2 5 -2 5
-1 -5 -1 -5 -1 -5 -1 -5
3
3 -1
3 -1 2
The University of Sydney
Page 55
OPT[i] – value of optimal solution ending at i
Dynamic programming algorithm
Example 2:
OPT[1] = 0 -2
OPT[2] = 5 OPT[3] = 4 OPT[4] = 0 OPT[5] = 3 OPT[6] = 2 OPT[7] = 4
Step 2: Find recurrences
-2 5
-1 -5 -2 5 -1
3 -1 2
-2 5
-2 5 -2 5 -2 5 -2 5
-1 -5 -1 -5 -1 -5 -1 -5
3
3 -1
3 -1 2
2 cases:
(1) A[i] is not included in the optimal solution ending at i.
(2) A[i] is included. In this case, the optimal solution ending at i
extends optimal solution ending at i – 1
The University of Sydney OPT[i] = max{OPT[i-1]+A[i], 0} Page 56
Dynamic programming algorithm Step 3: Solve the base cases
OPT[1] = max(A[1], 0)
OPT[i] = The University of Sydney
max(A[1], 0) max{OPT[i-1]+A[i], 0}
if i=1 if i>1
Why can’t we just take A[1]?
Page 57
Pseudo Code
OPT[1] = max(A[1], 0) for i = 2 to n do
OPT[i] = max(OPT[i-1]+A[i], 0) MaxSum = max1≤ i ≤ n OPT[i]
The University of Sydney
Page 58
OPT[i] – optimal solution ending at i
Total time: O(n)
Longest increasing subsequence
Given a sequence of numbers X[1..n] find the longest increasing subsequence (i1, i2, …, ik), that is a subsequence where numbers in the sequence are increasing.
The University of Sydney
Page 59
52863697
Longest increasing subsequence
Given a sequence of numbers X[1..n] find the longest increasing subsequence (i1, i2, …, ik), that is a subsequence where numbers in the sequence increase.
The University of Sydney
Page 60
52863697
Longest increasing subsequence
Step 1: Define subproblems
– L[i] = length of the longest increasing subsequence that ends at i.
– L[1]=1 52863697
– Example: L[1] = 1
L[2] = 1 L[3] = 2
L[4] = 2 L[5] = 2 L[6] = 3
L[7] = 4 L[8] = 4
The University of Sydney
Page 61
Longest increasing subsequence
Step 1: Define subproblems
– L[i] = length of the longest increasing subsequence that ends at i, including i itself
– L[1] = 1 (base case) 52863697
Step 2: Define recurrence
X[i] is in LIS ending at i, by definition, so it must extend the
LIS ending at j < I for some X[j] < X[i] L[i] = max { L[j] +1 | X[j] < X[i]}
0
– Goal: fill knapsack so as to maximize total value.
– Example: { 3, 4 } has value 40.
W = 11
Item Value Weight
– Greedy: repeatedly add item with maximum ratio vi / wi. (“best bang for buck”)
– Ex: { 5, 2, 1 } achieves only value = 35 Þ greedy not optimal. The University of Sydney
Page 65
111 262 3 18 5 4 22 6 5 28 7
Dynamic Programming: False Start
– Definition. OPT(i) = max profit subset of items 1, …, i.
– Case 1: OPT does not select item i.
• OPTselectsbestof{1,2,…,i-1}
– Case 2: OPT selects item i.
• accepting item i does not immediately imply that we will have to
reject other items
• without knowing what other items were selected before i, we don’t even know if we have enough room for i
Conclusion: Need subproblems with more structure!
The University of Sydney Page 66
Dynamic Programming: Adding a New Variable Step 1: Define subproblems
OPT(i, w) = max profit subset of items 1, …, i with weight limit w.
Item
Value
1
1
2
6
3
18
4
22
5
28
The University of Sydney
Page 67
i=5 w = 11
Dynamic Programming: Adding a New Variable Step 2: Find recurrences
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
Item
Value
1
1
2
6
3
18
4
22
5
28
The University of Sydney
Page 69
OPT[i,w] = OPT[i-1,w]
case 1
i=5 w = 11
max{
Dynamic Programming: Adding a New Variable Step 2: Find recurrences
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
– Case 2: OPT selects item i.
• new weight limit = w – wi
• OPT selects best of { 1, 2, …, i–1 } using this new weight limit
OPT[i,w] = OPT[i-1,w] , vi+OPT[i-1,w-wi]
case 1 case 2
The University of Sydney
Page 71
max{
Dynamic Programming: Adding a New Variable Step 2: Find recurrences
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
– Case 2: OPT selects item i.
• new weight limit = w – wi
• OPT selects best of { 1, 2, …, i–1 } using this new weight limit
OPT[i,w] = OPT[i-1,w] , vi+OPT[i-1,w-wi]}
case 1 case 2
The University of Sydney
Page 72
max{
Dynamic Programming: Adding a New Variable Step 3: Solve the base cases
The University of Sydney
Page 73
OPT[0,w] = 0
Dynamic Programming: Adding a New Variable
– Base case: OPT[0,w] = 0
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
– Case 2: OPT selects item i.
• newweightlimit=w–wi
• OPTselectsbestof{1,2,…,i–1}usingnewweightlimitw–wi
0 if i=0 OPT[i,w] = OPT[i-1,w] if wi > w
max{OPT[i-1,w], vi+OPT[i-1,w-wi]} otherwise
The University of Sydney Page 74
n+1
W+1
0 1 2 3 4 5 6 7 8 9 10 11
Æ 000000000000 {1} 011111111111 {1,2} 016777777777
{1,2,3} 0 1 6 7 7 18 19 24 25 25 25 25
Knapsack Algorithm Recurrence: Example
OPT[i,w] =
0
OPT[i-1,w]
max{OPT[i-1,w], vi+OPT[i-1,w-wi]}
if i=0
if wi > w otherwise
W = 11
Item Value Weight
111 262 3 18 5 4 22 6
5 28 7
The University of Sydney
Page 75
{1,2,3,4} {1,2,3,4,5}
0 1 6 7 7 18 22 24 28 29 29 40 0 1 6 7 7 18 22 28 29 34 34 40
Knapsack Problem: Bottom-Up
– Knapsack. Fill up an (n+1)-by-(W+1) array. Input: n, w1,…,wN, v1,…,vN
for w = 0 to W
M[0, w] = 0
for i = 1 to n
for w = 1 to W
if (wi > w)
M[i, w] = M[i-1, w]
else
M[i, w] = max {M[i-1, w], vi + M[i-1, w-wi ]} return M[n, W]
The University of Sydney
Page 76
Knapsack Algorithm: Bottom-Up Example
W+1
0
1
2
3
4
5
6
7
8
9
10
11
Æ
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
1
1
1
1
1
1
1
1
1
1
1
{ 1, 2 }
0
1
6
7
7
7
7
7
7
7
7
7
{ 1, 2, 3 }
0
1
6
7
7
18
19
24
25
25
25
25
{ 1, 2, 3, 4 }
0
1
6
7
7
18
22
24
28
29
29
40
{ 1, 2, 3, 4, 5 }
0
1
6
7
7
18
22
28
29
34
34
40
n+1
Item
Value
Weight
1
1
1
2
6
2
3
18
5
4
22
6
5
28
OPT[i,w] =
0
OPT[i-1,w]
max{OPT[i-1,w], vi+OPT[i-1,w-wi]}
if i=0
if wi > w otherwise
W = 11
The University of Sydney
7
Page 77
Knapsack Algorithm
W+1
0
1
2
3
4
5
6
7
8
9
10
11
Æ
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
1
1
1
1
1
1
1
1
1
1
1
{ 1, 2 }
0
1
6
7
7
7
7
7
7
7
7
7
{ 1, 2, 3 }
0
1
6
7
7
18
19
24
25
25
25
25
{ 1, 2, 3, 4 }
0
1
6
7
7
18
22
24
28
29
29
40
{ 1, 2, 3, 4, 5 }
0
1
6
7
7
18
22
28
29
34
34
40
n+1
Item
Value
Weight
1
1
1
2
6
2
3
18
5
4
22
6
5
28
OPT[i,w] =
0
OPT[i-1,w]
max{OPT[i-1,w], vi+OPT[i-1,w-wi]}
OPT: {4,3}
value = 22 + 18 = 40
if i=0
if wi > w otherwise
W = 11
The University of Sydney
7
Page 78
Knapsack Problem: Running Time
– Running time: Q(nW).
– Not polynomial in input size!
– “Pseudo-polynomial” : polynomial in size of numbers not their bit length – Decision version of Knapsack is NP-complete.
– Knapsack approximation algorithm. There exists a polynomial algorithm (w.r.t. n) that produces a feasible solution that has value within 0.01% of optimum.
The University of Sydney Page 79
What is input size?
Input size = O(n log W)
Dynamic Programming Summary
– Dynamicprogramming=smartrecursion
– Recipe.
– Characterizestructureofproblemstep
– Recursivelydefinevalueofoptimalsolution.
– Computevalueofoptimalsolution.
– Constructoptimalsolutionfromcomputedinformation.
– Dynamicprogrammingtechniques.
– Binary choice: weighted interval scheduling. – Adding a new variable: knapsack.
Viterbi algorithm for HMM also uses
DP to optimize a maximum likelihood tradeoff between parsimony and accuracy
– Top-down vs. bottom-up: different people have different intuitions.
The University of Sydney Page 80