The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
2.4k 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 (101k points)
edited by | 2.4k views
0

The reason why option d) is FALSE as given below - 

Say you're calculating the value of L(r,s) as L(2,3) which means r = 2 and s = 3 in ROW MAJOR ORDER . Now, the value L(p,q) say L(3,1) which means p =3 and q = 1 and as per given conditions, p<r i.e 3<2 (which is false), but since there's an OR and q<s ie (1<3) is True! 

Hence one of the condition is True, but to solve L (2,3) there's no need to solve L(3,1) if you're following Row Major Order.  Hence, FALSE!

To compute L(2,3) you only need L (1,3), L(2,2), L(1,2)

2 Answers

+27 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];
}
answered by Veteran (358k points)
edited by
0
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 _/\_
0

@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?

0
sir not able to understand options [email protected] arjun sir
0
what will be expr1?
0
Exp1 : l(i-1,j-1)+1;
+23 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 Boss (42.8k points)
0
Can you elaborate on last paragraph of the answer.
0
i think option D should also be correct  because to compute l[3,3] we need L[2,3]  or L[3,2] or L[2,2].
+3
he wrote wrong condition , in question its p<r, or q<s,

now he is trying to say , if i want to value of l[3,3] means l[r,s] , then it needs to compute , l[p,s] means l[2,3], l[2,2], l[3,2] for these no problem but ,l[4,2](q,s) which satisfied condition but it will compute after l[33] in row major oder ,,

thats why d is false ...
0
i understood the answer , but can someone pls explain what is option A trying to say ?
0
someone explain why row and colomn order same?wht option d meaning ?
+1
@Shaurya

option A is nothing but when u make a table to find out LCS, u will never initialize all the slots of the table to be 0.U will 0 only in the first row and first column...That's why this option is false
+1
@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
0
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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,776 questions
46,778 answers
140,741 comments
58,647 users