Data Structures and Algorithms

Lecture notes: Algorithm paradigms: Dynamic

programming 2025, Part 2

Lecturer: Michel Toulouse

Hanoi University of Science and Technology

[email protected]

20 juin 2025
Outline

Matrix-chain multiplication

Longest common subsequence

Floyd-Warshall algorithm

Computing the binomial coefficient

Problems that fail the optimal substructure test

Conclusion

Final exercises
Matrix-Chain Multiplication Problem (MCM)

Given a sequence of matrices A1 , A2 , . . . , An , where matrix Ai has size a × b, find a

full parenthesization of the product A1 A2 · · · An such that the number of scalar
multiplications required to compute A1 A2 · · · An is minimized.

Full parenthetization : A matrix product is fully parenthesized if it is :

1. a single matrix A
2. the product of two fully parenthesized matrices surrounded by parenthesis
((A1 A2 )(A3 A4 ))

If fully parenthesized, the matrix product of a sequence A1 , A2 , . . . , An is the

product of only two matrices.

Examples : A × B × C , if fully parenthesized, is the product of the matrix (A × B)

by the matrix C , ((A × B) × C ), or the product of matrix A by matrix (B × C ),
(A × (B × C ))
Matrix-Chain Multiplication Problem (MCM)

The product of an a × b matrix with a matrix b × c requires abc scalar

multiplications.

The dimensions of a sequence of n matrices a × b, b × c, c × d, d × e

can be compressed in a sequence d0 , d1 , . . . , dn of n + 1 positive
integers, given the number of columns of Ai is the same as the number
of rows of Ai+1 for each i.
MCM Example

If we are given four matrices, A1 , A2 , A3 , and A4 with sizes 100 × 3,

3 × 20, 20 × 50, 50 × 150, they can be represented by the sequence
100, 3, 20, 50, 150.

Assume we want to compute the product A1 A2 A3 A4 .

Two possible full parenthetization of this product are

1. (A1 (A2 (A3 A4 ))), i.e A1 by matrix (A2 (A3 A4 )) and
2. ((A1 A2 )(A3 A4 )), i.e. matrix (A1 A2 ) by matrix (A3 A4 )
MCM Example

Computing the product as (A1 (A2 (A3 A4 ))) requires 208,500 scalar
multiplications, and computing it as ((A1 A2 )(A3 A4 )) requires 456,000
scalar multiplications.

(A1 ( A2 ( A3 A4 )) ) ( (A1 A2 ) ( A3 A4 ))
100x3 3x20 20x50 50x150 100x3 3x20 20x50 50x150
A1 A2 A3 A4 A1 A2 A3 A4

100x3 3x20 20x150 20*50*150 100x3 3x20 20x150 20*50*150

A1 A2 B A1 A2 B

100x3 3x150 3*20*150 100*3*20 100x20 20x150

A1 C C B
100*3*150 100x150 100*20*150
100x150
Total=204,000 Total=456,000
D D
Dividing MCM into subproblems

Let M(1, n) be a function that returns the minimum number of scalar

multiplications for parenthesizing the sequence of matrices A1 A2 · · · An

The optimal solution M(1, n) will be the product of two fully parenthesized matrices
that looks like (A1 · · · Ak )(Ak+1 · · · An ), where 1 ≤ k < n, where the two half
sequences are fully parenthesized as well.

Given that each value of k, 1 ≤ k < n, divides the n matrices into two different full
parenthesized matrices, the optimal solution is the value of k for which the number
of scalar multiplications is minimized :

M(1, n) = min (M(1, k) + M(k + 1, n) + d0 dk dn ).

1≤k<n
A divide&conquer algorithm for MCM

int M(i, j)
if i == j then return (0) ; /* based case, a single matrix has 0 scalar multiplication */
else
return mini≤k<j (M(i, k) + M(k + 1, j) + di−1 dk dj ) ;

The recursion tree for the MCM problem with 4 matrices :

M[1,4] =Already Computed

M[1,1] M[2,4] M[1,2] M[3,4] M[1,3] M[4,4]

M[2,2] M[3,4] M[2,3] M[4,4] M[1,1] M[2,2] M[3,3] M[4,4] M[1,1] M[2,3] M[1,2] M[3,3]

M[3,3] M[4,4] M[2,2] M[3,3]

M[2,2] M[3,3] M[1,1] M[2,2]
Divide-&-conquer for MCM

M[1,4]
=Already Computed

M[1,1] M[2,4] M[1,2] M[3,4] M[1,3] M[4,4]

M[2,2] M[3,4] M[2,3] M[4,4] M[1,1] M[2,2] M[3,3] M[4,4] M[1,1] M[2,3] M[1,2] M[3,3]

M[3,3] M[4,4] M[2,2] M[3,3]

M[2,2] M[3,3] M[1,1] M[2,2]

▶ Notice that many of the calls are repeated (all the shaded boxes).
▶ The divide-&-conquer algorithm has the following recurrence
n−1
X
T (n) = (T (k) + T (n − k)) + cn
k=1

with T (0) = 0 and T (1) = 1.

Analysis of the recurrence for MCM

If n > 0,
n−1
X
T (n) = 2 T (k) + cn
k=1

Therefore Pn−1
T (n) − T (n − 1) = (2 k=1 T (k) + cn)
Pn−2
− (2 k=1 T (k) + c(n − 1))
= 2T (n − 1) + c
That is

T (n) = 3T (n − 1) + c
Analysis of the recurrence for MCM

using the substitution method :

T (n) = 3T (n − 1) + c
= 3(3T (n − 2) + c) + c
= 9T (n − 2) + 3c + c
= 9(3T (n − 3) + c) + 3c + c
= 27T (n − 3) + 9c + 3c + c
= 3k T (n − k) + c k−1 3l
P
n Pn−1 l=0
l
= 3 T (0) + c l=0 3
n
= c3n + c 3 2−1
= (c + c2 )3n − c2
T (n) ∈ Θ(3n ).

This recurrence can be solved using the recursion tree method. There are n − 1
levels, each level i execute 3i c operations, yielding the following summation :
30 + 31 + 32 + · · · + 3n−1 , the dominant term in this expression is 3n−1 ∈ Θ(3n )
Optimal Substructure

MCM satisfies the requirement that optimal solutions combine

solutions of two subproblems that are also optimal

The parenthesization of A1 · · · Ak and Ak+1 · · · An must be optimal

Otherwise there exist another parenthetisation M ′ of one of the two

subproblems, for example A1 · · · Ak , such that M ′ (1, k) < M(1, k) in
which case M(1, n) = M(1, k) + M(k + 1, n) + d0 × dk × dn is not an
optimal solution
Dynamic programming solution

MCM is a candidate for DP :

1. The recursive algorithm solves some subproblems more than one
time
2. It satisfies the optimal substructure condition : an optimal
solution to (A1 · · · Ak )(Ak+1 · · · An ) is based on parenthesizations
of A1 · · · Ak and Ak+1 · · · An that are optimal as well.
Bottom up DP solution for MCM

int M(i, j)
if i == j then return (0) ;
else
return mini≤k<j (M(i, k) + M(k + 1, j) + di−1 dk dj ) ;

Given a sequence A1 A2 . . . An of n matrices, defines an 2-dimensional n × n array M

1 2 3 4
1
2
3
4

In the 2-dimensional array

▶ row i refers to the position of the first matrix in the sequence
▶ column j refers to the position of the last matrix in the sequence.
An entry M[i, j] in the table stores the minimum number of scalar multiplications for the
subsequence of consecutive matrices Ai Ai+1 . . . Aj . The solution to A1 A2 . . . An is stored in
M[1, n].
Bottom up DP solution for MCM

The Bottom up DP algorithm for MCM is as follow

