GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
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)$

asked in Algorithms by Veteran (64.6k points)  
edited by | 1.1k views

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

2 Answers

+16 votes
Best answer

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

answered by Veteran (43.8k points)  
selected by
+13 votes

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));
}
answered by Loyal (4k points)  
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 .
Sir, I've same doubt as asked by Radha Gogla ma'am. Could you please clarify it.
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


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2070 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,648 answers
79,695 comments
31,069 users