The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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)$?

  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 (108k points)
edited by | 1.9k views

2 Answers

+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);
     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;
         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 (346k points)
edited by




Problem with tracing code.

When i=j=0.

and i=0 and j=1

Plz Help Me here _/\_

Here L[i-1][j] is for row major order, and L[i][j-1] for column major order
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++)


sir not able to understand options [email protected] arjun sir
what will be expr1?
+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

answered by Veteran (49.5k points)
Can you elaborate on last paragraph of the answer.
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 ...
i understood the answer , but can someone pls explain what is option A trying to say ?
someone explain why row and colomn order same?wht option d meaning ?

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

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

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

33,721 questions
40,265 answers
38,904 users