Lecture 6 1

CMPE371
Analysis of Algorithms
FALL 2020-2021
Lecture 6
Analysis of Algorithms
Part II: Algorithm Design Techniques
• Programming paradigms
• Brute force approach
• Divide and conquer
• Dynamic programming:
• matrix chain multiplication problem
• longest common subsequence problem
• rod cuting problem
• Greedy algorithms:
• activity selection problem
• fractional knapsack problem
Dynamic Programming
Dynamic Programming is a general algorithm design technique
for solving problems defined by or formulated as recurrences with overlapping
subinstances
• Invented by American mathematician Richard Bellman in the 1950s to solve

optimization problems and later assimilated by CS
• “Programming” here means “planning”
• Main idea:
- set up a recurrence relating a solution to a larger instance to solutions of some
smaller instances
- solve smaller instances once
- record solutions in a table
- extract solution to the initial instance from that table
Example: Fibonacci numbers
• Recall definition of Fibonacci numbers:
F(n) = F(n-1) + F(n-2)

F(0) = 0
F(1) = 1
• Computing the nth Fibonacci number recursively (top-down):
F(n)
F(n-1) + F(n-2)
F(n-2) + F(n-3) F(n-3) + F(n-4)
...
Example: Fibonacci numbers (cont.)
Computing the nth Fibonacci number using bottom-up iteration and
recording results:
F(0) = 0
F(1) = 1
F(2) = 1+0 = 1
…
F(n-2) =
F(n-1) =
F(n) = F(n-1) + F(n-2)
0 1 1 . . . F(n-2) F(n-1) F(n)

Efficiency:
- time n What if we solve it
- space n recursively?
Matrix-chain Multiplication
• Suppose we have a sequence or chain A1, A2, …, An of n matrices to
be multiplied
• That is, we want to compute the product A1A2…An
• There are many possible ways (parenthesizations) to compute the

product
Matrix-chain Multiplication …contd
• Example: consider the chain A1, A2, A3, A4 of 4

matrices
• Let us compute the product A1A2A3A4
• There are 5 possible ways:
1. (A1(A2(A3A4)))
2. (A1((A2A3)A4))
3. ((A1A2)(A3A4))
4. ((A1(A2A3))A4)
5. (((A1A2)A3)A4)
• To compute the number of scalar multiplications

necessary, we must know:
• Algorithm to multiply two matrices
• Matrix dimensions
• Can you write the algorithm to multiply two

matrices?
Algorithm to Multiply 2 Matrices
Input: Matrices Ap×q and Bq×r (with dimensions p×q and q×r)
Result: Matrix Cp×r resulting from the product A·B
MATRIX-MULTIPLY(Ap×q , Bq×r)
1. for i ← 1 to p
2. for j ← 1 to r
3. C[i, j] ← 0
4. for k ← 1 to q
5. C[i, j] ← C[i, j] + A[i, k] · B[k, j]
6. return C
Scalar multiplication in line 5 dominates time to compute

CNumber of scalar multiplications = pqr
• Example: Consider three matrices A10100, B1005, and

C550
• There are 2 ways to parenthesize
• ((AB)C) = D105 · C550
• AB  10·100·5=5,000 scalar multiplications Total:
• DC  10·5·50 =2,500 scalar multiplications 7,500
• (A(BC)) = A10100 · E10050
• BC  100·5·50=25,000 scalar multiplications
• AE  10·100·50 =50,000 scalar multiplications
Total:
75,000
• Matrix-chain multiplication problem

• Given a chain A1, A2, …, An of n matrices, where for i=1,
2, …, n, matrix Ai has dimension pi-1pi
• Parenthesize the product A1A2…An such that the total
number of scalar multiplications is minimized
• Brute force method of exhaustive search takes
time exponential in n
Dynamic Programming Approach
• The structure of an optimal solution
• Let us use the notation Ai..j for the matrix that results
from the product Ai Ai+1 … Aj
• An optimal parenthesization of the product A1A2…An
splits the product between Ak and Ak+1 for some integer
k where1 ≤ k < n
• First compute matrices A1..k and Ak+1..n ; then multiply
them to get the final matrix A1..n
Dynamic Programming Approach …contd
• Key observation: parenthesizations of the subchains

