GATE 2009 CSE & IT PYQ

Question

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?

Accepted Answer

expr2 = max( l(i − 1, j), l(i, j − 1))

Answer

expr1 = l(i − 1, j) + 1

Answer

expr1 = l(i, j − 1)

Answer

expr2 = max( l(i − 1,j − 1),l (i, j))