▶ Compute the number of scalar multiplications for all sequences of length 1 (base case
of the D&C), i.e. 0
▶ Compute the number of scalar multiplications for all sequences of length 2, the
solution to AB is a × b × c. There are n − 1 subsequences of length 2.
▶ Compute the number of scalar multiplications for all sequences of length 3. There are
n − 2 subsequences of length 3. Each sequence of length 3 has 2 subsequences, one
of length 1 and one of length 2, the solution to each of these two subsequences is
already in the DP table.
▶ Compute the number of scalar multiplications for all sequences of length 4.
▶ until n
MCM : Dynamic Programming Algo.

int MCM(int *M, int n) {

int M[n, n], min ;
for (i = 1; i ≤ n; i + +) M[i, i] = 0 ;
for (s = 1; s < n; s + +)
for (i = 1; i ≤ n − s; i + +)
min = ∞ ;
for (k = i; k < i + s; k + +)
if (M[i, k] + M[k + 1, i + s] + di−1 dk di+s < min)
min = M[i, k] + M[k + 1, i + s] + di−1 dk di+s ;
M[i, i + s] = min ;}

This
Pn algorithm has 3 nested loops. The summation is
Pn−1 Pi+s
s=1 i=1 k=i 1. The complexity of dynamic programming MCM is
3
Θ(n ).
Bottom up DP solution for MCM

M[1,4] =Already Computed

M[1,1] M[2,4] M[1,2] M[3,4] M[1,3] M[4,4] int M(i, j)

if i == j then return (0) ;
M[2,2] M[3,4] M[2,3] M[4,4] M[1,1] M[2,2] M[3,3] M[4,4] M[1,1] M[2,3] M[1,2] M[3,3] else
M[3,3] M[4,4] M[2,2] M[3,3] return mini≤k<j (M(i, k) + M(k + 1, j) + di−1 dk dj ) ;
M[2,2] M[3,3] M[1,1] M[2,2]

Base cases are subsequences of length 1 such as [1, 1], [2, 2], . . ., [n, n]. The base cases will
appear in the diagonal M[i, i] of the n × n table, the number of scalar multiplications is 0.

1 2 3 4
1 0
2 0
3 0
4 0
A dynamic programming solution to MCM
int M(i, j)
if i == j then return (0) ;
else
return mini≤k<j (M(i, k) + M(k + 1, j) + di−1 dk dj ) ;

The next larger problem sizes to solve involve the product of two consecutive
matrices, the subproblems are subsequences of length 2.
We multiple each 2 consecutive matrices, i.e. (1, 2), (2, 3), (n − 1, n), and store the
solution into M[i, i + 1]

Here k can only take one value, k = i. According to the recursive algo
M[i, i + 1] = M[i, i] + M[i + 1, i + 1] + di−1 dk dj = di−1 dk dj

1 2 3 4 5
0 d0 d1 d2 1
0 d1 d2 d3 2
0 d2 d3 d4 3
0 d3 d4 d5 4
0 5
A dynamic programming solution to MCM
int M(i, j)
if i == j then return (0) ;
else
return mini≤k<j (M(i, k) + M(k + 1, j) + di−1 dk dj ) ;

The next larger problem sizes to solve involve the product of three
consecutive matrices.
We multiple each 3 consecutive matrices, i.e. (1, 3), (2, 4), (n − 2, n),
and store the solution into M[i, i + 2]
Here k can only take two values, k = i and k = i + 1. According to the
k<j
recursive algo M[i, i + 2] = mink=i (M[i, k] + M[k + 1, j] + di−1 dk dj )
1 2 3 4 5
0 d0 d1 d2 ? 1
0 d1 d2 d3 ? 2
0 d2 d3 d4 ? 3
0 d3 d4 d5 4
0 5
MCM dynamic programming Example

We are given the sequence (4, 10, 3, 12, 20, 7).

The 5 matrices have sizes 4 × 10, 10 × 3, 3 × 12, 12 × 20, and 20 × 7.

We need to compute M[i, j], 1 ≤ i, j ≤ 5.

We know M[i, i] = 0 for all i.

1 2 3 4 5
0 1
0 2
0 3
0 4
0 5
MCM Example

We proceed, working away from the diagonal. We compute the optimal

solutions for products of 2 matrices.
Given the sequence (4, 10, 3, 12, 20, 7) :
M[1, 2] = 4 × 10 × 3 = 120,
M[2, 3] = 10 × 3 × 12 = 360,
M[3, 4] = 3 × 12 × 20 = 720,
M[4, 5] = 12 × 20 × 7 = 1680
1 2 3 4 5
0 120 1
0 360 2
0 720 3
0 1680 4
0 5
MCM Example (continued)
There are two ways one can split a sequence of 3 matrices in two
sub-sequences : (1) (2,3) or (1,2) (3). Given 5 matrices there are 3
sequences of 3 matrices. (4, 10, 3, 12, 20, 7)

M[1, 2] + M[3, 3] + d0 d2 d3 = 120 + 0 + 4 · 3 · 12 = 264
M[1, 3] = min
M[1, 1] + M[2, 3] + d0 d1 d3 = 0 + 360 + 4 · 10 · 12 = 840

M[2, 3] + M[4, 4] + d1 d3 d4 = 360 + 0 + 10 · 12 · 20 = 2760
M[2, 4] = min
M[2, 2] + M[3, 4] + d1 d2 d4 = 0 + 720 + 10 · 3 · 20 = 1320

M[3, 4] + M[5, 5] + d2 d4 d5 = 720 + 0 + 3 · 20 · 7 = 1140
M[3, 5] = min
M[3, 3] + M[4, 5] + d2 d3 d5 = 0 + 1680 + 3 · 12 · 7 = 1932

1 2 3 4 5 1 2 3 4 5
0 120 1 0 120 264 1
0 360 2 0 360 1320 2
⇒
0 720 3 0 720 1140 3
0 1680 4 0 1680 4
0 5 0 5
MCM Example (continued again)

A sequence of 4 matrices can be split in 3 different ways (1) (2,4), or

(1,2) (3,4), or (1,3) (4). Given 5 matrices, there are 2 sequences of 4
matrices. (4, 10, 3, 12, 20, 7)

 M[1, 3] + M[4, 4] + d0 d3 d4 = 264 + 0 + 4 · 12 · 20 = 1224
M[1, 4] = min M[1, 2] + M[3, 4] + d0 d2 d4 = 120 + 720 + 4 · 3 · 20 = 1080
M[1, 1] + M[2, 4] + d0 d1 d4 = 0 + 1320 + 4 · 10 · 20 = 2120


 M[2, 4] + M[5, 5] + d1 d4 d5 = 1320 + 0 + 10 · 20 · 7 = 2720
M[2, 5] = min M[2, 3] + M[4, 5] + d1 d3 d5 = 360 + 1680 + 10 · 12 · 7 = 2880
M[2, 2] + M[3, 5] + d1 d2 d5 = 0 + 1140 + 10 · 3 · 7 = 1350


1 2 3 4 5 1 2 3 4 5
0 120 264 1 0 120 264 1080 1
0 360 1320 2 0 360 1320 1350 2
⇒
0 720 1140 3 0 720 1140 3
0 1680 4 0 1680 4
0 5 0 5
MCM Example (continued again)

Now the product of 5 matrices. (4, 10, 3, 12, 20, 7)



 M[1, 4] + M[5, 5] + d0 d4 d5 = 1080 + 0 + 4 · 20 · 7 = 1640
M[1, 3] + M[4, 5] + d0 d3 d5 = 264 + 1680 + 4 · 12 · 7 = 2016

M[1, 5] = min

 M[1, 2] + M[3, 5] + d0 d2 d5 = 120 + 1140 + 4 · 3 · 7 = 1344