A1A2…Ak and Ak+1Ak+2…An must also be optimal if the
parenthesization of the chain A1A2…An is optimal (why?)
• That is, the optimal solution to the problem contains

within it the optimal solution to subproblems
• Recursive definition of the value of an optimal solution
• Let m[i, j] be the minimum number of scalar multiplications
• necessary to compute Ai..j
• Minimum cost to compute A1..n is m[1, n]
• Suppose the optimal parenthesization of Ai..j splits the product

between Ak and Ak+1 for some integer k where i ≤ k < j
• Ai..j = (Ai Ai+1…Ak)·(Ak+1Ak+2…Aj)= Ai..k · Ak+1..j
• Cost of computing Ai..j = cost of computing Ai..k + cost of
computing Ak+1..j + cost of multiplying Ai..k and Ak+1..j
• Cost of multiplying Ai..k and Ak+1..j is pi-1pk pj
• m[i, j ] = m[i, k] + m[k+1, j ] + pi-1pk pj for i ≤ k < j

• m[i, i ] = 0 for i=1,2,…,n
• But… optimal parenthesization occurs at one value of k
among all possible i ≤ k < j
• Check all these and select the best one
0 if i=j
m[i, j ] =
min {m[i, k] + m[k+1, j ] + pi-1pk pj } if i<j
i ≤ k< j
• To keep track of how to construct an optimal
solution, we use a table s
• s[i, j ] = value of k at which Ai Ai+1 … Aj is split for
optimal parenthesization
• Algorithm: next slide
• First computes costs for chains of length l=1
• Then for chains of length l=2,3, … and so on
• Computes the optimal cost bottom-up
Algorithm to Compute Optimal Cost
Input: Array p[0…n] containing matrix dimensions and n
Result: Minimum-cost table m and split table s
MATRIX-CHAIN-ORDER(p[ ], n)
for i ← 1 to n Takes O(n3) time
m[i, i] ← 0
Requires O(n2) space
for l ← 2 to n
for i ← 1 to n-l+1
j ← i+l-1
m[i, j] ← 
for k ← i to j-1
q ← m[i, k] + m[k+1, j] + p[i-1] p[k] p[j]
if q < m[i, j]
m[i, j] ← q
s[i, j] ← k
return m and s
Constructing Optimal Solution
• Our algorithm computes the minimum-cost table
m and the split table s
• The optimal solution can be constructed from the
split table s
• Each entry s[i, j ]=k shows where to split the product Ai
Ai+1 … Aj for the minimum cost
Example
 The algorithm takes O(n3) time and requires

O(n2) space.
 Example:
 Consider the following six matrix problem.
Matrix A1 A2 A3 A4 A5 A6
Dimensions 10x20 20x5 5x15 15x50 50x10 10x15
 The problem therefore can be phrased as one
of filling in the following table representing the
values m.
i\j 1 2 3 4 5 6
1 0
2 0
3
0
4
5 0
6 0
0
21
Example (Contd.)
 Chains of length 2 are easy, as there is no

minimization required, so
 m[i, i+1] = pi-1pipi+1
 m[1, 2] = 10x20x5 = 1000

 m[2, 3] = 20x5x15 = 1500
 m[3, 4] = 5x15x50 = 3750
 m[4, 5] = 15x50x10 = 7500
 m[5, 6] = 50x10x15 = 7500
i\j 1 2 3 4 5 6
1 0 1000
2 0 1500
3
0 3750
4
5 0 7500
6 0 7500
0
22
Example (Contd.)
 Chains of length 3 require some minimization –
but only one each.
 m[1,3]=min{(m[1,1]+m[2,3]+p 0p1p3),(m[1,2]+m[3,3]+p0p2p3)}
