Answer to Question #196170 in Algorithms for Emre

Question

PRINT-OPTIMAL-PARENS(s, i, j){

if (i=j) then

print “A”i else{

print “(”

PRINT-OPTIMAL-PARENS(s,i,s[i, j])

PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j)

print “)”} }

a- Test your algorithm for the following cases:

1. Find and print an optimal parenthesization of a matrix-chain product whose sequenceof dimensions is<5,10,3, X,12,5,50, Y,6>.

2. Find and print an optimal parenthesization of a matrix-chain product whose sequenceof dimensions is<5,10,50,6, X,15,40,18, Y,30,15, Z,3,12,5>.1

3. Find and print an optimal parenthesization of a matrix-chain product whose sequenceof dimensions is<50,6, X,15,40,18, Y,5,10,3,12,5, Z,40,10,30,5>.

b- Find the complexity of your program

c- Show that the parenthesization algorithm is loop invariant.

X=10, Y=20, Z=30

Answer 1

There are 6 matrices of dimensions $5\times 10,10\times 3,3\times12,12\times 5,5\times 50,50\times6$

Let the input 6 matrix be A, B, C,D,E and F. The minimum number of multiplications are obtained by putting parenthesis in following way

$((5×10)(10×3))(((3×12)(12×5))((5×50)(50×6))).$

2.

$5,10,50,6, X,15,40,18, Y,30,15, Z,3,12,5$

$=((5\times 10)(10\times 50))((6\times 15)(15\times 40))((40\times 18)(18\times 30))((30\times15)(15\times 3))((3\times 12)(12\times 5))$

The time complexity of the algorithm $O(n^3)$