Gate CS-2009 Question Paper With Solutions

Q. 8 A sub-sequence of a given sequence is just the given sequence with some elements
(possibly none of all) left out. We are given two sequence X[m] and Y[n] of length
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] of lengths m and 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]

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))

Answer: (C)

Explanation:

Gate CS-2009 Question Paper With Solutions

Learn More:   Gate EE-2016-2 Question Paper With Solutions

LEAVE A REPLY

Please enter your comment!
Please enter your name here