= min{(0+1500+10x20x15),
(1000+0+10x5x15)}
= min { 4500,1p1750
 m[2,4]=min{(m[2,2]+m[3,4]+p } = 1750
2p4),(m[2,3]+m[4,4]+p 1p3p4)}
= min{(0+3750+20x5x50),
(1500+0+20x15x50)}
= min { 8750,2p16500
 m[3,5]=min{(m[3,3]+m[4,5]+p } = 8750
3p5),(m[3,4]+m[5,5]+p 2p4p5)}
= min{(0+7500+5x15x10),
(3750+0+5x50x10)}
= min { 8250,3p6250
 m[4,6]=min{(m[4,4]+m[5,6]+p } = 6250
4p6),(m[4,5]+m[6,6]+p 3p5p6)}
= min{(0+7500+15x50x15),
(7500+0+15x10x15)}
= min { 18750, 9750 } = 9750
i\j 1 2 3 4 5 6
1 0 1000 1750
2 0 1500 8750
3
0 3750 6250
4
5 0 7500 9750
6 0 7500
0
23
Example (Contd.)
 m[1,4]=min{(m[1,1]+m[2,4]+p 0p1p4),(m[1,2]+m[3,4]+p0p2p4),
(m[1,3]+m[4,4]+p0p3p4)}
= min{(0+8750+10x20x50),
(1000+3750+10x5x50),
(1750+0+10x15x50)}
 m[2,5]=min{(m[2,2]+m[3,5]+p 1p27250,
= min { 18750, p5),(m[2,3]+m[4,5]+p
9250 } = 72501p3p5),
(m[2,4]+m[5,5]+p1p4p5)}
= min{(0+6250+20x5x10),
(1500+7500+20x15x10),
(8750+0+20x50x10)}
 m[3,6]=min{(m[3,3]+m[4,6]+p
= min { 7250,2p12000,
3p6),(m[3,4]+m[5,6]+p
18750 } = 7250 2p4p6),
(m[3,5]+m[6,6]+p2p5p6)}
= min{(0+9750+5x15x15),
(3750+7500+5x50x15),
(6250+0+5x10x15)}
i\j 1 =2 3
min { 10875, 4
15000, 5 } = 7000
7000 6
1 0 1000 1750 7250
2 0 1500 8750 7250
3
0 3750 6250 7000
4
5 0 7500 9750
6 0 7500
0
24
Example (Contd.)
 m[1,5]=min{(m[1,1]+m[2,5]+p 0p1p5),(m[1,2]+m[3,5]+p0p2p5),
(m[1,3]+m[4,5]+p0p3p5),
(m[1,4]+m[5,5]+p0p4p5)}
= min{(0+7250+10x20x10),
(1000+6250+10x5x10),
(1750+7500+10x15x10),
 m[2,6]=min{(m[2,2]+m[3,6]+p 1p2p6),(m[2,3]+m[4,6]+p 1p3p6),
(7250+0+10x50x10)} (m[2,4]+m[5,6]+p1p4p6),
(m[2,5]+m[6,6]+p= pmin
p )}{ 9250, 7750, 10750, 12250 } = 7750
1 5 6
= min{(0+7000+20x5x15),
(1500+9750+20x15x15),
(8750+7500+20x50x15),
 m[1,6]=min{(m[1,1]+m[2,6]+p 0p1p6),(m[1,2]+m[3,6]+p 0p2p6),
(7250+0+20x10x15)}
(m[1,3]+m[4,6]+p p p ),
= min { 8500, 15750, 31,250, 102500 3 } 6=
(m[1,4]+m[5,6]+p
8500 p p
0 4 6),
(m[1,5]+m[6,6]+p0p5p6)}
i\j 1 = 2min{(11500,
3 8750,
4 13750,
5 22250,
6 9250 }
= 8750
1 0 1000 1750 7250 7750 8750
2 0 1500 8750 7250 8500
3
0 3750 6250 7000
4
5 0 7500 9750
6 0 7500
0
25
Dynamic Programming Approach (Contd.)
 The algorithm takes O(n3) time and requires O(n2)
space.
 Step 4: Constructing an optimal solution
 Our algorithm computes the minimum-cost
table m and the split table s.
 The optimal solution can be constructed from
the split table s.
 Each entry s[i, j ]=k shows where to split the
product Ai Ai+1 … Aj for the minimum cost.
 The following recursive procedure prints an
optimal parenthesization.
Algorithm PrintOptimalPerens(s, i, j)
{ if (i=j) then
Print “A”i;
else
{ Print “(“;
PrintOptimalPerens(s, i, s[i,j]);
PrintOptimalPerens(s, s[i,j]+1,
j);
Print “)”;
26 }
}
Example (Contd.)
 So far we have decided that the best way to
parenthesize the expression results in 8750
multiplication.
 But we have not addressed how we should
actually DO the multiplication to achieve the
value.
 However, look at the last computation we did –
the minimum value came from computing
A = (A1A2)
(A3A4A5A6)
 Therefore in an auxiliary array, we store value

s[1,6]=2.
 In general, as we proceed with the algorithm, if
we find that the best way to compute Ai..j is as
Ai..j = Ai..kA(k+1)..j
then we set
s[i, j] = k.
 Then from the values of k we can reconstruct

the optimal way to parenthesize the
27 expression.
Example (Contd.)
 If we do this then we find that the s array looks
like this:
i\j 1 2 3 4 5 6
1 1 1 2 2 2 2
2 2 2 2 2 2
3
4 3 3 4 5
5 4 4 5
6 5 5
6
 We already know that we must compute A1..2
and A3..6.
 By looking at s[3,6] = 5, we discover that we
should compute A3..6 as A3..5A6..6 and then by
seeing that s[3,5] = 4, we get the final
parenthesization
A = ((A1A2)
(((A3A4)A5)A6)).
 And quick check reveals that this indeed takes

28
the required 8750 multiplications.
Example
• Show how to multiply this Matrix Dimension
matrix chain optimally
A1 30×35
• Solution on the board A2 35×15

• Minimum cost 15,125 A3 15×5
• Optimal parenthesization
((A1(A2A3))((A4 A5)A6)) A4 5×10
A5 10×20
A6 20×25
Longest Common Subsequence (LCS)
Application: comparison of two DNA strings

Ex: X= {A B C B D A B }, Y= {B D C A B A}
Longest Common Subsequence:
X= AB C BDAB
Y= B D CAB A
Brute force algorithm would compare each
subsequence of X with the symbols in Y
LCS Algorithm
• if |X| = m, |Y| = n, then there are 2m subsequences of X; we
must compare each with Y (n comparisons)
• So the running time of the brute-force algorithm is O(n 2 m)
• Notice that the LCS problem has optimal substructure:

solutions of subproblems are parts of the final solution.
• Subproblems: “find LCS of pairs of prefixes of X and Y”

LCS Algorithm
• First we’ll find the length of LCS. Later we’ll modify the algorithm to find
LCS itself.
• Define Xi, Yj to be the prefixes of X and Y of length i and j respectively
• Define c[i,j] to be the length of LCS of Xi and Yj
• Then the length of LCS of X and Y will be
c[m,n]
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ]  
 max(c[i, j  1], c[i  1, j ]) otherwise