M[1, 1] + M[2, 5] + d0 d1 d5 = 0 + 1350 + 4 · 10 · 7 = 1630


1 2 3 4 5 1 2 3 4 5
0 120 264 1080 1 0 120 264 1080 1344 1
0 360 1320 1350 2 0 360 1320 1350 2
⇒
0 720 1140 3 0 720 1140 3
0 1680 4 0 1680 4
0 5 0 5
MCM Example : Optimal Cost and Solution

The optimal cost is M[1, 5] = 1344.

What is the optimal parenthesization ?

We didn’t keep track of enough information to find that out.

The algorithm can be modified slightly to keep enough information to

derive the optimal parenthesization.

Each time the optimal value for M[i, j] is found, store also the value of
k that was used.

Then we can just work backwards, partitioning the matrices according

to the optimal split.
MCM Example : Optimal Solution

If we did this for the example, we would get

1 2 3 4 5
0 120/1 264/2 1080/2 1344/2 1
0 360/2 1320/2 1350/2 2
0 720/3 1140/4 3
0 1680/4 4
0 5

The k value for the solution is 2, so we have (A1 A2 )(A3 A4 A5 ). The

first half is done.
MCM Example : Optimal Solution

1 2 3 4 5
0 120/1 264/2 1080/2 1344/2 1
0 360/2 1320/2 1350/2 2
0 720/3 1140/4 3
0 1680/4 4
0 5

The optimal solution for the second half comes from entry M[3, 5].

The value of k here is 4, so now we have (A1 A2 )((A3 A4 )A5 ).

Thus the optimal solution is to parenthesize as (A1 A2 )((A3 A4 )A5 ).

Exercises 6 and 7 on matrix-chain multiplications

6. Given the sequence 2, 3, 5, 2, 4, 3, how many matrices do we

have and what is the dimension of each matrix. Using the previous
dynamic programming algorithm for matrix-chain multiplication,
compute the parenthetization of these matrices that minimize the
number of scalar multiplications.
7. Given the sequence 5, 4, 6, 2, 7, how many matrices do we have
and what is the dimension of each matrix. Using the previous
dynamic programming algorithm for matrix-chain multiplication,
compute the parenthetization of these matrices that minimize the
number of scalar multiplications.
Exercises 6 and 7 on matrix-chain multiplications

6. Given the sequence 2, 3, 5, 2, 4, 3, how many matrices do we have and what

is the dimension of each matrix. Using the previous dynamic programming
algorithm for matrix-chain multiplication, compute the parenthetization of
these matrices that minimize the number of scalar multiplications.
Solution (see details in the next slides) :
1 2 3 4 5
0 30/1 42/1 58/3 78/3 1
0 30/2 54/3 72/3 2
0 40/3 54/3 3
0 24/4 4
0 5

(A1 )(A2 A3 )(A4 A5 )

7. Given the sequence 5, 4, 6, 2, 7, how many matrices do we have and what is
the dimension of each matrix. Using the previous dynamic programming
algorithm for matrix-chain multiplication, compute the parenthetization of
these matrices that minimize the number of scalar multiplications.
Solution : 120, 48, 84, then 88, 104, then 158
Solving exercise 6

We compute the optimal solutions for products of 2 matrices.

Given the sequence (2, 3, 5, 2, 4, 3) :
M[1, 2] = 2 × 3 × 5 = 30,
M[2, 3] = 3 × 5 × 2 = 30,
M[3, 4] = 5 × 2 × 4 = 40,
M[4, 5] = 2 × 4 × 3 = 24
1 2 3 4 5
0 30 1
0 30 2
0 40 3
0 24 4
0 5
Solving exercise 6

There are two ways one can split a sequence of 3 matrices in two
sub-sequences : (1) (2,3) or (1,2) (3). Given 5 matrices there are 3
sequences of 3 matrices. (2, 3, 5, 2, 4, 3)

M[1, 2] + M[3, 3] + d0 d2 d3 = 30 + 0 + 2 · 2 · 2 = 50
M[1, 3] = min
M[1, 1] + M[2, 3] + d0 d1 d3 = 0 + 30 + 2 · 3 · 2 = 42

M[2, 3] + M[4, 4] + d1 d3 d4 = 30 + 0 + 3 · 2 · 4 = 54
M[2, 4] = min
M[2, 2] + M[3, 4] + d1 d2 d4 = 0 + 40 + 3 · 5 · 4 = 100

M[3, 4] + M[5, 5] + d2 d4 d5 = 40 + 0 + 5 · 4 · 3 = 100
M[3, 5] = min
M[3, 3] + M[4, 5] + d2 d3 d5 = 0 + 24 + 5 · 2 · 3 = 54

1 2 3 4 5
0 30/1 42/1 1
0 30/2 54/3 2
0 40/3 54/3 3
0 24/4 4
0 5
Solving exercise 6

A sequence of 4 matrices can be split in 3 different ways (1) (2,4), or

(1,2) (3,4), or (1,3) (4). Given 5 matrices, there are 2 sequences of 4
matrices. (2, 3, 5, 2, 4, 3)

 M[1, 3] + M[4, 4] + d0 d3 d4 = 42 + 0 + 2 · 2 · 4 = 58
M[1, 4] = min M[1, 2] + M[3, 4] + d0 d2 d4 = 30 + 40 + 2 · 5 · 4 = 120
M[1, 1] + M[2, 4] + d0 d1 d4 = 0 + 54 + 2 · 3 · 4 = 78


 M[2, 4] + M[5, 5] + d1 d4 d5 = 54 + 0 + 3 · 4 · 3 = 90
M[2, 5] = min M[2, 3] + M[4, 5] + d1 d3 d5 = 30 + 24 + 3 · 2 · 3 = 72
M[2, 2] + M[3, 5] + d1 d2 d5 = 0 + 54 + 3 · 5 · 3 = 99


1 2 3 4 5
0 30/1 42/1 58/3 1
0 30/2 54/3 72/3 2
0 40/3 54/3 3
0 24/4 4
0 5
Solving exercise 6

Now the product of 5 matrices. (2, 3, 5, 2, 4, 3)



 M[1, 4] + M[5, 5] + d0 d4 d5 = 58 + 0 + 2 · 4 · 3 = 82
M[1, 3] + M[4, 5] + d0 d3 d5 = 42 + 24 + 2 · 2 · 3 = 78

M[1, 5] = min

 M[1, 2] + M[3, 5] + d0 d2 d5 = 30 + 54 + 2 · 5 · 3 = 114
M[1, 1] + M[2, 5] + d0 d1 d5 = 0 + 72 + 2 · 3 · 3 = 90


1 2 3 4 5
0 30/1 42/1 58/3 78/3 1
0 30/2 54/3 72/3 2
0 40/3 54/3 3
0 24/4 4
0 5
Solving exercise 6

The minimum number of scalar multiplications is stored in M[1, 5] = 78.

The parenthesization that yields this solution is obtained by working backwards in

the dynamic programming table the partitioning of each sequence into two
subsequences of matrices.
We start with sequence A1 A2 A3 A4 A5 which, according to the entry M[1,5] of the
table, is decomposed into two subsequences between the third and the fourth matrix
(A1 A2 A3 )(A4 A5 )
Then we move into the entry M[1,3] of the table to find the decomposition of the
sequence A1 A2 A3 . According to the table this sequence is decomposed between the
first and second matrix (A1 )(A2 A3 )

The solution is (A1 )(A2 A3 )(A4 A5 ).

Proof the solution to exercise 6 is correct

The dimensions of these 3 matrices in the solution (A1 )(A2 A3 )(A4 A5 )

are A1 = (2, 3), A2 A3 = (3, 2), A4 A5 = (2, 3).

Thus the number of scalar multiplications to multiply

