GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
742 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]
The value of $l(i,j)$ could be obtained by dynamic programming based on the correct recursive definition of $l(i,j)$ of the form given above, using an array $L[M,N]$, where $M = m+1$ and $N = n+1$, such that $L[i, j] = l(i, j)$.

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of $l(i, j)$?

  1. All elements of $L$ should be initialized to 0 for the values of $l(i, j)$ to be properly computed.
  2. The values of $l(i, j)$ may be computed in a row major order or column major order of $L[M, N]$.
  3. The values of $l(i, j)$ cannot be computed in either row major order or column major order of $L[M, N]$.
  4. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.
asked in Algorithms by Veteran (76.2k points)   | 742 views

2 Answers

+8 votes
Best answer

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

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));
}

54. Answer is B. Dynamic programming is used to save the previously found LCS. So, for any index [p,q] all smaller ones should have been computed earlier. Option D is not correct as the condition given requires even L[3,2] to be computed before L[2,4] which is not a necessity if we follow row-major order. 

int lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
  
   /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
  
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
  
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
    
   /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
   return L[m][n];
}

 

answered by Veteran (283k points)  
selected by
Q.54

Suppose

X=abcba

Y=bcaba

Problem with tracing code.

When i=j=0.

and i=0 and j=1

Plz Help Me here _/\_

@Rajesh
Here L[i-1][j] is for row major order, and L[i][j-1] for column major order
X=abcba
Y=bcaba
i=0,j=0 will be matching  a $\neq$ b[a from 1st string, b from 2nd string]
 i=0 and j=1be a$\neq$c
 
but here the code will be
 

for (i=0; i<=m; i++)
   {
     for (j=i; j<=n; j++)
     {


na?

sir not able to understand options D@ arjun sir
+12 votes

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

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

Answer is B. We can either use Row Major or column major order.

Issue of option D -> Read option D carefully.

L[p,q] needs to be computed before L[r,s] if either p < q or r < s

 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 ! so D IS FALSE

answered by Veteran (41.3k points)  


Top Users Apr 2017
  1. akash.dinkar12

    3508 Points

  2. Divya Bharti

    2542 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,040 answers
63,230 comments
24,135 users