Question

Find an optimal parenthesization for matrix-chain multiplications using any language PYTHON/Java/C++ ,C for the number {26, 9, 41, 18, 13, 22, 28, 32, 25, 26, 30, 37, 19, 47, 11, 24, 20} using a straight forward-recursive solution. The output must be three lines: 1) the first line contains the optimal number of multiplication 2) the second line contains the optimal parenthesization and 3) the third line is the time required to compute the optimal parenthesization

Answer 1

Solution::)

// C++ program to print optimal parenthesization
// in matrix chain multiplication.
#include<bits/stdc++.h>
using namespace std;
  
// Function for printing the optimal
// parenthesization of a matrix chain product
void printParenthesis(int i, int j, int n,
int *bracket, char &name)
{
// If only one matrix left in current segment
if (i == j)
{
cout << name++;
return;
}
  
cout << "(";
  
// Recursively put brackets around subexpression
// from i to bracket[i][j].
// Note that "*((bracket+i*n)+j)" is similar to
// bracket[i][j]
printParenthesis(i, *((bracket+i*n)+j), n,
bracket, name);
  
// Recursively put brackets around subexpression
// from bracket[i][j] + 1 to j.
printParenthesis(*((bracket+i*n)+j) + 1, j,
n, bracket, name);
cout << ")";
}
  
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
void matrixChainOrder(int p[], int n)
{
/* For simplicity of the program, one extra
row and one extra column are allocated in
m[][]. 0th row and 0th column of m[][]
are not used */
int m[n][n];
  
// bracket[i][j] stores optimal break point in
// subexpression from i to j.
int bracket[n][n];
  
/* m[i,j] = Minimum number of scalar multiplications
needed to compute the matrix A[i]A[i+1]...A[j] =
A[i..j] where dimension of A[i] is p[i-1] x p[i] */
  
// cost is zero when multiplying one matrix.
for (int i=1; i<n; i++)
m[i][i] = 0;
  
// L is chain length.
for (int L=2; L<n; L++)
{
for (int i=1; i<n-L+1; i++)
{
int j = i+L-1;
m[i][j] = INT_MAX;
for (int k=i; k<=j-1; k++)
{
// q = cost/scalar multiplications
int q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
{
m[i][j] = q;
  
// Each entry bracket[i,j]=k shows
// where to split the product arr
// i,i+1....j for the minimum cost.
bracket[i][j] = k;
}
}
}
}
  
// The first matrix is printed as 'A', next as 'B',
// and so on
char name = 'A';
  
cout << "Optimal Parenthesization is : ";
printParenthesis(1, n-1, n, (int *)bracket, name);
cout<<"\n";
cout << "Optimal Cost is : " << m[1][n-1];
cout<<"\n";
  
}
  
// Driver code
int main()
{
int arr[] = {26, 9, 41, 18, 13, 22, 28, 32, 25, 26, 30, 37, 19, 47, 11, 24, 20} ;
int n = sizeof(arr)/sizeof(arr[0]);
matrixChainOrder(arr, n);
return 0;
}

OUTPUT:

Optimal Parenthesization is : (A(((((((((((((BC)D)E)F)G)H)I)J)K)L)(MN))O)P))
Optimal Cost is : 84397

I tried my level best..Thank you
CAUsers Personal Desktop abc.cpp Dev-C++5.11 File Edit Search View Project Execute Tools AStyle WindowHelp Pl.I. Untitled! abc.cpp 2 II C++ program to print optimal parenthesization 3 in matrix chain multiplication #includec bits/stdc++, h》 5 using namespace std; 7 Function for printing the optimal 8 parenthesization of a matrix chain product 9 void printParenthesis(int i, int j, int n, 18 int *bracket, char &name) 11void printParenthesis (int, int j, int n, int 'bracket, char &nane) 12 13 if (i j) 15 16 17 18 19 20 21 cout くく name ++j returnj cout <« "( // Recursively put brackets around subexpression I/ from i to bracketfij3) // Note that ""((brackett许)tj)" is similar to // bracketiJlj] printParenthesis(i, ((bracket i*n)-), n, 23 25 26 bracket, name)5 Compiler % Resources dh compile Log Debug @ Find Results榧 Close - Errors: o - Warnings: 0 - Output Filename: C:AUsers\ Personal\Desktoplabc.exe Output Size: 1.83399391174316 MiB - Compilation Time: 8.98s Shorten compiler paths Line: 10 Col: 17 Sel: 0 Lines: 102 Length: 2990 Done parsing in 0.093 seconds 02-11 PM 09-05-2019

CAUsers Personal Desktop abc.cpp Dev-C++5.11 File Edit Search View Project Execute Tools AStyle WindowHelp Pl.I. Untitled! abc.cpp 2 II C++ program to print optimal parenthesization 3 in matrix chain multiplication #includec bits/stdc++, h》 5 using namespace std; 7 Function for printing the optimal 8 parenthesization of a matrix chain product 9 void printParenthesis(int i, int j, int n, 18 int *bracket, char &name) 11void printParenthesis (int, int j, int n, int 'bracket, char &nane) 12 13 if (i j) 15 16 17 18 19 20 21 cout くく name ++j returnj cout <« "( // Recursively put brackets around subexpression I/ from i to bracketfij3) // Note that ""((brackett许)tj)" is similar to // bracketiJlj] printParenthesis(i, ((bracket i*n)-), n, 23 25 26 bracket, name)5 Compiler % Resources dh compile Log Debug @ Find Results榧 Close - Errors: o - Warnings: 0 - Output Filename: C:AUsers\ Personal\Desktoplabc.exe Output Size: 1.83399391174316 MiB - Compilation Time: 8.98s Shorten compiler paths Line: 10 Col: 17 Sel: 0 Lines: 102 Length: 2990 Done parsing in 0.093 seconds 02-11 PM 09-05-2019

CAUsers Personal Desktop abc.cpp Dev-C++5.11 File Edit Search View Project Execute Tools AStyle WindowHelp PUntitled1 abc.cpp //g-cost/scalar multiplications int q = "[i][k] + t (k+1][j] + pli-1]*p[k]+plj); if (qく"[i][j]) 70 72 73 bracket[i][j]-k; 7S 76 // The first matrix is printed as A, next as B // and so on char name A cout くく "optimal Parenthesization is : "; printParenthesis (1, n-1, n, int )bracket, name)3 cout<<In" cout << "Optimal Cost is<mn-1] cout<<"In" 78 79 85 86 89 Driver code 9n main() int arrl 26, 9, 41, 18, 13, 22, 28, 32, 25, 26, 3, 37, 19, 47, 11, 24, 28]; int n = sizeof(arr)/sizeof(arr[0]); matrixChainOrderfarr n) 93 Compiler % Resources dh compile Log Debug @ Find Results榧 Close - Errors: o - Warnings: 0 - Output Filename: C:AUsers\ Personal\Desktoplabc.exe Output Size: 1.83399391174316 MiB - Compilation Time: 8.98s Shorten compiler paths Line: 80 Col: 22 Sel: 0 Lines: 6 Length: 2806 Done parsing in 0.015 seconds 02-12 PM 09-05-2019 A4)

CAUsers Personal\Desktoplabc.exe ptimal Cost is: 84397 rocess exited after 0.0197 seconds with return value e ress any key to continue . . .