▶ A1 (A2 A3 ) = 2 × 3 × 2 = 12
▶ (A1 A2 A3 )(A4 A5 ) = 2 × 2 × 3 = 12

There are 30 scalar multiplications to multiply A2 × A3

There are 24 scalar multiplications to multiply A4 × A5

Thus the total number of scalar multiplications using the

parenthetization (A1 )(A2 A3 )(A4 A5 ) is 12 + 12 + 30 + 24 = 78, as in
table M[1,5]
Longest common subsequence (LCS)

A subsequence is a sequence that appears in the same relative order,

but not necessarily contiguous. For example, ”abc” and ”ace” are
subsequences of ”abcdef”.

LCS problem : Given 2 sequences, X = [x1 . . . xm ] and Y = [y1 . . . yn ],

find a subsequence common to both, but whose length is longest.

For example, ”ADH” is a subsequence of length 3 of the input

sequences ”ABCDGH” and ”AEDFHR”.
Brute-force algorithm for LCS

Brute-force algorithm : For every subsequence of X (of size m), check

whether it is a subsequence of Y (of size n). Asymptotic cost :
Θ(n2m ). Proof :
▶ 2m − 1 subsequences of X to check
▶ Each subsequence takes Θ(n) time to check : scan Y for first
letter, from there scan for second, and so on.
Optimal substructure

Consider the input sequences be X = [x1 . . . xm ] and Y = [y1 . . . yn ]

respectively of length m and n.

Let lcs(X [1..m], Y [1..n]) be the length of the LCS of X and Y . The
length of the LCS is computed recursively as follow :

▶ if the last character of both sequences match, i.e. if

X [m] == Y [n] then
lcs(X [1..m], Y [1..n]) = 1 + lcs(X [1..m − 1], Y [1..n − 1])

▶ if the last character of both sequences do not match, i.e. if

X [m] ̸= Y [n] then lcs(X [1..m], Y [1..n]) =
max(lcs(X [1..m − 1], Y [1..n]), lcs(X [1..m], Y [1..n − 1]))
Optimal substructure

Given sequences ”AGGTAB” and ”GXTXAYB”, last characters match,

so length of LCS can be written as :
lcs(”AGGTAB”, ”GXTXAYB”) = 1 + lcs(”AGGTA”, ”GXTXAY ”)

For sequences ”ABCDGH” and ”AEDFHR”, the last characters do not

match, so length of LCS is : lcs(”ABCDGH”, ”AEDFHR”) =
max(lcs(”ABCDG ”, ”AEDFHR”), lcs(”ABCDGH”, ”AEDFH”))

So the LCS problem has optimal substructure property as the optimal

solution of the main problem can be solved using optimal solutions to
subproblems.
A divide-&-conquer algorithm for LCS

int lcs(char* X, char* Y, int i, int j)

if (i == 0||j == 0) return 0 ;
if (X [i] == Y [j])
return 1 + lcs(X , Y , i − 1, j − 1) ;
else
return max(lcs(X , Y , i − 1, j), lcs(X , Y , i, j − 1)) ;

Time complexity of this recursive algorithm is O(2n ) in worst case and

worst case happens when all characters of X and Y mismatch i.e.,
length of LCS is 0.

Building a partial call tree for sequences AXYT and AYZX , it can be
verified that the recursive algorithm solves the same subproblems
several times. Soon you will observe that lcs(”AXY”, ”AYZ”) is being
solved twice.
Top Down DP algorithm for LCS

int tddplcs(char* X , char* Y , int i, int j )

if (i == 0||j == 0)
table[i, j] = 0 ; /* re-calculate each time */
return table[i, j] ;
if (X [i] == Y [j])
if (table[i, j] == −1)
table[i, j] = 1 + tddplcs(X , Y , i − 1, j − 1) ;
return table[i, j]
else return table[i, j] ;
if (X [i] ̸= Y [j])
if (table[i, j] == −1)
table[i, j] = max(tddplcs(X , Y , i, j − 1),
tddplcs(X , Y , i − 1, j)) ;
return table[i, j]
else return table[i, j] ;
Bottom up DP for LCS

LCS-Length(char* X , char* Y , int m, int n)

let b[1..m, 1..n] and c[0..m, 0..n]
for i = 1 to m c[i, 0] = 0
for j = 0 to n c[0, j] = 0
for i = 1 to m
for j = 1 to n
if X [i] == Y [j]
c[i, j] = c[i − 1, j − 1] + 1
b[i, j] =”↖”
else if c[i − 1, j] ≥ c[i, j − 1]
c[i, j] = c[i − 1, j]
b[i, j] =”↑”
else c[i, j] = c[i, j − 1]
b[i, j] =”←”
return c and b

Computational complexity is Θ(mn)

Example

LCS-Length(char* X , char* Y , int m, int n)

let b[1..m, 1..n] and c[0..m, 0..n]
for i = 1 to m c[i, 0] = 0
for j = 0 to n c[0, j] = 0
for i = 1 to m
for j = 1 to n
if X [i] == Y [j]
c[i, j] = c[i − 1, j − 1] + 1
b[i, j] =”↖”
else if c[i − 1, j] ≥ c[i, j − 1]
c[i, j] = c[i − 1, j] X = [ABCBDAB]
b[i, j] =”↑”
Y = [BDCABA]
else c[i, j] = c[i, j − 1]
b[i, j] =”←” m = 7; n = 6
return c and b LCS is [BCBA]
Example

int lcs(char *X, char *Y, int i, int j )

if (i == 0||j == 0) return 0 ;
if (X [i] == Y [j])
return 1 + lcs(X , Y , i − 1, j − 1) ;
else
return max(lcs(X , Y , i, j − 1),
lcs(X , Y , i − 1, j)) ;

X = [ABCBDAB]
Y = [BDCABA]
m = 7; n = 6
LCS is [BCBA]
Printing the LCS

Print-LCS(b,X,i,j)
if i == 0 or j == 0 return
if b[i, j] == ”↖”
Print-LCS(b,X,i-1,j-1)
print xi
else if b[i, j] == ”↑”
Print-LCS(b,X,i-1,j)
else if b[i, j] == ”←”
Print-LCS(b,X,i,j-1)

▶ Initial call is Print-LCS(b,X,m,n)

▶ b[i, j] points to table entry whose subproblem we used in solving LCS of Xi and Yj .
▶ When b[i, j] =↖, we have extended LCS by one character. So longest common
subsequence = entries with ↖ in them

Computational complexity is Θ(m + n)

Exercises : longest common subsequences

8. Find the LCS for X = [ABAZDC ] and Y = [BACBAD]

Solution : ABAD of length 4
B A C B A D
A 0 1 1 1 1 1
B 1 1 1 2 2 2
A 1 2 2 2 3 3
Z 1 2 2 2 3 3
D 1 2 2 2 3 4
C 1 2 3 3 3 4
9. Prove that the LCS for the input sequences X = [ABCDGH] and
Y = [AEDFHR] is ”ADH” of length 3.
Sol : Since the dynamic programming algorithm for this problem always solve
it to optimality, the algorithm is a proof by construction. Use DP algo. to
solve this problem instance, which constructs the solution, if the solution is
the same as string ”ADH”, this is the proof.
Shortest path problem
A path between a pair of vertices i, j in a weighted graph is a sequence of
consecutive edges linking i to j that has a cost equal to the sum of the path’s edge
weights
In the directed graph below, the sequence (0,2,7,3,6) is a path connecting vertices 0
and 6 that has cost 0.26 + 0.34 + 0.39 + 0.52 = 1.51
In a weighted graph, the shortest path problem consists to find the path of
minimum weight between a pair of vertices

In this graph there are several paths between vertices 0,6 beside the one we found
above : (0,2,7,5,1,3,6), (0,4,7,3,6), (0,4,7,5,1,3,6), (0,4,5,7,3,6), etc.
The All-Pairs Shortest-Path Problem

