1.9k views

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?

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

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

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

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

edited | 1.9k views
+2

I suppose in Q 53. expr2 should have X[i-1]!=Y[j-1].

0

## max(l(i-1,j) , l(i,j-1)) +1 ?

0
I think it must be l(i-1, j-1) +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));
}
selected
0
Sir for Q 54 both B and D should be correct . after you fill 0 in the first row and first coloum . for second one we can calculate either row wise or column wise .
+2

@Arjun
Question 54

B is correct : changing from row-major order to column-major order is equivalent to exchanging X and Y while keeping the order same.
D is incorrect : For example, assuming row-major order, you don't need to calculate L[1,3] before calculating L[2,2]. (p=1 q=3 r=2 s=2).

+1
Yes. D seems incorrect . Assuming that we want to compute L(3,3). We need not compute L(4,2) if we are using Row Major Order ! Here L(4,2) = L[p,q] & L(3,3) = L[r,s]. Then q<s still we need not compute it !
+5
In this question shouldn't expression 1 be 1+c[i-2,j-2] since we are starting arrays from indices 0 to m-1,and in general scenario we do 1+c[i-1,j-1] when we have arrays starting from indices 1 to m .
0
+1
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

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 ]$.

edited by

Answer is C ... Here is the video

edited

1
2