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 = _________.
34 | |
35 | |
36 | |
37 |
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
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?
Which of the following statements is TRUE?The algorithm uses dynamic programming paradigm | |
The algorithm has a linear complexity and uses branch and bound paradigm | |
The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm | |
The algorithm uses divide and conquer paradigm. |
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
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:
248000 | |
44000 | |
19000 | |
25000 |
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.
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
max(Y, a0+Y) | |
max(Y, a0+Y/2)
| |
max(Y, a0+2Y) | |
a0+Y/2
|
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 ori∈R it is possible that Y>a0+Y/2.
Note: Y/2 meaning: Each number picked in Y will get divided by 2
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
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]
expr1 ≡ l(i-1, j) + 1 | |
expr1 ≡ l(i, j-1) | |
expr2 ≡ max(l(i-1, j), l(i, j-1)) | |
expr2 ≡ max(l(i-1,j-1), l(i,j)) |
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)?
All elements L should be initialized to 0 for the values of l(i,j) to be properly computed. | |
The values of l(i,j) may be computed in a row major order or column major order of L(M,N). | |
The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N).
| |
L[p,q] needs to be computed before L[r,s] if either p |
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
X[i, j] = X[i - 1, j] ∨ X[i, j - ai]
| |
X[i, j] = X[i - 1, j] ∨ X[i - 1, j - ai]
| |
X[i, j] = X[i - 1, j] ∧ X[i, j - ai]
| |
X[i, j] = X[i - 1, j] ∧ X[i -1, j - ai] |
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.
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?
Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?X[1, W]
| |
X[n, 0] | |
X[n, W] | |
X[n-1, n] |
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.
Note: As per present GATE syllabus, this concept is not required.
There are 8 questions to complete.