## Dynamic-Programming

 Question 1
Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x+10y = _________.
 A 34 B 35 C 36 D 37
Algorithms       Dynamic-Programming       Gate 2014 Set -02
Question 1 Explanation:
Given is
A = “qpqrr” B = “pqprqrp”
The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:
(1) qpqr
(2) pqrr
(3) qprr
So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34
 Question 2
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below. Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array Which of the following statements is TRUE?
 A The algorithm uses dynamic programming paradigm B The algorithm has a linear complexity and uses branch and bound paradigm C The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm D The algorithm uses divide and conquer paradigm.
Algorithms        Dynamic-Programming       Gate 2011
Question 2 Explanation:
Key Note of Dynamic programming: 1. Dynamic programming is when you use past knowledge to make solving a future problem easier.
2. Dynamic programming is a technique used to avoid computing multiple time the same sub-problem in a recursive algorithm.
Note: It is neither backtracking nor branch and bound because we are not branching anywhere in the solution space. The algorithm is not divide and conquer as we are not dividing the problem and then merging the solution
 Question 3
Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is:
 A 248000 B 44000 C 19000 D 25000
Algorithms        Dynamic-Programming       Gate 2011
Question 3 Explanation:
Given matrices are, p = 10
q = 100
r = 20
s = 5
t = 80
Total no. of matrix multiplication for (n+1) matrices,
2nCn/(n+1)
Here,
n+1 = 4
n = 3
So, total no. of matrix multiplication possible is,
6C3/4 = ∠6/∠3×∠3×4 = 5
So, total 5 cases are possible,
Case 1:
(((M1 × M2) × M3) × M4) ∴ Total no. of scalar multiplications needed is,
20000 + 4000 + 1000 = 25000
Case 2:
((M1 × M2) × (M3 × M4)) ∴ Total no. of scalar multiplications needed is,
20000 + 8000 + 16000 = 44000
Case 3:
(M1 ×(M2 ×(M3 × M4))) ∴ Total scalar multiplications,
160000 + 80000 + 8000 = 248000
Case 4:
((M1 ×(M2 ×M 3)) × M4) ∴ Total scalar multiplications,
10000 + 5000 + 4000 = 19000
Case 5:
(M1 × ((M2 × M3) × M4)) ∴ Total scalar multiplications,
10000 + 40000 + 80000 = 130000
Hence, the minimum number of scalar multiplications is, 19000.
 Question 4
The weight of a sequence a0, a1, ..., an-1 of real numbers is defined as a0+a1/2+...+ an-1/2n-1.  A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0, a1, ...,an-1 and Y the maximum possible weight of a subsequence of a1, a2, ..., an-1. Then X is equal to
 A max(Y, a0+Y) B max(Y, a0+Y/2) C max(Y, a0+2Y) D a0+Y/2
Algorithms        Dynamic-Programming       2010
Question 4 Explanation:
Using concepts of Dynamic Programming, to find the maximum possible weight of a subsequence of X, we will have two alternatives:
1. Do not include a0 in the subsequence: then the maximum possible weight will be equal to maximum possible weight of a subsequence of {a1, a2,….an} which is represented by Y
2. Include a0: then maximum possible weight will be equal to : a0 + (each number picked in Y will get divided by 2) = a0 + Y/2.
Key point here is Y will itself pick optimal subsequence to maximize the weight. The value of a0 can be anything (negative or i∈R it is possible that Y>a0+Y/2.
Note: Y/2 meaning: Each number picked in Y will get divided by 2
 Question 5
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below: l(i,j) = 0, if either i=0 or j=0 = expr1, if i,j > 0 and X[i-1] = Y[j-1] = expr2, if i,j > 0 and X[i-1] != Y[j-1]
 A expr1 ≡ l(i-1, j) + 1 B expr1 ≡ l(i, j-1) C expr2 ≡ max(l(i-1, j), l(i, j-1)) D expr2 ≡ max(l(i-1,j-1), l(i,j))
Algorithms        Dynamic-Programming       2009
Question 5 Explanation:
The recursive definition for the function l(i, j) to compute the length of the LCS of X[m] and Y[n] is given below, Question 6
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0. The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j).

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?

 A All elements L should be initialized to 0 for the values of l(i,j) to be properly computed. B The values of l(i,j) may be computed in a row major order or column major order of L(M,N). C The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N). D L[p,q] needs to be computed before L[r,s] if either p
Algorithms        Dynamic-Programming       2009
Question 6 Explanation:
LCS procedure can followed by either row major or column major order. We can get the same solution by any order. The above question looks very big but they are explaining the procedure of LCS.
 Question 7
The subset-sum problem is defined as follows. Given a set of n positive integers,S = {a1 , a2 , a3 ,..., an },   and  positive  integer  W,  is  there  a  subset  of  S  whose elements sum to W? A dynamic program for solving this A X[i, j] = X[i - 1, j] ∨ X[i, j - ai] B X[i, j] = X[i - 1, j] ∨ X[i - 1, j - ai] C X[i, j] = X[i - 1, j] ∧ X[i, j - ai] D X[i, j] = X[i - 1, j] ∧ X[i -1, j - ai]
Algorithms        Dynamic-Programming       Gate-2008
Question 7 Explanation:
X[I, j] (2 <= i <= n and ai <= j <= W) is true if any of the following is true.
1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true.
2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.
 Question 8
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 , a2 , a3 ,..., an },   and  positive  integer  W,  is  there  a  subset  of  S  whose elements sum to W? A dynamic program for solving this Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
 A X[1, W] B X[n, 0] C X[n, W] D X[n-1, n]
Algorithms        Dynamic-Programming       Gate-2008
Question 8 Explanation:
The last row and last column given the value is 1 then subset of whose elements sum to W.
Note: As per present GATE syllabus, this concept is not required.
There are 8 questions to complete.