LCS recursive solution
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ]  
• We start with i = j = 0 (empty substrings of x and y)
• Since X0 and Y0 are empty strings, their LCS is

always empty (i.e. c[0,0] = 0)
• LCS of empty string and any other string is empty, so
for every i and j: c[0, j] = c[i,0] = 0
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ]  
• When we calculate c[i,j], we consider two cases:
• First case: x[i]=y[j]: one more symbol in strings X
and Y matches, so the length of LCS Xi and Yj equals
to the length of LCS of smaller strings X i-1 and Yi-1 ,
plus 1
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ]  
• Second case: x[i] != y[j]
• As symbols don’t match, our solution is not
improved, and the length of LCS(Xi , Yj) is the same
as before (i.e. maximum of
LCS(Xi, Yj-1) and LCS(Xi-1,Yj)
Why not just take the length of LCS(Xi-1, Yj-1) ?

LCS Length Algorithm
LCS-Length(X, Y)
1. m = length(X) // get the # of symbols in X
2. n = length(Y) // get the # of symbols in Y
3. for i = 1 to m c[i,0] = 0 // special case: Y0
4. for j = 1 to n c[0,j] = 0 // special case: X0
5. for i = 1 to m // for all Xi
6. for j = 1 to n // for all Yj
7. if ( Xi == Yj )
8. c[i,j] = c[i-1,j-1] + 1
9. else c[i,j] = max( c[i-1,j], c[i,j-1] )
10. return c[m,n] // return LCS length for X and Y
LCS Example
We’ll see how LCS algorithm works on the following
example:
• X = ABCB
• Y = BDCAB
What is the Longest Common Subsequence

of X and Y?
LCS(X, Y) = BCB
X=AB C B
Y= BDCAB
LCS Example (0) ABCB
j 0 1 2 3 4 5
BDCAB
i Yj B D C A B
0 Xi
1 A
2 B
3 C
4 B
X = ABCB; m = |X| = 4
Y = BDCAB; n = |Y| = 5
Allocate array c[4,5]
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0
2 B 0
3 C 0
4 B 0
for i = 1 to m c[i,0] = 0
for j = 1 to n c[0,j] = 0
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0
2 B 0
3 C 0
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0
2 B 0
3 C 0
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1
2 B 0
3 C 0
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0
3 C 0
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1
3 C 0
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1
3 C 0
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0 1
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0 1 1 2 2
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
j 0 1 2 3 4 5
BDCA
i Yj B D C A BB
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0 1 1 2 2 3
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
LCS Algorithm Running Time
• LCS algorithm calculates the values of each entry of

the array c[m,n]
• So what is the running time?
O(m*n)
since each c[i,j] is calculated in
constant time, and there are m*n
elements in the array
How to find actual LCS
• So far, we have just found the length of LCS, but
not LCS itself.
• We want to modify this algorithm to make it output
Longest Common Subsequence of X and Y
Each c[i,j] depends on c[i-1,j] and c[i,j-1]
or c[i-1, j-1]
For each c[i,j] we can say how it was acquired:
2 2 For example, here

2 3 c[i,j] = c[i-1,j-1] +1 = 2+1=3
How to find actual LCS - continued
• Remember that
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ]  
 So we can start from c[m,n] and go backwards

 Look first to see if 2nd case above was true
 If not, then c[i,j] = c[i-1, j-1]+1, so remember x[i]
