Introduction and background
Introduction and Background Advanced Algorithms & Data Structures
COMP4500/7500 Sep 8, 2020
1/12
Introduction and background
Overview of this week
Dynamic programming examples
Calculating Fibonacci numbers
Longest common subsequence (LCS) in strings Matrix-chain multiplication example
2/12
Dynamic programming
Dynamic programming
Method for efficiently solving problems of certain kind.
May apply to problems with optimal sub-structure:
An optimal solution to a problem can be expressed (recursively) in terms of optimal solutions to sub-problems.
A naive recursive solution may be ineffficient (exponential) due to repeated computations of subproblems.
Dynamic programming avoids re-computation of sub-problems by storing them.
Requires a deep understanding of the problem and its solution; however some standard formats apply.
August 28, 2019 3/28
Dynamic programming
Dynamic programming
August 28, 2019
4/28
Dynamic programming constructs a solution “bottom up”: Compute solutions to base-case sub-problems first;
then methodically calculate all intervening sub-problems; until the required problem can be computed.
Massive speed improvements are possible: from exponential-time to polynomial-time.
Dynamic programming
Memoisation
Memoisation is a type of dynamic programming (i.e. solutions to sub-problems are stored so that they are never recomputed).
Memoisation is “top-down”, in the same sense as recursion.
It is often more “elegant” but has slightly worse constant factors.
August 28, 2019
5/28
Dynamic programming
Fibonacci numbers
Many problems are naturally expressed recursively. However recursion can be computationally expensive.
Definition (Fibonacci numbers)
F(i) = 1 ifi=1ori=2 F(i) = F(i 1) + F(i 2) otherwise
Thus the sequence of Fibonacci numbers starting from 1 is: 1 1 2 3 5 8 13 21 34..
F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8) F(9).. F (35) = 9, 227, 465
August 28, 2019 6/28
Dynamic programming
Recursive algorithm for calculating Fibonacci numbers
August 28, 2019
7/28
FIB(n)
1 ifn==1orn==2
2 return 1
3 else
4 return FIB(n 1) + FIB(n 2)
Corresponding recurrence:
T(n) = T(n 1) + T(n 2) + ⇥(1)
2 ⇥(1.6n)(approx)
Dynamic programming
Recursive calculations
August 28, 2019
8/28
Lots of overlap/redundancy:
F(3) is calculated from scratch three times for F(6)
Key idea: Instead of recalculating a number already seen, store the original calculation in an array, and just look it up when encountered later.
Dynamic programming
Dynamic implementation of Fibonacci
FIB-DYN(n)
1 T=newint[n]
2 T[1]=1
3 T[2]=1
4 fori=3..n
5 T[i] = T[i 1]+T[i 2]
6 returnT [n]
The array elements correspond to the mathematical definition: T[1] T[2] T[3] T[4] T[5] T[6] T[7] T[8] T[9]..
1 1 2 3 5 8 13 21 34..
Analysis of FIB-DYN(n): T(n) = Pni=3 ⇥(1) 2 ⇥(n)
August 28, 2019 9/28
Dynamic programming
Memoised implementation of Fibonacci
August 28, 2019
10/28
Assume array T is a global variable, and we will never require a Fibonacci number past N.
FIB-INIT()
1 T=newint[N]
2 fori=1..N
3 T[i] = null
4 T[1]=1
5 T[2]=1
FIB-MEMO(n)
1 2 3
ifT[n]==null
T [n] = FIB-MEMO(n 1) + FIB-MEMO(n 2)
returnT [n]
Dynamic programming
General principles of dynamic programming
August 28, 2019
11/28
Solving problems using recursion is often intuitive and elegant. However it can be massively inefficient.
If:
1 the problem has the optimal substructure property, and
2 its recursive solution has overlapping subproblems
then dynamic programming techniques may apply.
Benefit: One gets an efficient (polynomial-time) implementation (for the loss of elegance).
Fibonacci:
Optimal substructure: a Fibonacci number can be calculated from smaller Fibonacci numbers
Overlapping subproblems: F(6) (etc.) recalculates F(3) three times
Dynamic programming
Longest common subsequence (LCS)
August 28, 2019
12/28
Problem: find the longest (non-contiguous) sequence of characters shared between two strings
S1: A B C B C S2: C A B B D
1 2
LCS(S1, S2) = ABB
Used in gene sequencing , File diff, …
Dynamic programming
Developing a recursive description for LCS
Assume you have already solved any strictly smaller subproblem (s).
How can you use that to solve your (top-level) problem? Identify the base cases.
August 28, 2019 14/28
Dynamic programming
Developing a recursive description for LCS
Assume that we have calculated for
S1 : ABCBC and S2 : CABBD
LCS(S1, S2) = ABB
What is the LCS of
ABCBCE and CABBDE ? More clearly: what is the LCS of
S1.E and S2.E? (Note: using ‘.’ for string concatenation)
Answer: August 28, 2019
ABBE Or : LCS(S1,S2).E
15/28
Dynamic programming
Developing a recursive description for LCS
August 28, 2019
16/28
What about the LCS of
that is,
where X 6= Y.
ABCBCX and CABBDY S1.X and S2.Y ?
Trap: its not necessarily LCS(S1, S2).
Dynamic programming
Recursive description for LCS (cont.)
For LCS of
whereX 6=Y,itispossibleX isinS2,orY isinS1
S1 .X and S2 .Y For instance: S1.D and S2.E, that is, for
ABCBCD and CABBDE LCS(S1.D, S2.E) = ABBD
Solution: when X 6= Y , recursively look at both possibilities, and pick the maximum.
LCS(S1.X , S2.Y ) = MAX(LCS(S1.X , S2), LCS(S1, S2.Y )) Recall assumption we have the answers to all smaller
subproblems August 28, 2019
17/28
Dynamic programming
Recursive description for LCS (cont.)
August 28, 2019
18/28
We have covered the cases for S1.X and S2.Y where X = Y and X 6= Y.
The only other possibility is that one or both are empty – the base case(s).
LCS(hi, S2) = LCS(S1, hi) = hi where hi is the empty string
Dynamic programming
Recursive description for LCS (cont.)
Put it all together:
Definition (Longest common subsequence (LCS))
LCS(hi, S2) = LCS(S1.X , S2.X ) = LCS(S1.X , S2.Y ) =
LCS(S1, hi) = hi
LCS(S1, S2).X
MAX(LCS(S1, S2.Y ), LCS(S1.X , S2))
provided X 6= Y
August 28, 2019 19/28
Dynamic programming
Recursive description for LCS Length
Simplify to finding the length of an LCS.
Definition (Length of longest common subsequence)
LCS(hi, S2) = LCS(S1, hi) = 0
LCS(S1.X,S2.X) = LCS(S1,S2)+1
LCS(S1.X , S2.Y ) = MAX(LCS(S1, S2.Y ), LCS(S1.X , S2))
provided X 6= Y
August 28, 2019 20/28
Dynamic programming
Recursive calculations
August 28, 2019
21/28
Recursive implementation using arrays and indexes. Initial call: LCS-LENGTH-REC(S1, S2, n, m)
where length(S1) = n and length(S2) = m (indexing from 1) LCS-LENGTH-REC(S1, S2, i, j)
1 2 3 4 5 6 7 8 9
ifi ==0orj ==0/Basecase
return 0 else
if S1[i] == S2[j]
return LCS-LENGTH-REC(S1, S2, i 1, j 1) + 1
else
return MAX(
LCS-LENGTH-REC(S1, S2, i 1, j), LCS-LENGTH-REC(S1, S2, i, j 1))
Dynamic programming
Recursive calculations
There are ⌦(2min(n,m)) possible subsequences to check We have solved an optimisation problem by finding optimal
solutions to subproblems.
A quick inspection confirms there will be overlapping subproblems, and hence extreme inefficiency for this recursive implementation.
August 28, 2019
23/28
Dynamic programming
Dynamic implementation
LCS-LENGTH-DYN(S1, S2, n, m)
1 2 3 4 5 6 7 8 9
10 11 12 13
T = new int[n][m] fori=1ton
T[i,0] = 0 forj=1tom
T[0,j] = 0 fori=1ton
for j = 1 to m
if S1[i] == S2[j]
T[i,j] = T[i 1,j 1]+1 else if T [i 1, j ] > T [i , j 1]
T[i,j] = T[i 1,j] T[i,j] = T[i,j 1]
T (n) 2 ⇥(nm) August 28, 2019
25/28
else
soln[i,j] =- soln[i,j] =” soln[i,j] =
soln = new int[n][m]
Dynamic programming
Dynamic-programming algorithm
IDEA: ABCBDAB Compute the
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
2
2
2
2
2
2
0
0
0
0
1
1
2
2
2
2
2
2
2
2
2
2
0
0
1
1
1
1
2
2
2
2
2
2
3
3
3
3
0
0
1
1
2
2
2
2
3
3
3
3
3
3
4
4
0
0
1
1
2
2
2
2
3
3
3
3
4
4
4
4
table bottom-up.
Time = Θ(mn).
B D C A B A
August 28, 2019
26/28
November 7, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L15.29
Dynamic programming
Dynamic-programming algorithm
IDEA:
Compute the table bottom-up.
Time = Θ(mn).
Reconstruct LCS by tracing backwards.
A B C B D A B
0 0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
1 1
1
1
1
1
2
2
2
2
2
2
0
0
0
0
1
1
2 2
2
2
2
2
2
2
2
2
0
0
1
1
1
1
2 2
2
2
2
2
3
3
3
3
0
0
1
1
2
2
2
2
3 3
3 3
3
3
4
4
0
0
1
1
2
2
2
2
3
3
3
3
4 4
4 4
B D C A B A
August 28, 2019
27/28
November 7, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L15.30
Dynamic programming
Matrix-chain multiplication – problem overview
Task: Find an order in which to multiply the chain of matrices M1.M2.M3 . . . Mn
which has the least cost (i.e. will be fastest).
Assume that the matrices may have different dimensions, but that the multiplication is well-defined
(e.g. #columns of Mi = #rows of Mi+1).
Example: The matrix chain M1.M2.M3 can be multiplied in two different ways:
M1 .(M2 .M3 ) or (M1 .M2 ).M3 Which one has the least cost (i.e. will be faster)?
September 1, 2019 5/30
Dynamic programming
Matrix-chain multiplication – problem overview
Why do we care?
Large matrix-chain multiplications are:
needed in theoretical and applied physics,
needed in mining large data sets in bioinformatics,
applicable to graphs, when using an adjacency matrix representation.
September 1, 2019 6/30
Dynamic programming
Matrix multiplication
Example, with M1 and M2 both 2 × 2 matrices. M1 = w x M2 = α β
Note:
yz γδ M1.M2 = w.α + x.γ w.β + x.δ
y.α+z.γ y.β+z.δ
M1.M2 ̸= w.α x.β y.γ z.δ
September 1, 2019 7/30
Dynamic programming
Matrix multiplication
Matrices M1 and M2 can only be multiplied if they are compatible: #columns of M1 = #rows of M2.
IfmatrixM1 isp×qandM2 isq×rthenM1.M2 isp×r. Example if M1 is 1×3 and M2 is 3×2:
dg M1 = a b c M2 = e h
fi
They are compatible (#columns of M1 = #rows of M2 = 3) and:
M1.M2 = a.d+b.e+c.f a.g+b.h+c.i
September 1, 2019 8/30
Dynamic programming
Costs of matrix multiplication
A straightforward algorithm to multiply two matrices A of dimension p × q and B of dimension q × r:
MAT-MULT(A,B,p,q,r)
1 2 3 4 5 6
letCbeanewp×rmatrix fori=1top
for j = 1 to r Cij = 0
for k = 1 to q
Cij = Cij +Aik ·Bkj
Total number of multiplications in the inner-loop is p.q.r. Time complexity is Θ(p.q.r).
September 1, 2019 9/30
Dynamic programming
Matrix multiplication
In general, matrix multiplication is not commutative, that is, M1.M2 ̸= M2.M1
but it is associative, that is,
M1.(M2.M3) = (M1.M2).M3
The key point motivating the problem is that calculating the result of M1.M2.M3 can result in huge differences in time factors depending on which of the above two parenthesising choices is made.
September 1, 2019 10/30
Dynamic programming
Matrix multiplication
Recall if M1 is p×q and M2 is q×r then the number of multiplications required is p.q.r
M1 is 10×100
M2 is 100×5 Cost of M1.M2 = 10.100.5
= 5000 iterations of inner loop
September 1, 2019 11/30
Dynamic programming
Matrix-chain multiplication
Now consider M1.M2.M3 where
M1 is 10 × 100 M2 is 100×5 M3 is 5×50
By associativity:
Case 1: (M1.M2).M3, or Case 2: M1.(M2.M3)
= 5000
= 10.5.50 = 2500 = 7500 total
= 100.5.50 = 25, 000 = 10.100.50 = 50, 000 = 75, 000 total
Case 1:
Case 2:
Cost of M1.M2 Cost of (10 × 5).M3
Cost of M2.M3 Cost of M1.(100 × 50)
September 1, 2019 12/30
Dynamic programming
Matrix-chain multiplication: the task
Task: Find an order in which to multiply the chain of matrices M1.M2.M3 . . . Mn
which has the least cost (i.e. will be fastest), assuming that each matrix Mi has dimensions pi−1 × pi so that:
each adjacent pair of matrices is compatible (#columns of Mi = #rows of Mi+1).
The cost of Mi .Mi+1 is pi−1.pi .pi+1. MatrixMi.Mi+1 isofdimensionspi−1 ×pi+1.
Remember that the cost depends on the order.
E.g. M1.(M2.M3) might be cheaper than (M1.M2).M3.
September 1, 2019 13/30
Dynamic programming
Matrix-chain multiplication: the solution?
Why can’t we just enumerate each possible way of multiplying n matrices together and check to see which one is cheapest?
How may ways are there of multiplying n matrices together? M1.M2…..Mn−1.Mn
N(1) = ?
N(2) = ?
N(3) = ?
N(4) = ?
N(n) = ?
– can you define this as a recurrence relation?
September 1, 2019 14/30
Dynamic programming
Quick question
How may ways are there of multiplying n matrices together?
N (1) = 1 N(2) = 1
= N(1) × N(1) N(3) = 2
= N(1) × N(2) + N(2) × N(1)
N(4) = 5
= N(1) × N(3) +
N(2) × N(2) + N(3) × N(1)
(M1 )
(M1 ).(M2 )
(M1 ).(M2 .M3 ) (M1 .M2 ).(M3 )
M1 .(M2 .(M3 .M4 )), (M1 .M2 ).(M3 .M4 ) (M1 .(M2 .M3 )).M4 ,
M1 .((M2 .M3 ).M4 ) ((M1 .M2 ).M3 ).M4
N(n) = n−1 N(i) × N(n − i) i=1
September 1, 2019 15/30
Dynamic programming
Quick question
Show that N(n) ∈ Ω(2n) where N(1) = 1
N(n) = n−1 N(i) × N(n − i) i=1
We have that: N(1) = 1
N(n) ≥ N(1)×N(n−1)+N(n−1)×N(1)=2×N(n−1)
and we can solve the simpler lower-bound recurrence for the solution we seek.
September 1, 2019 16/30
Dynamic programming
Matrix-chain multiplication
Task: find the least cost of muliplying a chain of n matrices: M1.M2…..Mn−1.Mn
Problem: there are an exponential number of possible ways to muliply them (Ω(2n)).
Solution: try to find a dynamic programming solution … first step: think about the problem recursively (ignoring
efficiency).
second step: apply dynamic programming
September 1, 2019 17/30
Dynamic programming
Matrix-chain multiplication: recursive solution
Identify the sub-problems:
LetCi..j givetheminimumcostofmultiplyingMi.Mi+1…..Mj. The solution to our problem will be given by C1..n.
Identify the base cases:
The solution to each sub-problem Ci..i is 0.
Define the recursive case:
Look again at the chain of length 4.
C1..1 + C2..4 + p0.p1.p4 C1..4 = min C1..2 + C3..4 + p0.p2.p4 C1..3 + C4..4 + p0.p3.p4
M1.(. . .) (M1.M2).(M3.M4) (. . .).M4
where
C2..4 = min C2..2 + C3..4 + p1.p2.p4 M2.(M3.M4)
C2..3 + C4..4 + p1.p3.p4 (M2.M3).M4
September 1, 2019 18/30
Dynamic programming
Matrix-chain multiplication: recursive solution
More generally:
Ci..j =mini≤k