GATE CSE 2009 | Question: 53

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?

• A. $\text{expr1} = l\left(i-1, j\right) +1$

• B. $\text{expr1} = l\left(i, j-1\right)$

• C. $\text{expr2} = \max\left(l\left(i-1, j\right), l\left(i,j-1\right)\right)$

• D. $\text{expr2} = \max\left(l\left(i-1, j-1\right), l\left(i,j\right)\right)$

Comments

I think it must be l(i-1, j-1) +1

---

I think expr1 = l(i-1,j-1)+1

and expr2=max(l(i-1,j),l(i,j-1))

---

is there a video solutio for this?

Answer 1

Answer is C. When the currently compared elements doesn't match, we have two possibilities for the LCS, one including X[i] but not Y[j] and other including Y[j] but not X[i].

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

Comments

i have same doubt it has to be 1+c[i-2][j-2] otherwise algo will run into an infinite loop pls clarify in many areas it is given wrong

---

Its an algorithm not a piece of code that it will run for infinite times . These small things are taken care of while writing code.

---

valid point learnt something new thanks

Answer 2

Answer is C. 

When the currently compared elements doesn't match, we have two possibilities for the LCS, one including $X\left [ i \right ]$ but not $Y\left [ j \right ]$  and other including $Y\left [ j \right ]$ but not $X\left [ i \right ]$.

Answer 3

The standard LCS recurrence is:

\[
l(i,j)=
\begin{cases}
0, & \text{if } i=0 \text{ or } j=0 \\[4pt]
l(i-1,j-1)+1, & \text{if } X[i-1]=Y[j-1] \\[4pt]
\max(l(i-1,j),\,l(i,j-1)), & \text{if } X[i-1]\ne Y[j-1]
\end{cases}
\]

Therefore,

\[
\text{expr1}=l(i-1,j-1)+1
\]

and

\[
\text{expr2}=\max(l(i-1,j),\,l(i,j-1))
\]

Explanation:

If \(X[i-1]=Y[j-1]\), then the matching character contributes \(1\) to the LCS, so

\[
l(i,j)=l(i-1,j-1)+1.
\]

If \(X[i-1]\neq Y[j-1]\), then either \(X[i-1]\) or \(Y[j-1]\) must be excluded, and we take the better of the two possibilities:

\[
l(i,j)=\max(l(i-1,j),\,l(i,j-1)).
\]

Hence,

\[
\boxed{\text{expr1}=l(i-1,j-1)+1}
\]

\[
\boxed{\text{expr2}=\max(l(i-1,j),\,l(i,j-1))}
\]

Among the given options, only Option C correctly specifies \(\text{expr2}\).