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.
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
Write short notes on
What is SRS? Write the features of SRS.
What are tunnelling and encapsulation in the context of mobile IP?
Short Notes : UML
