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
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination