The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 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)$?

- All elements of $L$ should be initialized to 0 for the values of $l(i, j)$ to be properly computed.
- The values of $l(i, j)$ may be computed in a row major order or column major order of $L[M, N]$.
- The values of $l(i, j)$ cannot be computed in either row major order or column major order of $L[M, N]$.
- $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.

+24 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]; }

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 _/\_

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 [email protected] arjun sir

+19 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**

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

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

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 285
- Exam Queries 398
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,721 questions

40,265 answers

114,393 comments

38,904 users