(because x[i] is a part of LCS)
 When i=0 or j=0 (i.e. we reached the beginning),
output remembered letters in reverse order
Algorithm to find actual LCS
• Here’s a recursive algorithm to do this:
LCS_print(x, m, n, c) {
if (c[m][n] == c[m-1][n]) // go up?
LCS_print(x, m-1, n, c);
else if (c[m][n] == c[m][n-1] // go left?
LCS_print(x, m, n-1, c);
else { // it was a match!
LCS_print(x, m-1, n-1, c);
print(x[m]); // print after recursive call
}
}
Finding LCS
j 0 1 2 3 4 5
i Yj B D C A B
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0 1 1 2 2 3
Finding LCS (2)
j 0 1 2 3 4 5
i Yj B D C A B
0 Xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0 1 1 2 2 3
LCS (reversed order): B C B
LCS (straight order): B C B
(this string turned out to be a palindrome)
Knapsack 0-1 Problem
The goal is to maximize
the value of a knapsack
that can hold at most W
units (i.e. lbs or kg) worth
of goods from a list of
items I0, I1, … In-1.
◦ Each item has 2 attributes:

1) Value – let this be vi for
item Ii
2) Weight – let this be wi for
item Ii
 The difference between
this problem and the
fractional knapsack one
is that you CANNOT
take a fraction of an
item.
◦ You can either take it or

not.
◦ Hence the name
Knapsack 0-1 problem.
Brute Force
◦ The naïve way to solve this problem is to cycle through all 2 n
subsets of the n items and pick the subset with a legal weight
that maximizes the value of the knapsack.
◦ We can come up with a dynamic programming algorithm that

will USUALLY do better than this brute force technique.
As we did before we are going to solve the problem
in terms of sub-problems.
◦ So let’s try to do that…
Our first attempt might be to characterize a sub-

problem as follows:
◦ Let Sk be the optimal subset of elements from {I0, I1, …, Ik}.
 What we find is that the optimal subset from the elements {I0, I1,
…, Ik+1} may not correspond to the optimal subset of elements
from {I0, I1, …, Ik} in any regular pattern.
◦ Basically, the solution to the optimization problem for Sk+1

might NOT contain the optimal solution from problem S .
Let’s illustrate that point with an example:
Item Weight Value(benefit)
I0 3 10
I1 8 4
I2 9 9
I3 8 11
 The maximum weight the knapsack can hold is 20.
