The Gateway to Computer Science Excellence
+34 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 by Veteran (105k points)
edited by | 4.2k views

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)

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

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

2 Answers

+35 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];
by Veteran (431k 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?
Exp1 : l(i-1,j-1)+1;
in the last option here either or means xor or normal or?
Regular usage of OR obviously but truth values still holds during its usage.
+34 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

by Boss (41.9k 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
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

Related questions

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
50,737 questions
57,385 answers
105,369 users