Find the shortest path distance between each pair of vertices in a

nonnegative weighted graph
The graph is represented by a distance matrix L[i, j] which gives the length of each
edge :
▶ L[i, i] = 0
▶ L[i, j] ≥ 0 if i ̸= j,
▶ L[i, j] = ∞ if the edge (i, j) does not exist.
 
0 5 ∞ ∞
 50 0 15 15 
L= 
 30 ∞ 0 15 
15 ∞ 5 0

The dynamic programming algorithm we study to solve this problem is called the
Floyd-Warshall algorithm.
First find a way to reduce the problem size

Let assume the n nodes in the graph are numbered consecutively from 1 to n
We seek the shortest path between a pair of nodes i, j. Initially this path has the
option to pass through any intermediary nodes in the set {1, 2, . . . , n} \ {i, j}.

We reduce the size of the problem by reducing the set of options in

{1, 2, . . . , n} \ {i, j} that can be included in the shortest path between i and j.
For example, we can remove node k from the intermediate set of nodes, thus the
path between i and j can only pass through nodes in the set {1, 2, . . . , n} \ {i, j, k}.
The problem is now to find the shortest distance between i, j going through a set of
n − 3 intermediary nodes ({1, 2, . . . , n} \ {i, j, k}) rather than a set of n − 2 nodes
Building sub-problems

Once a node k has been excluded from the intermediary set, one must decide what
to do with k.
There are two choices :
1. k is made mandatory part of the path between i and j,
2. k is excluded permanently from this path.
Building sub-problems : base case
If recursively we keep removing vertices from the intermediary set, this set is
eventually empty.
Furthermore, if the removed nodes are never considered to be include in the path,
the cost of the shortest path between a pair of nodes i and j is the cost of the direct
edge, this is the base case.

Assume the intermediate set in the graph below is empty, there is no edge between
nodes 0 and 2, thus the length of the shortest path, the self-solution, base case, is
∞
Building sub-problems : keeping k in the path
Assume the removed node k is made a mandatory part of the shortest pth between
nodes i and j
Consider the graph below, where node 4 is removed from the intermediate set,
leaving this set to be {1, 3}.
Furthermore, node 4 is made a necessary part of the shortest path between 0 and 2.
Having node 4 in the path between 0 and 2 creates two new shortest path
sub-problems :
▶ one between 0 and 4 and
▶ another between 4 and 2
Where both sub-problems have intermediate set {0, 1, 2, 3, 4} \ {0, 2, 4} = {1, 3}
A divide-&-conquer algo for all-pairs shortest path

Denote the function that returns the cost of the shortest path between
nodes i, j using only intermediary nodes from the set {1, 2, . . . , k} as
Path(i, j, k)

Base case : the value returns by Path(i, j, ∅) is the cost of the direct
edge from i to j in the graph, i.e. Path(i, j, ∅) = L[i, j]
Costs of shortest paths in a divide-&-conquer algo
Assume the nodes in the graph are numbered consecutively from 1 to n. There are
two possible ways one can compute the cost of Path(i, j, k)
1. node k is not part of the shortest path between i, j, the cost of
Path(i, j, k) = Path(i, j, k − 1) where Path(i, j, k − 1) is a new subproblem
solved using nodes from the set {1, 2, . . . , k − 1}
2. node k is part of the shortest path between i, j. Then there are two
subproblems : path from i to k and path from k to j using only intermediate
nodes {1, 2, . . . , k − 1}.

Path(i, j, k) = Path(i, k, k − 1) + Path(k, j, k − 1) is the length of the path from i

to k to j, the concatenation of the shortest path from i to k and the shortest path
from k to j, each one only using intermediate vertices in {1, 2, . . . , k − 1}.
A divide-&-conquer algo for all-pairs shortest path

function Path(i, j, k)
if (k == ∅) then return L[i, j] ; /* Base case */
else
return min(Path(i, j, k − 1),
Path(i, k, k − 1) + Path(k, j, k − 1))

The above algorithm is called for each pair of node i, j in a graph. It is also used to
design the Floyd-Warshall dynamic programming algorithm that solves the all pairs
of shortest paths problem.
Call tree for D-&-C between nodes 0 and 2

{1,3,4} 4
P(0,2,4)
4
{1,3} P(0,2,3)

{1} 4 P(0,2,1) P(0,3,1)+ P(3,2,1) 9

{∅} P(0,2,∅) P(0,1,∅)+ P(1,2,∅)

∞ 3 1

P(3,2,∅) P(3,1,∅)+ P(1,2,∅)

2 ∞ 1

P(0,3,∅) P(0,1,∅)+ P(1,3,∅) 13

7 3 4 {1,3}
8 P(0,4,3)+ P(4,2,3) 5

8 ∞ ∞ 5
P(0,3,1)+P(3,4,1) P(4,2,1) P(4,3,1)+P(3,2,1) {1}
P(0,4,1)

P(0,4,∅) P(3,4,∅) P(4,2,∅) P(4,3,∅) P(3,2,∅) {∅}

P(0,3,∅)
8 ∞ 3 2
7 ∞
P(0,1,∅)+ P(1,4,∅)
P(3,1,∅)+ P(1,4,∅) P(4,1,∅)+ P(1,4,∅)
3 ∞ P(3,1,∅)+ P(1,2,∅)
P(0,1,∅)+ P(1,3,∅) ∞ ∞ ∞ ∞ ∞ 1
3 4
Conditions for using DP

The function Path(i, j, k) has to be called for each pair of nodes i, j in the graph.
Already from the previous small example, we see subproblems been computed
repetitively, for example P(0, 3, 1) or P(3, 2, ∅)

The recurrence relation for Path(i, j, k) is T (n) = 3T (n − 1) + 1 solving in O(3n ),

which is astonishingly costly considering this is the cost to paid for each pair of
nodes in the graph.
Conditions for using DP

The problem satisfies the optimal substructure property, the optimal solution to
Path(i, j, k) is based on the optimal solution of Path(i, k, k − 1) and
Path(k, j, k − 1). Suppose this is not the case, and assume that the subpath i to k
is not optimal. Then there exists another subpath i to k with cost
Path(i, k, k − 1)′ < Path(i, k, k − 1) which contradicts that Path(i, j, k) is optimal.
Floyd-Warshall Algorithm
It is a bottom up dynamic programming algorithm. Considering the nodes in the
graph are numbered consecutively from 1 to n, the DP algorithms starts by
computing the shortest path for all pairs of nodes for k = 0 (no intermediate node).
Then it considers k = 1, k = 2, until k = n.

A 3-dimensional array n × n × n D gives the length of the shortest path between

each pair of nodes for the different values of k

D0,i,j = L, the length of the direct edge between nodes i, j.

Algorithm Floyd(L[n, n])

D0 = L
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
D[k, i, j] = min(D[k − 1, i, j], D[k − 1, i, k] + D[k − 1, k, j])
return Dk

After each iteration k, Dk contains the length of the shortest paths that only use
nodes in {1, 2, . . . , k} as intermediate nodes.
Floyd Algorithm

Algorithm Floyd(L[n, n])

D0 = L
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
D[k, i, j] = min(D[k − 1, i, j], D[k − 1, i, k] + D[k − 1, k, j])
return Dk

At iteration k, the algo checks each pair of nodes (i, j) whether or not there exists a
path from i to j passing through node k that is better than the present optimal
path passing only through nodes in {1, 2, . . . , k − 1}.

D[k, i, j] = min(D[k − 1, i, j], D[k − 1, i, k] + D[k − 1, k, j])

