MindStudy - MindStudy

Question:

Published on: 23 February, 2025

What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.

Answer:

Dynamic Programming:

It is a problem solving technique like divide and conquer where problems are divided into subproblems. Dynamic programming is used when the subproblems are not independent. It can solve optimization problem as well as the multistage decision problems. It is a bottom-up mechanism-we solve all possible small problems and then combine them to obtain solutions for bigger problems.

Algorithm of chain matrix multiplication:

Matrix-Chain(array p[1 .. n], int n) 
{
         Array s[1 .. n − 1, 2 .. n];
         for i = 1 to n 
              do m[i, i] = 0;                                             // initialize
         for L = 2 to n do {                                             // L=length of subchain
              for i = 1 to  n − L + 1 do {
                   j = i + L − 1;
                   m[i, j] = infinity;
                   for k = i to j − 1 do {                             // check all splits
                        q = m[i, k] + m[k + 1, j] + p[i − 1] p[k] p[j];
                        if (q < m[i, j]) {
                             m[i, j] = q; 
                             s[i, j] = k; 
                        }
                    } 
               } 
           }
           return m[1, n](final cost) and s (splitting markers); 
}

where p is the input array, m is the auxiliary array and s is the splitting array.

Subjects

Computer Graphics and Multimedia Data Structures & Algorithm Design and Analysis of Algorithm C Programming and Practices Database Management System Compiler Design

Trending

What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.

23 February, 2025

Why Recursion tree method is best than the Substitution method for solving a recurrence relation? Find the asymptotic upper bound of the following recurrence relation with the help of recursion tree method.

T(n)=T(n/4)+T(n/2)+Θ(n²)

23 February, 2025

Define classes P,NP,NP hard and NP-complete and also explain their relationship diagrammatically. What is nondeterministic algorithm? Explain with example. Define circuit satisfiability problem and prove that circuit SAT is in NP class.

23 February, 2025

Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.

23 February, 2025

Write short notes on