What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
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.
Write short notes on
Write short notes on
What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
What is Resource management?
Write a C program to transpose of a matrix.
