1
GATE CSE 2014 Set 2
Numerical
+2
-0
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 = ___.
2
GATE CSE 2011
+2
-0.6
Four matrices M1, M2, M3 and M4 of dimensions p $$\times$$ q, q $$\times$$ r, r $$\times$$ s and s $$\times$$ t respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 $$\times$$ M2) $$\times$$ (M3 $$\times$$ M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 $$\times$$ M2) $$\times$$ M3) $$\times$$ 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
3
GATE CSE 2009
+2
-0.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.

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 I(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]
The value 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 of 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 < r or q < s.
4
GATE CSE 2009
+2
-0.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.

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 I(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]
Which one of the following options is correct?
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))
GATE CSE Subjects
EXAM MAP
Medical
NEET