Bsc CSIT Semester 5 – Design and Analysis of Algorithms – Unit 5. Dynamic Programming

What do you mean by Dynamic programming strategy? Explain the element of DP.

Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity.

What do you mean by memorization strategy? Compare memorization with dynamic programing.

Write the dynamic programming algorithm for matrix chain multiplication. Find the optimal parenthesization for the matrix chain product ABCD with size of each is given as A5×10 , B10×15 , C15×20 , D20×30

Find the edit distance between the string ” ARTIFICIAL” and “NATURAL” Using dynamic programming.

Write down advantages of dynamic programming over greedy. strategy.Find optimal bracketing to multiply 4 matrices of order (2,3,4,2,5).

Differentiate between dynamic programming and memorization. Compute the shortest path between every pairs in the following graphs using Floyd Warshal algorithm.

Write an algorithm to find the nth fibonacci number with its time and space complexity.

Define order statistics problem. Find the edit distance between "cat" and "car" using dynamic programming.

Distinguish between dynamic programming and memorization. Parenthesize the matrices A(30 × 1), B(1 × 40), C(40 × 10) and A(10 × 15), for computing matrix multiplication using dynamic programming.

Justify the worst case for binary search. Find the edit distance from the string "RELEVANT" to "ELEPHANT" using dynamic programming approach.