Execution of Floyd’s algorithm
Algorithm Floyd(L[n, n])
D0 = L
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
D[k, i, j] = min(D[k − 1, i, j], D[k − 1, i, k] + D[k − 1, k, j])
return Dk
Base case D0 = L, the smallest problem instances
Execution of Floyd’s algorithm
Algorithm Floyd(L[n, n])
D0 = L
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
D[1, i, j] = min(D[0, i, j], D[0, i, k] + D[0, k, j])
return Dk

For k = 1, compute the shortest path between each pair of nodes (i, j)
when the path is allowed to pass through node 1.
Execution of Floyd’s algorithm
Algorithm Floyd(L[n, n])
D0 = L
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
D[2, i, j] = min(D[1, i, j], D[1, i, k] + D[1, k, j])
return Dk

For k = 2, compute the shortest path between each pair of nodes (i, j)
when the path is allowed to pass through nodes 1 and 2.
Execution of Floyd’s algorithm
Algorithm Floyd(L[n, n])
D0 = L
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
D[3, i, j] = min(D[2, i, j], D[2, i, k] + D[2, k, j])
return Dk

For k = 3, compute the shortest path between each pair of nodes (i, j)
when the path is allowed to pass through nodes {1, 2, 3}.
Execution of Floyd’s algorithm
Algorithm Floyd(L[n, n])
D0 = L
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
D[4, i, j] = min(D[3, i, j], D[3, i, k] + D[3, k, j])
return Dk

For k = 4, solution, compute the shortest path between each pair of

nodes (i, j) when the path is allowed to pass through any nodes.
Computing the shortest paths

We want to know the shortest paths, not just their length.

For that we create a 2-dimensional matrix P of size n × n.

Then use the following algorithm in place of the previous one :

Algorithm Floyd(D[n, n])

Input : A 3-dimensional array D of shortest path lenghts
Output : The shortest path between every pair of nodes
P[n, n] an n × n array initialized to 0
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
if D[k − 1, i, k] + D[k − 1, k, j] < D[k − 1, i, j] then
D[k, i, j] = D[k − 1, i, k] + D[k − 1, k, j]
P[i, j] = k ;
Computing the shortest pathsK k = 1

Algorithm Floyd(D[n, n])

Input : A 3-dimensional array D of shortest path lenghts
Output : The shortest path between every pair of nodes
P[n, n] an n × n array initialized to 0
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
if D[k − 1, i, k] + D[k − 1, k, j] < D[k − 1, i, j] then
D[k, i, j] = D[k − 1, i, k] + D[k − 1, k, j]
P[i, j] = k ;

0 0 0 0
0 0 0 0
0 1 0 0
0 1 0 0
Computing the shortest paths : k = 2

Algorithm Floyd(D[n, n])

Input : A 3-dimensional array D of shortest path lenghts
Output : The shortest path between every pair of nodes
P[n, n] an n × n array initialized to 0
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
if D[k − 1, i, k] + D[k − 1, k, j] < D[k − 1, i, j] then
D[k, i, j] = D[k − 1, i, k] + D[k − 1, k, j]
P[i, j] = k ;

0 0 2 2
0 0 0 0
0 1 0 0
0 1 0 0
Computing the shortest paths : k = 3

Algorithm Floyd(D[n, n])

Input : A 3-dimensional array D of shortest path lenghts
Output : The shortest path between every pair of nodes
P[n, n] an n × n array initialized to 0
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
if D[k − 1, i, k] + D[k − 1, k, j] < D[k − 1, i, j] then
D[k, i, j] = D[k − 1, i, k] + D[k − 1, k, j]
P[i, j] = k ;

0 0 2 2
3 0 0 0
0 1 0 0
0 1 0 0
Computing the shortest paths : k = 4

Algorithm Floyd(D[n, n])

Input : A 3-dimensional array D of shortest path lenghts
Output : The shortest path between every pair of nodes
P[n, n] an n × n array initialized to 0
for (k = 1; k ≤ n; k + +)
for (i = 1; i ≤ n; i + +)
for (j = 1; j ≤ n; j + +)
if D[k − 1, i, k] + D[k − 1, k, j] < D[k − 1, i, j] then
D[k, i, j] = D[k − 1, i, k] + D[k − 1, k, j]
P[i, j] = k ;

0 0 4 2
4 0 4 0
0 1 0 0
0 1 0 0
Computing the shortest paths

▶ The matrix P is initialized to 0.

▶ When the previous algorithm stops, P[i, j] contains the number of
the last iteration k that caused a change in D[k, i, j].
 
0 0 4 2
 4 0 4 0 
P=
 0

1 0 0 
0 1 0 0
▶ If P[i, j] = 0, then the shortest path between i and j is directly
along the edge (i, j).
▶ If P[i, j] = k, the shortest path from i to j goes through k.
Computing the shortest paths

 
0 0 4 2
 4 0 4 0 
P=
 0

1 0 0 
0 1 0 0

▶ Look recursively at P[i, k] and P[k, j] to find other intermediate

vertex along the shortest path.
▶ In the table above, since, P[1, 3] = 4, the shortest path from 1 to
3 goes through 4. If we look recursively at P[1, 4] we find that the
path between 1 and 4 goes through 2. Recursively again, if we
look at P[1, 2] and P[2, 4] we find direct edge.
▶ Similarly if we look recursively to P[4, 3] we find a direct edge
(because P[4, 3] = 0). Then the shortest path from 1 to 3 is
1,2,4,3.
Exercises : All pairs shortest paths

10. Compute the all pairs of shortest paths for the following oriented
graph.  
0 5 10 3
 ∞ 0 1 4 
L=
 ∞

∞ 0 ∞ 
∞ ∞ 2 0
11. Compute the all pairs of shortest paths for the following oriented
graph.  
0 3 8 ∞ 4
 ∞ 0 ∞ 1 7 
 
 ∞
L= 4 0 ∞ ∞ 

 2 ∞ 5 0 ∞ 
∞ ∞ ∞ 6 0
 0
0 1 ∞ ∞ ∞
 
1
 ∞ 0 1 3 ∞ 
1 8
D0 = L =  ∞ ∞ 0 1 6 
 
2 1
6 1
 8 ∞ ∞ 0 3  3
4 3
∞ ∞ ∞ ∞ 0 3

Here the set of intermediate nodes is {0}

D1 [0, 0] = 0 ;
0 1 ∞ ∞ ∞
 
 ∞ 0 1 3 ∞  D1 [0, 1] = min D0 [0, 1], D0 [0, 0] + D0 [0, 1] = 1
D1 =  ∞ ∞ 0 1 6 D1 [0, 2] = min D0 [0, 2], D0 [0, 0] + D0 [0, 2] = ∞
 

 8 9 ∞ 0 3 
D1 [0, 3] = min D0 [0, 3], D0 [0, 0] + D0 [0, 3] = ∞
∞ ∞ ∞ ∞ 0 D1 [0, 4] = min D0 [0, 4], D0 [0, 0] + D0 [0, 4] = ∞
D1 [1, 0] = min D0 [1, 0], D0 [1, 0] + D0 [0, 0] = ∞; D1 [2, 0] = min D0 [2, 0], D0 [2, 0] + D0 [0, 0] = ∞ ;
D1 [1, 1] = 0
D1 [1, 2] = min D0 [1, 2], D0 [1, 0] + D0 [0, 2] =1 D1 [2, 1] = min D0 [2, 1], D0 [2, 0] + D0 [0, 1] = ∞
D1 [1, 3] = min D0 [1, 3], D0 [1, 0] + D0 [0, 3] =3 D1 [2, 2] = 0
D1 [1, 4] = min D0 [1, 4], D0 [1, 0] + D0 [0, 4] =∞ D1 [2, 3] = min D0 [2, 3], D0 [2, 0] + D0 [0, 3] = 1
D1 [2, 4] = min D0 [4, 4], D0 [2, 0] + D0 [0, 4] = 6
D1 [3, 0] = min D0 [3, 0], D0 [3, 0] + D0 [0, 0] = 8;
D1 [3, 1] = min D0 [3, 1], D0 [3, 0] + D0 [0, 1] = 9;
D1 [3, 2] = min D0 [3, 2], D0 [3, 0] + D0 [0, 2] =∞ D1 [4, 0] = min D0 [4, 0], D0 [4, 0] + D0 [0, 0] = ∞ ;
D1 [3, 3] = 0
D1 [3, 4] = min D0 [3, 4], D0 [3, 0] + D0 [0, 4] =3 D1 [4, 1] = min D0 [4, 1], D0 [4, 0] + D0 [0, 1] = ∞
D1 [4, 2] = min D0 [4, 3], D0 [4, 0] + D0 [0, 2] = ∞
D1 [4, 3] = min D0 [4, 3], D0 [4, 0] + D0 [0, 3] = ∞
D1 [4, 4] = 0
 0
