Question

We wish to find the length of the longest common subsequence (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] $\ne$ Y[j -1]

Which one of the following options is correct?

• A. expr1 $\equiv$ l(i -1, j) + 1
• B. expr2 $\equiv$ max (l(i-1, j - 1), l(i, j))
• C. expr1 $\equiv$ l(i, j -1)
• D. expr2 $\equiv$ max (l(i-1, j), l(i, j- 1))

Answer 1

The correct option is D expr2 $\equiv$ max (l(i-1, j), l(i, j- 1))

l(i . j) = 0; if either i = 0 or j = 0

= l(i - 1, j - 1);
if i, j > 0 and x[i - 1]=Y[j - 1]

= max (l(i - 1, j),l(i, j - 1));
if i . j > 0 and x[i - 1] $\ne$ Y[j - 1]

$\therefore expr2\equiv max\left(l\right(i-1,j),l(i,j-1\left)\right)$