Question on problems on algorithms, the topics on Dynamic programming. Here is t

Question

Question on problems on algorithms, the topics on Dynamic programming.

Here is the Question

The iterated matrix product problem is perhaps the most popular example of dynamic programming used in algorithms texts. Given n matrices, M_1, M_2, ..., M_n, where for 1 lessthanorequalto i lessthanorequalto n, M_i is a r_i - 1 times r_i matrix, parenthesize the product M_1 middot M_2 ... M_n so as to minimize the total cost, assuming that the cost of multiplying an r_i - 1 times r_i matrix by a r_i times r_i + 1 matrix using the naive algorithm is r_i - 1 r_i r_i + 1 (See also Problems 91 and 263.) Here is the dynamic programming algorithm for the matrix product problem: function matrix(n) for i:= 1 to n do m[I, i]:= 0 for d:= 1 to n - 1 do for i:= 1 to n - d do j:= i + d m[i, j]:= min_i lessthanorequalto k

Explanation / Answer

import java.util.Scanner;

public class MatrixMultiplication {

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.print("Enter number of rows in A: ");
int rowsInA = s.nextInt();
System.out.print("Enter number of columns in A / rows in B: ");
int columnsInA = s.nextInt();
System.out.print("Enter number of columns in B: ");
int columnsInB = s.nextInt();
int[][] a = new int[rowsInA][columnsInA];
int[][] b = new int[columnsInA][columnsInB];
System.out.println("Enter matrix A");
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
a[i][j] = s.nextInt();
}
}
System.out.println("Enter matrix B");
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < b[0].length; j++) {
b[i][j] = s.nextInt();
}
}
int[][] c = multiply(a, b);
System.out.println("Product of A and B is");
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < c[0].length; j++) {
System.out.print(c[i][j] + " ");
}
System.out.println();
}
}

public static int[][] multiply(int[][] a, int[][] b) {
int rowsInA = a.length;
int columnsInA = a[0].length; // same as rows in B
int columnsInB = b[0].length;
int[][] c = new int[rowsInA][columnsInB];
for (int i = 0; i < rowsInA; i++) {
for (int j = 0; j < columnsInB; j++) {
for (int k = 0; k < columnsInA; k++) {
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
}
return c;
}
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.