Make your own free website on Tripod.com

 

 

COMP510

 

Assignment # 1

 

John To

 

MSCS Fall 2005

 

Exercise 1:

 

Find an optimal parenthesization of a matrix-chain product whose sequence of dimension is: {5, 10, 3, 12, 5, 50, 6}

 

Given Matrix-chain of

<5, 10, 3, 12, 5, 50, 6>

A1 = 5,10

A2 = 10,3

A3 = 3,12

A4 = 12,5

A5 = 5,50

A6 = 50,6

 

Resolve by split big problem into sub problems

Equation:

m[i,j]={min of m[i,k] = m[k+1, j] + Pi 1.Pi.Pj } (1)

i k < j

And

m[1,1] = m[2,2] = m[3,3] = m[4,4] = m[5,5] = m[6,6] = 0

 

m[1,2] = P0xP1xP2 = 5x10x3 = 150

m[2,3] = P1xP2xP3 = 10x3x12 = 360

m[3,4] = P2xP3xP4 = 3x12x5 = 180

m[4,5] = P3xP4xP5 = 12x5x50 = 3000

m[5,6] = P4xP5xP6 = 5x50x6 = 1500

 

From equation (1) we have:

m[1,3] = min of:

(k=1)

m[1,1] + m[1,2] + P0P1P3 = 5x10x3 + 5x10x12 = 750

(k= 2)

m[1,2] + m[3,3] + P0xP2xP3 = 150 + 0 + 5x3x12 = 330 (min)

 

m[1,4] = min of

(k=1)

m[1,1] + m[2,4] + P0xP1xP4

m[2,4] = m[2,2] + m[3,4] + P1xP2xP4 = 0 + 180 + 10x3x5 = 330 (for i = k = 2)

m[2,4] = m[2,3] + m[4,4] + P2xP3xP4 = 360 + 0 + 3x12x5 = 540 (k = 3)

m[1,4] = min of: 0 + 330 + 5x10x5 = 580

(k=2)

m[1,2] + m[3,4] + P0xP2xP4 = 150 + 180 + 5x3x5 = 405 (min)

(k=3)

m[1,3] + m[4,4] + P0xP3xP4 = 330 + 0 + 5x12x5 = 630

 

m[1,5] = min of

(k=1)

m[1,1] + m[2,5] + P0xP1xP5

m[2,5] = m[2,2] + m[3,5] + P1xP2xP5 (k=2)

m[3,5] = m[3,3] + m[4,5] + P2xP3P5 = 0 + 3000 + 2x12x50 = 4200 (k=3)

m[2,5] = 0 + 4200 + 10x3x50 = 5700

m[3,5] = m[3,4] + m[5,5] + P2xP4xP5 = 180 + 0 + 3x5x50 = 930 (k=4)

m[2,5] = 0 + 930 + 10x3x50 = 2430

m[1,5] = min of 0 + 2430 + 5x3x50 = 3180

m[2,5] = m[2,3] + m[4,5] + P1xP3xP5 = 180 + 3000 + 10x12x50 = 9150

m[1,5] = min of 0 + 9150 + 5x3x50 = 9900

m[2,5] = m[2,4] + m[5,5] + P1xP4xP5 = 330 + 0 + 10x5x50 = 2830

m[1,5] = 0 + 2830 + 5x3x50 = 3580

(k=2)

m[1,2] + m[3,5] + P0xP2xP5 = 150 + 930 + 5x3x50 = 1830 (min)

 

(k=3)

m[1,3] + m[4,5] + P0xP3xP5 = 330 + 3000 + 5x12x50 = 6330

 

(k=4)

m[1,4] + m[5,5] + P0xP4xP5 = 405 + 0 + 5x5x50 = 1655 (min)


 

m[1,6] = min of

(k=1)

m[1,1] + m[2,6] + P0xP1xP6

m[2,6] = m[2,2] + m[3,6] + P1xP2xP6

m[3,6] = m[3,3] + m[4,6] + P2xP3xP6

m[4,6] = m[4,4] + m[5,6] + P3xP4xP6 = 0 + 1500 + 12x5x6 = 1860

