1.1k 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.1k views

I suppose in Q 53. expr2 should have X[i-1]!=Y[j-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].

selected

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));
}
edited by
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 .

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

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 !
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 .
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