in Algorithms edited by
14,187 views
46 votes
46 votes

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$.
in Algorithms edited by
14.2k views

4 Comments

@Bipin Jaiswal if there would have AND then condition will be p<=r and q<=s.

1
1
Here what does the option a say? Could any one tell me?
0
0
@ tusharp p <= r and q <= s implies that L[r,s] needs to be computed before L[r,s], which is not true.

i guess, (p<=r and q<s) or (p<r and q<=s) should be correct.
0
0

3 Answers

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

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

4 Comments

in the last option here either or means xor or normal or?
0
0
Regular usage of OR obviously but truth values still holds during its usage.
0
0

To compute l(i,j) in column major order, we can just swap the two for loops (i.e. first j loop will come and then the i loop nested inside it) and we will get same output.

0
0
38 votes
38 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

4 Comments

@Gateset2018

Bro whenever u try to fill the table to find LCS, either u can go row-wise or column wise.

option D meaning is already well explained by above answer
1
1
Yes it is necessary to  compute the L(2,2) we need to have L(1,1), L(1,2) and L(2,1) but it is not at all necessary that we need to compute L(4,1) in prior as it also satisfies the given constraints
0
0
I THINK IF INSTEAD OF (EITHER ,OR) BOTH ,AND  WOULD HAVE BEEN CORRECT
2
2
1 vote
1 vote

expr2=max(l(i−1,j),l(i,j−1))expr2=max(l(i−1,j),l(i,j−1))

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.

Here main confusion is from option D

But if you read carefully you can see that it is talking about either case i.e p<r or q<s that's why option is not CORRECT.

But if there is AND case in option D  then option is also right.

 

1 comment

The last line in the answer is so underrated in this discussion, yet so important to understand why. Great job pointing it out.
0
0
Answer:

Related questions