m[4,6] = m[4,5] + m[6,6] + P3xP5xP6 = 3000 + 0 + 12x50x6 = 6600

m[3,6] = 0 + 1860 + 3x12x6 = 2076 (k=3)

m[3,6] = m[3,4] + m[5,6] + P2xP4xP6 = 180 + 1500 + 3x5x6 = 1770 (k=4)

m[3,6] = m[3,5] + m[6,6] + P2xP5xP6 = 930 + 0 + 3x50x6 = 1830 (k=5)

m[2,6] = 0 + 1770 + 10x3x6 = 1950 (k=2)

m[2,6] = m[2,3] + m[4,6] + P1xP3xP6 = 360 + 1860 + 10x12x6 = 2940 (k=3)

m[2,6] = m[2,4] + m[5,6] + P1xP4xP6 = 330 + 1500 + 10x5x6 = 2130 (k=4)

m[2,6] = m[2,5] + m[6,6] + P1xP5xP6 = 360 + 1860 + 10x50x6 = 5220

m[1,6] = 0 + 1950 + 5x10x6 = 2250 (k=1)

 

(k=2)

m[1,6] = m[1,2] + m[3,6] + P0xP2xP6 = 150 + 1770 + 5x3x6 = 2010 (k=2, min)

 

(k=3)

m[1,6] = m[1,3] + m[4,6] + P0xP3xP6 = 330 + 1860 + 5x12x6 = 2550 (k=3)

 

(k=4)

m[1,6] = m[1,4] + m[5,6] + P0xP4xP6 = 1500 + 405 + 5x5x6 = 2055 (k=4)

 

(k=5)

m[1,6] = m[1,5] +m [6,6] + P0xP5xP6 = 1665 + 0 + 5x50x6 = 3165 (k=5)

 

m[2,4] = min of

m[2,4] = m[2,2] + m[3,4] + P1xP2xP4 = 0 + 180 + 10x3x5 = 330 (k = 2)

 

m[2,5] = min of

m[2,5] = m[2,2] + m[3,5] + P1xP2xP5 = 0 + 930 + 10x3x50 = 2430 (k=2)

 

m[2,6] = min of

m[2,6] = m[2,2] + m[3,6] + P1xP2xP6 = 0 + 1770 + 10x3x6 = 1950 (k=2)

 

m[3,5] = min of

m[3,5] = m[3,4] + m[5,5] + P2xP4xP5 = 180 + 0 + 3x5x50 = 930 (k=4)

 

m[3,6] = min of

m[3,6] = m[3,4] + m[5,6] + P2xP4xP6 = 180 + 1500 + 3x5x6 = 1770 (k=4)

 

m[4,6] = min of

m[4,6] = m[4,4] + m[5,6] + P3xP4xP6 = 0 + 1500 + 12x5x6 = 1860 (k=4)

 

Construct the m table:

 

 

 

 

i

 

 

 

 

 

1

2

3

4

5

6

 

6

2010

1950

1770

1840

1500

0

 

5

1655

2430

930

3000

0

 

j

4

405

330

180

0

 

 

 

3

330

360

0

 

 

 

 

2

150

0

 

 

 

 

 

1

0

 

 

 

 

 

 

Fill out the S table

 

1 2 3 4 5

6| 2 2 4 4 5

5| 4 2 4 4

4| 2 2 3

3| 2 2

2| 1

 

Therefore the answer is

((A1A2)(A3A4)(A5A6))

 

 

 

Exercise 2:

 

Give a recursive algorithm Matrix-Chain-Multiply (A,s,i,j) that actually performs the optimal matrix-chain multiplication, given the sequence of matrices <A1,A2, , An>, the S table computed by Matrix-Chain-Order, and the indices i and j. (The initial call would be MATRIX-CHAIN-MULTIPLY (A,s,1,n)).

 

MATRIX-CHAIN-MULTIPLY(A,s,1,n)

if i = j

return A1

else

return MATRIX-CHAIN-MULTIPLY(A,s,1,s[1,n])

return MATRIX-CHAIN-MULTIPLY(A,s,s[1,n] + 1, j)