Dynamic Programming
Chain Matrix Multiplication
2021-02-03 CSC373 Winter 2021 – Sam Toueg 1
Multiplication of 2 matrices
• Multiplying a !×# matrix $ by a #×% matrix & yields a !×% matrix ‘ &
“##
!% × =% #$%
(!” = * +!# , -#”
#%!#%# ⋯ #%$
&
%%”
(
)
!!”
!#” ⋮
!$”
”
!
! multiplications for each “!” 1≤%≤&
1≤’≤(
• To compute ‘ we need ! · % · # multiplications
‘
‘
2021-02-03 CSC373 Winter 2021 – Sam Toueg
2
Multiplication of 3 matrices
•/=$·&·’
• $·&·’=($·&)·’= $· &·’
• Does the cost of multiplication depend on the multiplication order? Yes!
• Example:
852
2 4×8×5=4
A
0
/
1
Dimension: 4 x 5
Dimension: 8 x 2
ØCostof($·&)·’is: 4,8,5+4,5,2=200 ØCostof$·(&·’)is: 8,5,2+4,8,2=144
• Problem:findthebestordertomultiplyachainofmatrices! 2021-02-03 CSC373 Winter 2021 – Sam Toueg
3
Chain Matrix Product
Ø Input: The dimension 9!’%×9! of every matrix $! in $%, $(, … , $)
Ø Output: Minimum number of multiplications to compute $% · $( · … · $)
• IdeaI—Naïverecursion
• < =, > = Minimum number of multiplications to compute $! · $!*% · … · $”
• Try all the ways to put the outer-level parentheses, and take the best one: ($!·…·$#)·($#*%·…·$”)forall?∈ =,…,>−1
=C==> =C=<>
• Problem
1%)! x 1′ 1′ x 1″ <=,> =B0,
min!+#,” <=,? + +9!’%·9#·9″ ,
• Recursive procedure 2 %, ‘ :
Ø if&=(thenreturn0
Ø elsereturnmin%&'(” , &,. +, .+1,( +1%)! ·1’ ·1″
• Time complexity to compute 2 1, 5 :
2021-02-03 CSC373 Winter 2021 – Sam Toueg
4
6(5)=∑$%#(6 ; +6 5−; +>) !”#
Chain Matrix Product
H(I)=∑)’%(H ? +H I−? +() #$%
•HI =2,∑)’%H?+(I−1),( (1) #$%
• H I + 1 = 2 , ∑) H ? + I , ( (2) #$%
Do “(2) minus (1)′′ ⇒
HI+1 −HI =2,HI +(
⇒HI+1=3,HI+(
=3, 3,H I−1 +( +(
=3(,H I−1 ,+3,(+(
=3)’%,H2 ,+3)'(,(+…+3,(+(
= ( -*’% -‘%
= Θ(3))!
Too many subproblems are computed multiple times!
c
2021-02-03 CSC373 Winter 2021 – Sam Toueg 5
Chain Matrix Product
• Idea II — Dynamic Programming problem size: ‘ − %
• <(=, >) = minimum number of multiplications to compute $! · $!*% · ⋯ · $” <=,> =B0, =C==> min!+#,” <=,? + +9!’%·9#·9″ , =C=<>
• Avoid recomputing the same < =, > subproblems. How?
• By computing them bottom-up: from small > − = size to large size.
For= ←1toIdo<(=,=)←0 @(5)iterations
For Z←1toI−1 {*loopbyincreasingproblemsizeZ=>−=*}
For = ← 1 to I − Z
> ← = + Z @ 5′ inner loop iterations
<=,> ←min!+#,”{<=,? + +9!’%·9#·9″}
Return < 1,I
Time Complexity: @(5&)
2021-02-03 CSC373 Winter 2021 - Sam Toueg 6
eachmintakes @ 5 J%2K
Much better than Θ(3$)!
Dynamic Programming 0-1 Knapsack
2021-02-03 CSC373 Winter 2021 - Sam Toueg 1
Overview and Motivation
Knapsack Problem
• Given:!items,item"hasvalue#! >0andweight&! >0,
weight capacity (
• Assume: (, #!, and &! are integers
• Goal: find a subset ) of items with maximum total value and total weight at most (
• 0-1 Knapsack: We can either take a complete item or not take it 2021-02-03 CSC373 Winter 2021 – Sam Toueg 2
0-1 Knapsack — A Greedy Solution Attempt
• Greedy algorithm:
Ø Sort the items by decreasing value/weight ratio
Ø Take them in that order…
2021-02-03 CSC373 Winter 2021 – Sam Toueg 3
t
0-1 Knapsack
• Greedy algorithm does not work!
• Example: Knapsack with capacity 0 = 4 and items
Items
Weight
Value
Value/ Weight
1
3
10
3+1/3
2
2
6
3
3
2
6
3
• Greedy algorithm: selects item 1 with value 10
• Optimal choice: selects items 2 and 3 with total value 12
2021-02-03 CSC373 Winter 2021 – Sam Toueg 5
Algorithm for 0-1 Knapsack
Let ) be an optimal knapsack for items 1, 2, … , ! and capacity (
There are two possible cases for the last item !:
• !∉).Then)isanoptimalknapsackfor1,2,…,!−1and( (1)
• !∈).Then)=)”∪{!}and)”isanoptimalknapsack
for 1, … , ! − 1 and (′ = ( − &# (2)
Subproblems to solve:
• T(“, U) = value of optimal knapsack for 1, 2, … , ” and capacity U
Bellman Equation: (1)
(2)
max ! #−1,% ,! #−1,%−.! +0! , !(#,%)=( ! #−1,% ,
0,
#1#>0456%≥.! #1#>0456%<.!
#1 # = 0 9: % = 0
2021-02-03
CSC373 Winter 2021 - Sam Toueg
6
!(#,%)=(
max ! #−1,% ,! #−1,%−.! +0! , ! #−1,% ,
#1#>0456%≥.!
#1#> 0456%<.!
#1 # = 0 9: % = 0
0
(0, *) (1, *)
0
(0, 0) (1, 0)
0,
0
(0, 1) (1, 1)
!(0, () = 0
............... ...............
(" − 1, & − '! )
%!
0
0
!(#, 0) = 0
(" − 1, &)
0 (",&)
0
(n, 0) 2021-02-03
(n, 1)
...............
CSC373 Winter 2021 - Sam Toueg
(n, *)
7
...............
...............
...............
Algorithm for 0-1 Knapsack
Knapsack(),, ... , )-, ,,, ... , ,-, -)
For 3 = 0 to - do 8(0, 3) ← 0 For9=0to:do8(9,0)← 0 For 9 = 1 to : do
running time: Z(! ⋅ ()
For 3 = 1 to - do
if 3 < ). then 8(9, 3) ← 8(9 − 1, 3)
else 8(9, 3) ← max{8(9 − 1, 3), 8(9 − 1, 3 − ).)+,.}
return 8(:, -) What if we also want to find the optimal set
H ← Ø; 9 ← : ; 3 ← - While9 >0and3>0do
of knapsack items instead of just its value?
if 8(9, 3) = 8(9 − 1, 3) then 9 ← 9 − 1
elseH←H ∪{9};9←9−1;3←3−).
return H
2021-02-03 CSC373 Winter 2021 – Sam Toueg 8
Running Time
• Computing all 4 5, 7 :
Ø”∈ 1,…,!
Ø U ∈ {1, … , (} (recall weights and capacity are integers) ØThere are Z ! ⋅ ( distinct T “,U to compute
Ø Each is computed only once
Ø Each takes Z(1) time to compute
Ø So the total running time is Z(! ⋅ () 2″# = 18,446,744,073,709,551,616
• Q: Is this running time polynomial in the input size?
Ø A: No! Because the number ( is exponential in the number of
bits to represent it (e.g., if ( is 64 bits-long, ( could be ≈ 2&’) So computing all T(“, U) is exponential in the size of the input
Ø But this is pseudo-polynomial: polynomial in the input values
Ø Is there a fully polynomial time algorithm? 2021-02-03 CSC373 Winter 2021 – Sam Toueg
iff P=NP!
9
A different algorithm for 0-1 Knapsack
• Q: What if instead of 0, 8;, … , 8< being small integers, we were told that :; , ... , :< and are small integers?
Ø Then we can use a different dynamic programming approach! First note that the maximum value that can be achieved
with all the ! items (if we had enough knapsack capacity) is: ] = #) + #* + ⋯ + ##
2021-02-03 CSC373 Winter 2021 - Sam Toueg 10
A different algorithm for 0-1 Knapsack
• 4(5, 🙂 = minimum capacity needed to pack
total value of at least : using items 1, ... , 5
ØGoal:Computemax#∈ 1,...,] ∶T!,# ≤( Ø where ] = #) + #* + ⋯ + ##
• Consider item 5
ØIfwedon’tchoose",weneedcapacityT "−1,#
Ø I f w e c h o o s e " , w e n e e d c a p a c i t y T ( " − 1 , # − # ) +& &+ !!!
! #,0 = • 1≤-≤.
min
0 ∞
! #−1,0 ,
.! + ! # − 1, 0 − 0!
if 0 ≤ 0
if 0 > 0, # = 0
if0>0,#>0
•0≤%≤/ 2021-02-03
runningtime:0 .⋅/ Sowecanget0(.⋅3)or0(.⋅/) CSC373 Winter 2021 – Sam Toueg 12
Approximate Solution
• Unless P =NP, we cannot hope to solve knapsack exactlyintimeZ cdef !,log(,log] …
Knapsack input size
• But we can find good approximate solutions in poly time:
Ø For any g > 0, we can get a knapsack value
that is at least 1 − g ]∗ , where ]∗ is the optimal value, intimeB C9DE 5,logI,logJ,”#
Ø Such algorithms are approximation algorithms
Ø Core idea for approximate solution to knapsack:
o Approximate all weights and values up to the desired precision o Solve knapsack on approximate input using DP
2021-02-03 CSC373 Winter 2021 – Sam Toueg 13