The best set of items from {I0, I1, I2} is {I0, I1, I2}
BUT the best set of items from {I0, I1, I2, I3} is {I0, I2, I3}.
◦ In this example, note that this optimal solution, {I 0, I2, I3}, does NOT build upon
the previous optimal solution, {I0, I1, I2}.
 (Instead it build's upon the solution, {I0, I2}, which is really the optimal subset of
Knapsack 0-1 problem
 So now we must re-work the way we build upon previous sub-problems…
◦ Let B[k, w] represent the maximum total value of a subset S k with weight w.
◦ Our goal is to find B[n, W], where n is the total number of items and W is the
maximal weight the knapsack can carry.
 So our recursive formula for subproblems:

B[k, w] = B[k - 1,w], if wk > w
= max { B[k - 1,w], B[k - 1,w - wk] + bk}, otherwise
 In English, this means that the best subset of S k that has total weight w is:
1) The best subset of Sk-1 that has total weight w, or
2) The best subset of Sk-1 that has total weight w-wk plus the item k
Knapsack 0-1 Problem –Recursive Formula
The best subset of Sk that has the total weight w, either

contains item k or not.
First case: wk > w

◦ Item k can’t be part of the solution! If it was the total weight
would be > w, which is unacceptable.
Second case: wk ≤ w
◦ Then the item k can be in the solution, and we choose the case
with greater value.
Knapsack 0-1 Algorithm
for w = 0 to W { // Initialize 1st row to 0’s
B[0,w] = 0
}
for i = 1 to n { // Initialize 1st column to 0’s
B[i,0] = 0
}
for i = 1 to n {
for w = 0 to W {
if wi <= w { //item i can be in the solution
if vi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
}
else B[i,w] = B[i-1,w] // wi > w
}
}
Let’s run our algorithm on the following data:
◦ n = 4 (# of elements)
◦ W = 5 (max weight)
◦ Elements (weight, value):
(2,3), (3,4), (4,5), (5,6)
Knapsack 0-1 Example
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0
2 0
3 0
4 0
// Initialize the base cases

for w = 0 to W
B[0,w] = 0
for i = 1 to n
B[i,0] = 0
Items:
Knapsack 0-1 Example 1: (2,3)

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=1
1 0 0 vi = 3
2 0 wi = 2
3 0 w=1
4 0 w-wi = -1
if wi <= w //item i can be in the solution

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=1
1 0 0 3 vi = 3
2 0 wi = 2
3 0 w=2
4 0 w-wi = 0

B[i,w]
B[i,w] = v=i +vB[i-1,w-
i + B[i-1,w-
wi]wi]
else
B[i,w]
B[i,w] = B[i-1,w]
= B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=1
1 0 0 3 3 vi = 3
2 0 wi = 2
3 0 w=3
4 0 w-wi = 1

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=1
1 0 0 3 3 3 vi = 3
2 0 wi = 2
3 0 w=4
4 0 w-wi = 2

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=1
1 0 0 3 3 3 3 vi = 3
2 0 wi = 2
3 0 w=5
4 0 w-wi = 3

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=2
1 0 0 3 3 3 3 vi = 4
2 0 0 wi = 3
3 0 w=1
4 0 w-wi = -2

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=2
1 0 0 3 3 3 3 vi = 4
2 0 0 3 wi = 3
3 0 w=2
4 0 w-wi = -1

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=2
1 0 0 3 3 3 3 vi = 4
2 0 0 3 4 wi = 3
3 0 w=3
4 0 w-wi = 0

B[i,w]
B[i,w] = v=i +vB[i-1,w-
i + B[i-1,w-
wi]wi]
else
B[i,w]
B[i,w] = B[i-1,w]
= B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=2
1 0 0 3 3 3 3 vi = 4
2 0 0 3 4 4 wi = 3
3 0 w=4
4 0 w-wi = 1

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=2
1 0 0 3 3 3 3 vi = 4
2 0 0 3 4 4 7 wi = 3
3 0 w=5
4 0 w-wi = 2

B[i,w] = vi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=3
1 0 0 3 3 3 3 vi = 5
2 0 0 3 4 4 7 wi = 4
3 0 0 3 4 w = 1..3
4 0 w-wi = -3..-1

B[i,w] = v=i +vB[i-1,w-
B[i,w] w]
i + B[i-1,w-i wi]
else
B[i,w] = B[i-1,w]
B[i,w] = B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=3
1 0 0 3 3 3 3 vi = 5
2 0 0 3 4 4 7 wi = 4
3 0 0 3 4 5 w=4
4 0 w-wi = 0

B[i,w]
B[i,w] = v=i +vB[i-1,w-
i + B[i-1,w-
wi]wi]
else
B[i,w]
B[i,w] = B[i-1,w]
= B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=3
1 0 0 3 3 3 3 vi = 5
2 0 0 3 4 4 7 wi = 4
3 0 0 3 4 5 7 w=5
4 0 w-wi = 1

B[i,w]
B[i,w] = v=i +vB[i-1,w-
i + B[i-1,w-
wi]wi]
else
B[i,w]
B[i,w] = B[i-1,w]
= B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=4
1 0 0 3 3 3 3 vi = 6
2 0 0 3 4 4 7 wi = 5
3 0 0 3 4 5 7 w = 1..4
4 0 0 3 4 5 w-wi = -4..-1

B[i,w]
B[i,w] = v=i +vB[i-1,w-
i + B[i-1,w-
wi]wi]
else
B[i,w]
B[i,w] = B[i-1,w]
= B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=4
1 0 0 3 3 3 3 vi = 6
2 0 0 3 4 4 7 wi = 5
3 0 0 3 4 5 7 w=5
4 0 0 3 4 5 7 w-wi = 0

B[i,w]
B[i,w] = v=i +vB[i-1,w-
i + B[i-1,w-
wi]wi]
else
B[i,w]
B[i,w] = B[i-1,w]
= B[i-1,w]
Items:

2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 3 3 3 3
2 0 0 3 4 4 7
3 0 0 3 4 5 7
4 0 0 3 4 5 7
We’re DONE!!
The max possible value that can be carried in this knapsack is $7
This algorithm only finds the max possible value that
can be carried in the knapsack
◦ The value in B[n,W]
To know the items that make this maximum value, we

need to trace back through the table.
Finding the Items
 Let i = n and k = W
if B[i, k] ≠ B[i-1, k] then
mark the ith item as in the knapsack
i = i-1, k = k-wi
else
i = i-1 // Assume the ith item is not in the knapsack
// Could it be in the optimally packed
knapsack?
Items: Knapsack:
Knapsack 0-1 Algorithm 1: (2,3)
Finding the Items 2: (3,4)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=4
1 0 0 3 3 3 3 k=5
2 0 0 3 4 4 7 vi = 6
3 0 0 3 4 5 7 wi = 5
4 0 0 3 4 5 7 B[i,k] = 7
B[i-1,k] = 7
i=n,k=W
while i, k > 0
i = i-1, k = k-wi
else
i = i-1
Items: Knapsack:
Knapsack 0-1 Algorithm 1: (2,3)
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=3
1 0 0 3 3 3 3 k=5
2 0 0 3 4 4 7 vi = 5
3 0 0 3 4 5 7 wi = 4
4 0 0 3 4 5 7 B[i,k] = 7
B[i-1,k] = 7
i=n,k=W
while i, k > 0
i = i-1, k = k-wi
else
i = i-1
Items: Knapsack:
Knapsack 0-1 Algorithm 1: (2,3) Item 2
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=2
1 0 0 3 3 3 3 k=5
2 0 0 3 4 4 7 vi = 4
3 0 0 3 4 5 7 wi = 3
4 0 0 3 4 5 7 B[i,k] = 7
B[i-1,k] =
3
i=n,k=W k – wi = 2
while i, k > 0
i = i-1, k = k-wi
else
i = i-1
Items: Knapsack:
Finding the Items 2: (3,4) Item 1
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=1
1 0 0 3 3 3 3 k=2
2 0 0 3 4 4 7 vi = 3
3 0 0 3 4 5 7 wi = 2
4 0 0 3 4 5 7 B[i,k] = 3
B[i-1,k] =
0
i=n,k=W k – wi = 0
while i, k > 0
i = i-1, k = k-wi
else
i = i-1
Items: Knapsack:
Finding the Items 2: (3,4) Item 1
3: (4,5)
4: (5,6)
i/w 0 1 2 3 4 5
0 0 0 0 0 0 0 i=1
1 0 0 3 3 3 3 k=2
2 0 0 3 4 4 7 vi = 3
3 0 0 3 4 5 7 wi = 2
4 0 0 3 4 5 7 B[i,k] = 3
B[i-1,k] =
0
k = 0, so we’re DONE! k – wi = 0
The optimal knapsack should contain:

Item 1 and Item 2
Knapsack 0-1 Problem – Run Time
for w = 0 to W O(W)
B[0,w] = 0
for i = 1 to n O(n)
B[i,0] = 0
Repeat n times
for i = 1 to n
O(W)
for w = 0 to W
< the rest of the code >
What is the running time of this algorithm?

O(n*W)
Remember that the brute-force algorithm takes: O(2n)

Knapsack Problem
1) Fill out the dynamic
programming table
for the knapsack
problem to the
right.
2) Trace back through
the table to find the
items in the
knapsack.
Rod cutting Problem
Suppose you have a rod of length n, and you want to cut up the rod and sell the pieces in
a way that maximizes the total amount of money you get. A piece of length i is worth pi
dollars.
For example, if you have a rod of length 4, there are eight different ways to cut it, and the
best strategy is cutting it into two pieces of length 2, which gives you 10 dollars.
Exercise: How many ways are there to cut up a rod of length n?
Answer: 2 ^n−1 , because there are n − 1 places where we can choose to make cuts, and at
each place, we either make a cut or we do not make a cut.
Despite the exponentially large possibility space, we can use dynamic programming to write
an algorithm that runs in Θ(n^2).
Ahmet Unveren