0 1 ∞ ∞ ∞
 
1
 ∞ 0 1 3 ∞ 
1 8
D1 =  ∞ ∞ 0 1 6 
 
2 1
6 1
 8 9 ∞ 0 3  3
4 3
∞ ∞ ∞ ∞ 0 3

Here the set of intermediate nodes is {0, 1}

D1 [0, 0] = 0 ;
0 1 2 4 ∞
 
 ∞ 0 1 3 ∞  D1 [0, 1] = min D1 [0, 1], D1 [0, 1] + D1 [1, 1] = 1
D2 =  ∞ ∞ 0 1 6 D1 [0, 2] = min D1 [0, 2], D1 [0, 1] + D1 [1, 2] = 2
 

 8 9 10 0 3 
D1 [0, 3] = min D1 [0, 3], D1 [0, 1] + D1 [1, 3] = 4
∞ ∞ ∞ ∞ 0 D1 [0, 4] = min D1 [0, 4], D1 [0, 1] + D1 [1, 4] = ∞
D1 [1, 0] = min D1 [1, 0], D1 [1, 1] + D1 [1, 0] = ∞; D1 [2, 0] = min D1 [2, 0], D1 [2, 1] + D1 [1, 0] = ∞ ;
D1 [1, 1] = 0
D1 [1, 2] = min D1 [1, 2], D1 [1, 1] + D1 [1, 2] =1 D1 [2, 1] = min D1 [2, 1], D1 [2, 1] + D1 [1, 1] = ∞
D1 [1, 3] = min D1 [1, 3], D1 [1, 1] + D1 [1, 3] =3 D1 [2, 2] = 0
D1 [1, 4] = min D1 [1, 4], D1 [1, 1] + D1 [1, 4] =∞ D1 [2, 3] = min D1 [2, 3], D1 [2, 1] + D1 [1, 3] = 1
D1 [2, 4] = min D1 [2, 4], D1 [2, 1] + D1 [1, 4] = 6
D1 [3, 0] = min D1 [3, 0], D1 [3, 1] + D1 [1, 0] = 8;
D1 [3, 1] = min D1 [3, 1], D1 [3, 1] + D1 [1, 1] = 9;
D1 [3, 2] = min D1 [3, 2], D1 [3, 1] + D1 [1, 2] = 10 D1 [4, 0] = min D1 [4, 0], D1 [4, 1] + D1 [1, 0] = ∞ ;
D1 [3, 3] = 0
D1 [3, 4] = min D1 [3, 4], D1 [3, 1] + D1 [1, 4] =3 D1 [4, 1] = min D1 [4, 1], D1 [4, 1] + D1 [1, 1] = ∞
D1 [4, 2] = min D1 [4, 3], D1 [4, 1] + D1 [1, 2] = ∞
D1 [4, 3] = min D1 [4, 3], D1 [4, 1] + D1 [1, 3] = ∞
D1 [4, 4] = 0
 0
0 1 2 4 ∞
 
1
 ∞ 0 1 3 ∞ 
1 8
D2 =  ∞ ∞ 0 1 6 
 
2 1
 8 6 1
9 10 0 3  3
4 3
∞ ∞ ∞ ∞ 0 3

Here the set of intermediate nodes is {0, 1, 2}

D1 [0, 0] = 0 ;
0 1 2 3 8
 
 ∞ 0 1 2 7  D1 [0, 1] = min D2 [0, 1], D2 [0, 2] + D2 [2, 1] = 1
D3 =  ∞ ∞ 0 1 6 D1 [0, 2] = min D2 [0, 2], D2 [0, 2] + D2 [2, 2] = 2
 

 8 9 10 0 3 
D1 [0, 3] = min D2 [0, 3], D2 [0, 2] + D2 [2, 3] = 3
∞ ∞ ∞ ∞ 0 D1 [0, 4] = min D2 [0, 4], D2 [0, 2] + D2 [2, 4] = 8
D1 [1, 0] = min D2 [1, 0], D2 [1, 2] + D2 [2, 0] = ∞; D1 [2, 0] = min D2 [2, 0], D2 [2, 2] + D2 [2, 0] = ∞ ;
D1 [1, 1] = 0
D1 [1, 2] = min D2 [1, 2], D2 [1, 2] + D2 [2, 2] =1 D1 [2, 1] = min D2 [2, 1], D2 [2, 2] + D2 [2, 1] = ∞
D1 [1, 3] = min D2 [1, 3], D2 [1, 2] + D2 [2, 3] =2 D1 [2, 2] = 0
D1 [1, 4] = min D2 [1, 4], D2 [1, 2] + D2 [2, 4] =7 D1 [2, 3] = min D2 [2, 3], D2 [2, 2] + D2 [2, 3] = 1
D1 [2, 4] = min D2 [4, 4], D2 [2, 2] + D2 [2, 4] = 6
D1 [3, 0] = min D2 [3, 0], D2 [3, 2] + D2 [2, 0] = 8;
D1 [3, 1] = min D2 [3, 1], D2 [3, 2] + D2 [2, 1] = 9;
D1 [3, 2] = min D2 [3, 2], D2 [3, 2] + D2 [2, 2] = 10 D1 [4, 0] = min D2 [4, 0], D2 [4, 2] + D2 [2, 0] = ∞ ;
D1 [3, 3] = 0
D1 [3, 4] = min D2 [3, 4], D2 [3, 2] + D2 [2, 4] =3 D1 [4, 1] = min D2 [4, 1], D2 [4, 2] + D2 [2, 1] = ∞
D1 [4, 2] = min D2 [4, 3], D2 [4, 2] + D2 [2, 2] = ∞
D1 [4, 3] = min D2 [4, 3], D2 [4, 2] + D2 [2, 3] = ∞
D1 [4, 4] = 0
 0
0 1 2 3 8
 
1
 ∞ 0 1 2 7 
1 8
D3 =  ∞ ∞ 0 1 6 
 
2 1
 8 6 1
9 10 0 3  3
4 3
∞ ∞ ∞ ∞ 0 3

Here the set of intermediate nodes is {0, 1, 2, 3}

D1 [0, 0] = 0 ;
0 1 2 3 6
 
 10 0 1 2 5  D1 [0, 1] = min D3 [0, 1], D3 [0, 3] + D3 [3, 1] = 1
D4 =  9 10 0 1 4 D1 [0, 2] = min D3 [0, 2], D3 [0, 3] + D3 [3, 2] = 2
 

 8 9 10 0 3 
