Java dynamic programming: for this project, we will implement Matrix Chain Multi
ID: 3707921 • Letter: J
Question
Java dynamic programming: for this project, we will implement Matrix Chain Multiplication
Exercise 15.2-2:
Figure 15.5
PRINT-OPTIMAL-PARENS(s, i, j) MATRIX-CHAIN-ORDER(p) 1 n = p.length-1 2 let m[1..n, 1..n] and s[1..n-1, 2.n] be new tables2 print "A" i 3 fori-1 to n 3 else print "C" 4 PRINT-OPTIMAL-PARENS(s, ?, s[i,j]) 5 PRINT-OPTIMAL-PARENS(s, s[i,j]+1,j) 5 for l- 2 to n /I I is the chain length 6 for i -1 to n- 1 6 print ")” j=i+1-1 8 m[i, j] 9 for k i to j-1 10 q = mli, k] + m[k+1, j] + pi-1 pp, 11 ifq?m[i,j] 12 13 14 return m and s m[i, j] = q sli, jl kExplanation / Answer
/*
Java dynamic programming: implementation Matrix Chain Multiplication
using tabularization method
*/
public class MatrixChainMultiplication {
void matrixchain(int a[]) //function for dynamically store the value
{
int q;
int n=a.length;
int m[][]=new int[n][n]; //2-D Array to store the values of table
int s[][]=new int[n][n]; //2-D Array to store the position of braces in the form of i and j
for (int i=1;i<n;i++)
m[i][i]=0;
for (int l=2;l<n;l++) //l is the length
{
for(int i=1 ;i<n-l+1;i++)
{
int j=i+l-1;
m[i][j]=Integer.MAX_VALUE;
for (int k=i ;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+a[i-1]*a[k]*a[j]; //optimal substructure of the MatrixChainMultiplication
if(q<m[i][j])
{
m[i][j]=q; //storing minnimum value to the array
s[i][j]=k;
}
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
System.out.print(m[i][j]+" ");
System.out.println();
}
print_optimal(s,1,6); //function call for printing the Table and the MatrixChainMultiplication order
}
void print_optimal(int s[][],int i,int j)
{
if (i==j)
System.out.print("A"+i); //minimum cost of the MatrixChainMultiplication
else
{
System.out.print("(");
print_optimal(s,i,s[i][j]); //recursively print the MatrixChainMultiplication chain order
print_optimal(s,s[i][j]+1,j);
System.out.print(")");
}
}
public static void main(String args[])
{
int a[]={30, 35, 15, 5, 10, 20, 25};//input array for Matrix Dimantion
MatrixChainMultiplication n=new MatrixChainMultiplication();
n.matrixchain(a);
}
}
Time Complexity: O(n^3)
Auxiliary Space: O(n^2)
Output:
0 0 0 0 0 0 0
0 0 15750 7875 9375 11875 15125
0 0 0 2625 4375 7125 10500
0 0 0 0 750 2500 5375
0 0 0 0 0 1000 3500
0 0 0 0 0 0 5000
0 0 0 0 0 0 0
((A1(A2A3))((A4A5)A6))
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.