Font size
WorksheetsDynamic Programming DAA
Total questions: 20
Worksheet time: 10mins
In dynamic programming, the technique of storing the previously calculated values is called ___________
Saving value property
Storing value property
Memorization
Mapping
Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
0
3
4
None of the above
What are 2 things required in order to successfully use the dynamic programming technique?
Optimal sub structure and overlapping sub problems
A problem that can’t be sub divided and is complex
Non overlapping sub problems and intervals
Recursion and a problem that is complex
Dynamic Programming is often used for (choose all that apply):
Optimization problems that involve making a choice that leave one or more subproblems to be solved.
Problems previously solved using divide and conquer that have over lapping subproblems
Non polynomial solution problems
Subproblems where resources are shared
The difference between Divide and Conquer and Dynamic Programming is:
The division of problems and combination of subproblems
Whether the sub problems overlap or not
The way we solve the base case
The depth of recurrence
If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.
Overlapping subproblems
Optimal substructure
Memorization
Greedy
Which of the following problems is NOT solved using dynamic programming?
0/1 knapsack problem
Matrix chain multiplication problem
Edit distance problem
Fractional knapsack problem
Find the longest increasing subsequence for the given sequence:
{10, -10, 12, 9, 10, 15, 13, 14}
{10, 12, 15}
{10, 12, 13, 14}
{-10, 12, 13, 14}
{-10, 9, 10, 13, 14}
For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
True
False
You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?
170
200
160
90
Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?
10*20
20*30
10*30
10*20*30
Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
6
7
8
9
In which of the following cases will the edit distance between two strings be zero?
When one string is a substring of another
When the lengths of the two strings are equal
When the two strings are equal
The edit distance can never be zero
Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.
True
False
Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
3
4
5
6
For which of the following pairs of strings is the edit distance maximum?
Sunday & Monday
Monday & Tuesday
Tuesday & Wednesday
Wednesday & Thursday
Which of the following problems is equivalent to the 0-1 Knapsack problem?
You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value
You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized
You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S
None of the mentioned
The 0-1 Knapsack problem can be solved using Greedy algorithm
True
False
Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?
dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
What is the time complexity of the dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?
O(n)
O(m)
O (m + n)
O(mn)
