[go: up one dir, main page]
Scribd
Upload
9 views9 pages

Sample EXP 3

The document outlines an experiment on the Dynamic Programming approach, specifically focusing on matrix chain multiplication. It details the objectives, theory, pseudocode, and Java program implementation, along with the time complexity analysis, which is consistently O(n^3) for best, average, and worst cases. The conclusion emphasizes the efficiency of dynamic programming in optimizing complex problems like matrix chain multiplication.

Uploaded by

Tanay Kinariwala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views9 pages

Sample EXP 3

The document outlines an experiment on the Dynamic Programming approach, specifically focusing on matrix chain multiplication. It details the objectives, theory, pseudocode, and Java program implementation, along with the time complexity analysis, which is consistently O(n^3) for best, average, and worst cases. The conclusion emphasizes the efficiency of dynamic programming in optimizing complex problems like matrix chain multiplication.

Uploaded by

Tanay Kinariwala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

Subject Design and Analysis of Algorithms (CS205)

Name Purav Ahya

UID no. 2022300001

Batch Comps A – (A)

Experiment No. 4

AIM : Experiment on Dynamic Programming Approach

Objective : 1. To implement Dynamic Programming


2. To perform matrix chain multiplication using dynamic programming
3. Calculating time complexity for it.
The primary use of dynamic programming is as an improvement above simple
Theory : recursion. Dynamic programming may be used to optimise recursive solutions that
include repeated calls for the same inputs. To avoid having to recalculate
subproblem outcomes later on, the idea is to just store them. With this
straightforward optimisation, time complexities are reduced from exponential to
polynomial.
Matrix Chain Multiplication

The Matrix Chain Multiplication technique is utilized to ascertain the most


economical method of multiplying matrices. The actual multiplication is carried out
by multiplying the matrices following the conventional procedure, which is based on
the fundamental requirement that the number of rows in one matrix match the
number of columns in another matrix. To obtain the product, several scalar
multiplications must be performed.

To brief it further, consider matrices A, B, C, and D, to be multiplied; hence, the


multiplication is done using the standard matrix multiplication. Multiple
combinations of the matrices are found while using the standard approach since
matrix multiplication is associative.

Matrix Chain Multiplication Pseudocode

MATRIX-CHAIN-MULTIPLICATION(p)
n = p.length ─ 1
let m[1…n, 1…n] and s[1…n ─ 1, 2…n] be new matrices
for i = 1 to n
m[i, i] = 0
for l = 2 to n // l is the chain length
for i = 1 to n - l + 1
j=i+l-1
m[i, j] = ∞
for k = i to j - 1
q = m[i, k] + m[k + 1, j] + pi-1pkpj
if q < m[i, j]
m[i, j] = q
s[i, j] = k
return m and s
Algorithm:
Matrix Chain Multiplication :

MATRIX-CHAIN-ORDER (p)

1. n length[p]-1
2. for i ← 1 to n
3. do m [i, i] ← 0
4. for l ← 2 to n // l is the chain length
5. do for i ← 1 to n-l + 1
6. do j ← i+ l -1
7. m[i,j] ← ∞
8. for k ← i to j-1
9. do q ← m [i, k] + m [k + 1, j] + pi-1 pk pj
10. If q < m [i,j]
11. then m [i,j] ← q
12. s [i,j] ← k
13. return m and s.

To print :

PRINT-OPTIMAL-PARENS (s, i, j)
1. if i=j
2. then print "A"
3. else print "("
4. PRINT-OPTIMAL-PARENS (s, i, s [i, j])
5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j)
6. print ")"
Program
Code : import java.util.Scanner;

class Dp {
static char name;

// Function for printing the optimal parenthesization of a matrix


chain product
static void printParenthesis(int i, int j, int n,
int[][] dp) {

// If only one matrix left


if (i == j) {
System.out.print(name++);
return;
}
System.out.print("(");

printParenthesis(i, dp[i][j], n, dp);


printParenthesis(dp[i][j] + 1, j, n, dp);
System.out.print(")");
}

static void matrixChainOrder(int p[], int n) {

int[][] m = new int[n][n];


int[][] dp = new int[n][n];

// 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] = Integer.MAX_VALUE;
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;
dp[i][j] = k;
}
}
}
}
System.out.println("\nOptimal Cost is : " + m[1][n - 1]);

// Print matrix chain table (m)


System.out.println("\nMatrix Chain Table (m):");
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
System.out.print(m[i][j] + "\t");
}
System.out.println();
}

// Print split point table (dp or k table)


System.out.println("\nK Table :");
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println();
}

// The first matrix is printed as 'A', next as 'B'


name = 'A';
System.out.print("\nOptimal Parenthesization is : ");
printParenthesis(1, n - 1, n, dp);
}

public static void main(String[] args) {


Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of matrices : ");
int n = sc.nextInt();
int arr[] = new int[n + 1]; // +1 because dimensions start from 0
to n
System.out.println("Enter the dimensions of each matrix :");
for (int i = 0; i <= n; i++) {
arr[i] = sc.nextInt();
}
matrixChainOrder(arr, n + 1); // +1 because dimensions start from
0 to n
System.out.println();
sc.close();
}
}
Output : Matrix Chain Multiplication :

Solving :
Result : 1. Best Case : O(n^3)
 In the best case, the time complexity of the dynamic programming
approach for matrix chain multiplication is O(n^3), where n is the
number of matrices. This occurs when the input matrices are
already in the optimal order, and the algorithm only needs to fill
the dp table.
2. Average Case : O(n^3)
 The average case time complexity of the dynamic programming
approach for matrix chain multiplication is also O(n^3). This is
because, on average, the algorithm will need to consider all
subproblems and fill the dp table, leading to cubic time complexity.
3. Worst Case : O(n^3)
 The worst case time complexity of the dynamic programming
approach for matrix chain multiplication is O(n^3). This occurs
when the input matrices are in the worst possible order, and the
algorithm needs to consider all subproblems and fill the dp table,
resulting in the highest time complexity.

Conclusion : The temporal complexity of matrix chain multiplication with dynamic


programming is O(n^3), where n is the number of matrices in the chain. The
algorithm's capacity to divide the problem into smaller subproblems and store the
solutions to those subproblems reduces the amount of unnecessary computations,
which leads to this efficiency. The approach finds the optimal matrix
multiplication order by filling the cost and split point matrices successively.
Because it keeps the total time complexity under control, dynamic programming
is a useful technique for resolving challenging optimisation issues like matrix
chain multiplication. Matrix chain multiplication taught me about dynamic
programming.

You might also like