# GATE2009-54

5.3k 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$.

edited
13

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)

0
what will be the answer if option d is given as p<r and  q<s. ?
0

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

0
Here what does the option a say? Could any one tell me?

$\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
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;
0
in the last option here either or means xor or normal or?
0
Regular usage of OR obviously but truth values still holds during its usage.

$\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

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

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
1
I THINK IF INSTEAD OF (EITHER ,OR) BOTH ,AND  WOULD HAVE BEEN CORRECT

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.

## Related questions

1
3.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 ... $\text{expr2} = \max\left(l\left(i-1, j-1\right), l\left(i,j\right)\right)$
Consider the program below: #include <stdio.h> int fun(int n, int *f_p) { int t, f; if (n <= 1) { *f_p = 1; return 1; } t = fun(n-1, f_p); f = t + *f_p; *f_p = t; return f; } int main() { int x = 15; printf("%d/n", fun(5, &x)); return 0; } The value printed is: $6$ $8$ $14$ $15$
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm? $\text{(b, e) (e, f) (a, c) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (a, c) (f, g) (b, c) (c, d)}$ $\text{(b, e) (a, c) (e, f) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (b, c) (a, c) (f, g) (c, d)}$