Lecture 6 1

Uploaded by

Copyright:

Available Formats

Lecture 6 1

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 6 1

Uploaded by

Copyright:

Available Formats

CMPE371

• Brute force approach

• Divide and conquer

• Invented by American mathematician Richard Bellman in the 1950s to solve

• “Programming” here means “planning”

F(n) = F(n-1) + F(n-2)

• Computing the nth Fibonacci number recursively (top-down):

F(n-2) + F(n-3) F(n-3) + F(n-4)

0 1 1 . . . F(n-2) F(n-1) F(n)

• There are many possible ways (parenthesizations) to compute the

• Example: consider the chain A1, A2, A3, A4 of 4

• To compute the number of scalar multiplications

• Can you write the algorithm to multiply two

Scalar multiplication in line 5 dominates time to compute

• Example: Consider three matrices A10100, B1005, and

• Matrix-chain multiplication problem

• Key observation: parenthesizations of the subchains

• That is, the optimal solution to the problem contains

• Minimum cost to compute A1..n is m[1, n]

• Suppose the optimal parenthesization of Ai..j splits the product

• m[i, j ] = m[i, k] + m[k+1, j ] + pi-1pk pj for i ≤ k < j

 The algorithm takes O(n3) time and requires

 Chains of length 2 are easy, as there is no

 m[1, 2] = 10x20x5 = 1000

 Therefore in an auxiliary array, we store value

 Then from the values of k we can reconstruct

 And quick check reveals that this indeed takes