D1 [0, 3] = min D3 [0, 3], D3 [0, 3] + D3 [3, 3] = 3
∞ ∞ ∞ ∞ 0 D1 [0, 4] = min D3 [0, 4], D3 [0, 3] + D3 [3, 4] = 6
D1 [1, 0] = min D3 [1, 0], D3 [1, 3] + D3 [3, 0] = 10 ; D1 [2, 0] = min D3 [2, 0], D3 [2, 3] + D3 [3, 0] = 9 ;
D1 [1, 1] = 0
D1 [1, 2] = min D3 [1, 2], D3 [1, 3] + D3 [3, 2] =1 D1 [2, 1] = min D3 [2, 1], D3 [2, 3] + D3 [3, 1] = 10
D1 [1, 3] = min D3 [1, 3], D3 [1, 3] + D3 [3, 3] =2 D1 [2, 2] = 0
D1 [1, 4] = min D3 [1, 4], D3 [1, 3] + D3 [3, 4] =5 D1 [2, 3] = min D3 [2, 3], D3 [2, 3] + D3 [3, 3] = 1
D1 [2, 4] = min D3 [4, 4], D3 [2, 3] + D3 [3, 4] = 4
D1 [3, 0] = min D3 [3, 0], D3 [3, 3] + D3 [3, 0] = 8;
D1 [3, 1] = min D3 [3, 1], D3 [3, 3] + D3 [3, 1] = 9;
D1 [3, 2] = min D3 [3, 2], D3 [3, 3] + D3 [3, 2] = 10 D1 [4, 0] = min D3 [4, 0], D3 [4, 3] + D3 [3, 0] = ∞ ;
D1 [3, 3] = 0
D1 [3, 4] = min D3 [3, 4], D3 [3, 3] + D3 [3, 4] =3 D1 [4, 1] = min D3 [4, 1], D3 [4, 3] + D3 [3, 1] = ∞
D1 [4, 2] = min D3 [4, 3], D3 [4, 3] + D3 [3, 2] = ∞
D1 [4, 3] = min D3 [4, 3], D3 [4, 3] + D3 [3, 3] = ∞
D1 [4, 4] = 0
Computing the P matrix

 
−1 −1 1 2 3
 3
 −1 −1 2 3 

 3
P= 3 0−1 −1 3 

 −1 0 1 −1 −1 
−1 −1 −1 −1 −1
-1 means the shortest path between nodes x and y is the directed edge
in the graph. Shortest path between :
▶ (0, 2) = (0, 1)(1, 2) = (0, 1, 2)
▶ (0, 3) = (0, 2)(2, 3) where (0, 2) = (0, 1)(1, 2) = (0, 1, 2, 3)
▶ (0, 4) = (0, 3)(3, 4) = (0, 1, 2, 3, 4)
▶ (1, 0) = (1, 3)(3, 0) where (1, 3) = (1, 2)(2, 3) = (1, 2, 3) = (1, 2, 3, 0)
▶ (1, 3) = (1, 2)(2, 3) = (1, 2, 3)
▶ (1, 4) = (1, 3)(3, 4) = (1, 2, 3, 4)
▶ (2, 0) = (2, 3)(3, 0) = (2, 3, 0)
▶ (2, 1) = (2, 3)(3, 1) = (2, 3, 1)
▶ (2, 4) = (2, 3)(3, 4) = (2, 3, 4)
▶ (3, 1) = (3, 0)(0, 1) = (3, 0, 1)
▶ (3, 2) = (3, 1)(1, 2) where (3, 1) = (3, 0)(0, 1) = (3, 0, 1) = (3, 0, 1, 2)
Computing the binomial coefficient

Binomial coefficients are coefficients of the binomial

formula :
(a + b)n = n0 an b0 + · · · + kn an−k bk + . . . + nn a0 bn

The value of the 

binomial coefficient can be computed as
  
 1 if k = 0 or k = n
    
n n−1 n−1
= + if 0 < k < n
k 
 k −1 k
0 otherwise

Recursive solution
Suppose 0 ≤ k ≤ n. We can calculate the binomial coefficient using a
recursive algorithm :

function C (n, k)
if (k == 0 or k == n) then return 1
else return C (n − 1, k − 1) + C (n − 1, k)

4
2

3 3
1 2

2 2 2 2
0 1 1 2

1 1 1 1
0 1 0 1
Complexity of recursive binomial

The recurrence relation of the recursive algorithm for the binomial

coefficient is the following :

1 k = 0 or k = n
T (n) =
T (n − 1, k − 1) + T (n − 1, k) + 1 otherwise
n


The solution to this recurrence relation is k . In fact, T (n) is at least
in kn , i.e. T (n) ∈ Ω( kn ).



DP algorithm for binomial coefficient

There exist a dynamic programming algorithm for the binomial

coefficient that runs in Θ(nk).

function C dyn(n, k)
int *f, i, j ;
f = malloc((n × k) ∗ sizeof(int)) ;
for (i = 0; i ≤ n; i + +)
for (j = 0; j ≤ min(i, k); j + +)
if ((j == 0)||(j == i) then
f [i, j] = 1 ;
else
if (j ≤ k) then f [i, j] = f [i − 1, j − 1] + f [i − 1, j] ;
return f [n, k] ;
DP algorithm for binomial coefficient

0 1 2
0
function C dyn(n, k) 1
int *f, i, j ; 2
f = malloc((n × k) ∗ sizeof(int)) ; 3
for (i = 0; i ≤ n; i + +) 4
for (j = 0; j ≤ min(i, k); j + +)
if ((j == 0)||(j == i) then
f [i, j] = 1 ;
else
if (j ≤ k) then f [i, j] =
f [i − 1, j − 1] + f [i − 1, j] ;
return f [n, k] ;
Cost of dynamic programs

Calculate how many table or list entries you fill in (sometimes you
don’t use the entire table, just all entries under the diagonal or
something like that).

Calculate how much work it takes to compute each entry.

Multiply the two numbers.

Then add the cost of retrieving the answer from the table.
Example : problem fails the optimal substructure test

Unweighted longest simple path : Find a “simple” path from u to v

consisting of the most edges.
We may assume that the problem of finding an unweighted longest
simple path exhibits optimal substructure, i.e. if we decompose the
longest simple path from u to v into subpaths p1 = u → w and
p2 = w → v then p1 and p2 must also be the longest subpaths between
u − w and w − v . The figure below shows that this is not the case :

Consider the path q → r → t, the longest simple path from q to t.

q → r is not the longest, rather q → s → t → r is.
Dynamic Programming : Conclusion

As we have seen, dynamic programming is a technique that can be used

to find optimal solutions to certain problems, often in polynomial time.

Dynamic programming works when a problem has the following

characteristics :
▶ Optimal Substructure : If an optimal solution contains optimal
subsolutions, then a problem exhibits optimal substructure.
▶ Overlapping subproblems : When a recursive algorithm would
visit the same subproblems repeatedly, then a problem has
overlapping subproblems.

Dynamic programming takes advantage of these facts to solve

problems more efficiently.

It works well only for problems that exhibit both properties.

Exercise : Longest common string
The longest common string problem consists to find the longest sequence of consecutive
symbols that belong to two or more strings. For example, the longest common subtring of
string ”ABABC”’ and ”BABCA” is ”ABC”.
1. Write a divide-&-conquer algorithm to solve this problem

int lcsub(char *X, char *Y, int i, int j )

if (i == 0||j == 0) return 0 ;
if (X [i] == Y [j])
return 1 + lcsub(X , Y , i − 1, j − 1) ;
else
lcsub(X , Y , i − 1, j) ;
lcsub(X , Y , i, j − 1) ;
return 0 ;

2. Base on your recursive algorithm, generate a table to store the results of a dynamic
programming algorithm and fill the table for the strings ABAZDC and BACBAD
1 2 3 4 5 6
A B A Z D C
0 0 0 0 0 0 0
1 B 0 0 1 0 0 0 0
2 A 0 1 0 2 0 0 0
3 C 0 0 0 0 0 0 1
4 B 0 0 1 0 0 0 0
5 A 0 1 0 2 0 0 0
6 D 0 0 0 0 0 1 0