15.2 Matrix-chain multiplication (Matrix multiplication)

Details and full solution for example 15.2 page (376) in the book (Introduction to Algorithms, Third Edition. by Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein )

To Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <30, 35, 15, 5, 10, 20, 25>.

Done by: Bakr AlMushaileh

 

Sequence	P0	P1	P2	P3	P4	P5	P6
Dimension	30	35	15	5	10	20	25

Matrix	A1	A2	A3	A4	A5	A6
Dimension	30 X 35	35 X 15	15 X 5	5 X 10	10 X 20	20 X 25

1	m(1,2)=m(1,1)+m(2,2)+P0P1P2		= 0 + 0 + (30 . 35 . 15) = 15750	K = 1
	m(2,3)=m(2,2)+m(3,3)+P1P2P3		= 0 + 0 + (35 . 15 . 5) = 2625	K = 2
	m(3,4)=m(3,3)+m(4,4)+P2P3P4		= 0 + 0 + (15 . 5 . 10)= 750	K = 3
	m(4,5)=m(4,4)+m(5,5)+P3P4P5		= 0 + 0 + (5 . 10 . 20)= 1000	K = 4
	m(5,6)=m(5,5)+m(6,6)+P4P5P6		= 0 + 0 + (10 . 20 . 25)= 5000	K = 5
2	m(1,3)=min	m(1,1)+m(2,3)+P0P1P3	=0+2625+ (30 . 35 . 5)= 7875	min = 7875 K=1
		m(1,2)+m(3,3)+P0P2P3	=15750+0+ (30 . 15 . 5)= 18000
	m(2,4)=min	m(2,2)+m(3,4)+P1P2P4	= 0 + 750 + (35 . 15 . 10)= 6000	min = 4375 K=3
		m(2,3)+m(4,4)+P1P3P4	= 2625 + 0 + (35 . 5 . 10)= 4375
	m(3,5)=min	m(3,3)+m(4,5)+P2P3P5	= 0 + 1000 + (15 . 5 . 20)= 2500	min = 2500 K=3
		m(3,4)+m(5,5)+P2P4P5	= 750 + 0 + (15 . 10 . 20)= 3750
	m(4,6)=min	m(4,4)+m(5,6)+P3P4P6	= 0 + 5000 + (5 . 10 . 25)= 6250	min = 3500 K=5
		m(4,5)+m(6,6)+P3P5P6	= 1000 + 0 + (5 . 20 . 25)= 3500
3	m(1,4)= min	m(1,1)+m(2,4)+P0P1P4	=0+4375+(30 . 35 . 10 )=14875	min = 9375 K=3
		m(1,2)+m(3,4)+P0P2P4	=15750+750+(30.15.10 )=21000
		m(1,3)+m(4,4)+P0P3P4	=7875+0+ (30 . 5 . 10)=9375
	m(2,5)= min	m(2,2)+m(3,5)+P1P2P5	=0+2500+(35 . 15 . 20 )=13000	min = 7125 K=3
		m(2,3)+m(4,5)+P1P3P5	=2625+1000+(35 . 5 . 20 )=5125
		m(2,4)+m(5,5)+P1P4P5	=4375+0+ (35 . 10 . 20)=11375
	m(3,6)= min	m(3,3)+m(4,6)+P2P3P6	=0+3500+(15 . 5 . 25)=5375	min = 5375 K=3
		m(3,4)+m(5,6)+P2P4P6	=750+5000+(15 .10. 25)=9500
		m(3,5)+m(6,6)+P2P5P6	=2500+0+ (15 . 20 . 25)= 10000
4	m(1,5)= min	m(1,1)+m(2,5)+P0P1P5	=0+7125+(30.35.20)=25125	min =11875 K=3
		m(1,2)+m(3,5)+P0P2P5	=15750+2500+(30.15.20)=27250
		m(1,3)+m(4,5)+P0P3P5	=7875+1000+(30.5.20)=11875
		m(1,4)+m(5,5)+P0P4P5	=9375+0+(30.10.20 )=15375
	m(2,6)= min	m(2,2)+m(3,6)+P1P2P6	=0+9375+(35.15.25 )=22500	min =10500 K=3
		m(2,3)+m(4,6)+P1P3P6	=2625+3500+(35.5.25)=10500
		m(2,4)+m(5,6)+P1P4P6	=4375+5000+(35.10.25)=18125
		m(2,5)+m(6,6)+P1P5P6	=7125+0+(35.20.25)=24625
5	m(1,6)= min	m(1,1)+m(2,6)+P0P1P6	=0+10500+(30.35.25)=36750	min =15125 K=3
		m(1,2)+m(3,6)+P0P2P6	=15750+9375+(30.15.25 )=36375
		m(1,3)+m(4,6)+P0P3P6	=7875+3500+(30.5.25 )=15125
		m(1,4)+m(5,6)+P0P4P6	=9375+5000+(30.10.25 )=21875
		m(1,5)+m(6,6)+P0P5P6	=11875+0+(30.20.25 )=26875

((A₁ (A₂ A₃))((A₄ A₅) A₆))