• Solution on the board A2 35×15

Application: comparison of two DNA strings

• So the running time of the brute-force algorithm is O(n 2 m)

• Notice that the LCS problem has optimal substructure:

• Subproblems: “find LCS of pairs of prefixes of X and Y”

• Since X0 and Y0 are empty strings, their LCS is

Why not just take the length of LCS(Xi-1, Yj-1) ?

What is the Longest Common Subsequence

• LCS algorithm calculates the values of each entry of

2 2 For example, here

 So we can start from c[m,n] and go backwards

◦ Each item has 2 attributes:

◦ You can either take it or

◦ We can come up with a dynamic programming algorithm that

Our first attempt might be to characterize a sub-

◦ Basically, the solution to the optimization problem for Sk+1

 The maximum weight the knapsack can hold is 20.

 So our recursive formula for subproblems:

The best subset of Sk that has the total weight w, either

First case: wk > w

// Initialize the base cases

Knapsack 0-1 Example 1: (2,3)

if wi <= w //item i can be in the solution

Knapsack 0-1 Example 1: (2,3)

if wi <= w //item i can be in the solution

Knapsack 0-1 Example 1: (2,3)

if wi <= w //item i can be in the solution

Knapsack 0-1 Example 1: (2,3)

if wi <= w //item i can be in the solution

Knapsack 0-1 Example 1: (2,3)

if wi <= w //item i can be in the solution