CS & IT 20 25

ENGINEERING
Algorithms

Dynamic Programming(DP)

Lecture No.- 05 By- Aditya sir

Recap of Previous Lecture

Topic 1 01 knapsack code

2 Complexity analysis
Topic
2 Common Subsequence
longest
 Topics to be Covered

Topic LCS DCode

Topic

3
 LIRocurrence
It LCS i i j e if sit Mj
i
LCS j

j 1

Icscij max
if tj
i i
j

4
 Topic : Algorithms
Algorithm LCS based on Bottom-up Tabulation method :
Algorithm LCS (x, y) To 1 2 n 1
Integer x[0..n], y [0..m]; x x An
{
integer L [0..n , 0..m];
1. for i ← 0 to n – 1
tfd

L [i, – 1] = 0;
2. for j ← 0 to m – 1
L [–1 , j] = 0;
3. for i ← 0 to n – 1
for j ← 0 to m – 1
me
Auxilaryspate­ff.FI
 Topic : Algorithms
If (x [i] = y [j]) then

else Lc
L[I, j] = 1 + L [I – 1, j – 1]; Diqonal­
L[i, j] = max { L [i – j,– 1], L [I – 1 j]};

max
ll­lLfisj7
Lti j 1 Li 1

TTP
left Ofman
SC
QmnI
5 matrix chain multiplication product MCM

B
a
given
two matrices A
of size

men and nxp

are
required
scalar
multiplications
How many
C 2
in Ann Bnxp

5
 Call Square matrices
Bnxn
Ann
A B

ii
101
921 922
2 220
Wyn
2 7 2

elems 2
22
ʰ

A ᵈ1
scale multistory
Here Total
921 611 922 621
12 2 2 2

CE
14 921 biz 922 622 2 21
 Square matrices Anent Brian m
Lalmultiplicating

14
 smaremahx Cmyp
love.no Amen Bnxp
B
A

7110111
110

MXI
I elem requires n

any
elem scalar multiplications
for all m xp
Here

Total scales multiplications Mx mxp MII

14
 Imp Result

In

B map
nxE

Scalar
multiplications
Total number
of
Mxn XP

14
 MIM Problem statement

ibe non square

Given
a
Dang to multiply
matrices it is required

them together
to get
a
final
resultant matrix

14
 matrices in chain
1 E3 no
of

A B Crox ABC 22
o 10 50 2 20

I
Parenthesization
ABI problem

output of both
A B C A BAC will be
same

14 1yd
 scaler multiplication
A B AC How
many
T B
mul 2 10
R C A2x1 52
Bessy
12 50

mul
AAB C 211
50 20
2 50
AAB C

So total scalar multiplications for 1000 2000

are 2 5042 50 20
14
3000g
 A BAC

Mul 10 50 20

10 150 20

10 20

2 20
mad 10
20
2710 A BAC

Scaler
multiplications for
Total
50 20
10
10401
14 2 10 20 400
 objective function
MCI
minimize the number of
to
Scales multiplications

A B C

A XB C
A BX

14
DPbasedapp roach.i­e

n matrices A A2 An
Given
a chain of
where matrix Ai is of
Dimension
PinxPI
mm

Paranthesize
The MCM problem
is to
fully
the chain such that the total number of
Scalar multiplications are minimizeds
30
1 2,20
14 B
 a How to multiply chain of
many ways
n matrices I
AiAzAgiAygg
2
14
4 1

3
ABI K

1 A A2 Azan
ATALA
Au
A B C AIA A A Ay

AC
AAB
A As Asx A2XN

A2X A3XAY A2 A yay

y
14 tways
 Generalieresult

Total no
of ways to multiply a chain
of
Catalan Number
motives
lost
g
MIT 613
1 Cn
E1i.in

matrices
mid n

14 6,15
 2h 1
a
n
matrices 1 C
n 1

14
 Recurrence MIM
DP based
Derivation of for

be the
Let the resultant matrix
Aij of
Product
1 t
Ai Air Aitz Aj
vervet AI
t t b
A A2 As An
Anna K 1 to n t
14
 Parenthesisation must
Any optimal
the chain about the matrix
split
AK AK Art such that the
A
are minimum
number
of Scales multiplications

14
DIRewee
the number scalar
Let m i
j represent of
multiplications to get the resultant matrix Aij

AixAit AKA Mfi

A
Aj Aij j
b splitatk where To
Akt Aj i K
j
1

Affk
Mti K
MSK I
j
14
 M i
j7 min mri k m k.tl
jI APj
Umm

IMI
mm
Ai Ak Akt Aj
Diend 1
Pinapi
I PelleanLm

p
Ri 122

peap pj.ca

Pi IA Pk Pk Pj
14
 ˢ
Example E A PoxP

A A2 A 4 As AG A2 PixPa 3 5
m 1,6 A 16
As 12 83 511
Au 8 4
AI A
Au Ag Bx Pu
2 3 5 8
8
47 6 As Es 4 7

o P1 P2 B
papp 1 P5XP6
Af PsXP6 7 6
m
1,3 mly 6
Po Pn
It
71
2 8
G
PF
mud of Po P3 P6 2 1 1 k 6
both14 Resultants Wem 811
3
j
Aretmolappingsubproblems
3
AI Az Az Au
K 1,2

K f I ES
ATATA AU
AI AzᵗA3 Ay AI 2 ASAY M 4,4
MCs 3
m 2 m
MAD m 214
3 4 1
4 2

A2 As
A ASAY AAS AY
Ac AzA3 A

m 2,2 mail msya

m 3
m mry u

14
 Down Recursion Approach
Top

Eg A A2 A AU
213 315 518 4
Po Pi P2 P3 Pu
n
P 253 5
8,4

9 The minimum no
of
Scales multiplications
chain A A2 As Ay
heard to mull the
14 min 240 723047401 01
 Sold
214 AtAtA3tAu
1,2 min 232,174
min 244,240

AzA3AN
2301

AIA 2
_yet
AAU A AzA3
174

Ay

5160
244 7 3240
120796
Lk 2

20 A2 A ATAYAY 120 30

16 As
230 Ailed
Of 1
A AZA A3Ay AI A2A3 AY CA A2 A Ay A1A2 A3

14 T F
 Ac Az A AU Az 5 8

An 8 4
5 4
3
f f Total mud
g

3 5
1 3 5 4
160
A A2
A3AI my 1601260
31
2

2 3 4 21
14
 A 72 43 Ay
48

ᵈ
3 8 4 96

12

I
3 216
2 4
3
In
2 3 4
21 21

14
 A A2 Azan 160730
41
01 160b
2 5 5 4

A A2 2 5 4
231
2 5 4 5
41
2 7 5 30

7 5

14
 Ai Azaz An
26 11 0345,2 08 4

2 8 4
2 3 8

Total 120 48 64

168 64

231
14
 A A2 Az Ay
30
2 5 51T 8 4
To 8
215
2 8 4

Total 30 80 66

110 64

174

14
 Topic : Algorithms 1
Bottom Tabulation
Algorithm Matrix-Chain-Product (p)
up

1. n ←length [p] ⎯ 1
p.an.fi
2. for i ← 1 to n

q ps m
3. do m[i ,i] ← 0 no
of
4. for Il ← 2 to n I is the chain length. matric
5. t
for I ← 1 to n – I + 1
O
6. J ← i + Il – 2 Digonals
Base condition
7. m[i, j] ← ∞
 Topic : Algorithms
8. for k ← i to j – 1

9. q ← m[ i , k] + m[k + 1, j] + Pi–1 Pk Pj

10. if (q < m [i , j]) r

11. then m[i , j] ← q

leagthofcha.it

12. s[i, j] ← k
13. return m and s
l

1 2 me 2

m
2,3
m 3 4
 0

THANK - YOU

Telegram Link for Aditya Jain sir:

https://t.me/AdityaSir_PW

13