Please help The first part is listed in the picture. MATRIX-CHAIN-ORDER(p) PRINT
ID: 3819736 • Letter: P
Question
Please help
The first part is listed in the picture.
MATRIX-CHAIN-ORDER(p) PRINT-OPTIMAL-PARENS(s, i, ln p length -1 2 let ml1.n, 1., n] and s[1..n-1, 2., n] be new tables 2 print "A" i for 3 else print to 4 mli, i 30 4 PRINT-OPTIMAL PARENS(s, i, sli, jl) 5 for 2 to n //lis the chain length 5 PRINT-OPTIMAL-PARENS(s, sli, jl+1,j) 6 for i 1 to n-1 1 6 print m i, j] 9 for j-1 10 11 if q mli, j] 12 13 14 return m and s First, create a MATRIX-CHAIN-M class and include the bottom-up approach class ULTIPLICATION methods MATRIX-CHAIN-ORDER and PRINT-OPTIMAL-PARENS. The pseudocode for these two algorithms are given below. Also, you will need a recursive method MATRIX-CHAIN-MULTIPLY, as outlined in Exercise 15.2-2. Next, add to the class the top-down approaches RECURSIVE-CHAIN-MULTIPY and MEMOLzED-MATRIx- CHAIN together with its helper method LooKUP-CHAIN. Write a driver program that creates six matrices, Al through As of the dimensions given in the example shown in Figure 15.5. Fill the matrices with random integers on the interval (0, 100). Use a bottom-up approach to compute the product matrix A which is the result of multiplying all of the six input matrices together. Instrument your code so that you can measure the amount of time taken to compute the product matrix A Then use a top-down approach to compute the product matrix A using a recursive approach. Again, instrument your code to record the amount of time taken on the top-down recursive approach. Finally, use the top-down memoized approach to compute the product matrix A and record the time required Note the absence of the auxiliary array s in the top-down approach. When you have written and run all of the code, and observed the running times, write up your observations about the amount of running time and space required. Contemplate the advantages to learning about studying an algorithmic approach and learning how to make programming as efficient as possibleExplanation / Answer
/* A naive recursive implementation that simply
follows the above optimal substructure property */
#include<stdio.h>
#include<limits.h>
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChainOrder(int p[], int i, int j)
{
if(i == j)
return 0;
int k;
int min = INT_MAX;
int count;
// place parenthesis at different places between first
// and last matrix, recursively calculate count of
// multiplications for each parenthesis placement and
// return the minimum count
for (k = i; k <j; k++)
{
count = MatrixChainOrder(p, i, k) +
MatrixChainOrder(p, k+1, j) +
p[i-1]*p[k]*p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 2, 3, 4, 3};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, 1, n-1));
getchar();
return 0;
}