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 the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
Find the recurrence relation of binary search and derive the time complexity of binary search.
Write a C program to find a number is AMSTRONG or NOT.
What is Weak entity set? Explain with suitable example.
What are the methodology for dialog design?
Difference between Inspections and Walkthrough
