A sub-sequence of a given sequence is just the given sequence with some… — GATE CS 2009 Q54

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

View worked solution

Answer: B

To find the correct statement, let us analyze the recurrence relation for the Longest Common Subsequence (LCS) problem:

l(i, j) = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ l(i-1, j-1) + 1 & \text{if } X[i-1] = Y[j-1] \\ \max(l(i-1, j), l(i, j-1)) & \text{if } X[i-1] \neq Y[j-1] \end{cases}

Dependency Analysis

To compute the value of $L[i, j]$ , we require the values of:

$L[i-1, j-1]$ (top-left diagonal neighbor)
$L[i-1, j]$ (top neighbor)
$L[i, j-1]$ (left neighbor)

This means any evaluation order must ensure that these three cells are computed before $L[i, j]$ .

Row-Major Order: We fill the table row by row (from top to bottom, left to right). When computing $L[i, j]$ , the previous row ( $i-1$ ) and the left element in the current row ( $j-1$ ) are already computed. Thus, this is a valid evaluation order.
Column-Major Order: We fill the table column by column (from left to right, top to bottom). When computing $L[i, j]$ , the previous column ( $j-1$ ) and the top element in the current column ( $i-1$ ) are already computed. Thus, this is also a valid evaluation order.

Hence, statement B is TRUE.

Elimination of Other Options

Option A: Only the base cases (the first row $i=0$ and the first column $j=0$ ) must be initialized to $0$ . The remaining cells are computed and overwritten, so initializing the entire array to $0$ is not necessary.
Option C: Incorrect, as both row-major and column-major orders are valid.
Option D: This is too restrictive. For example, let $p=1, q=5$ and $r=2, s=1$ . Here, $p < r$ , but $L[2, 1]$ only depends on $L[1, 0]$ , $L[1, 1]$ , and $L[2, 0]$ . It does not depend on $L[1, 5]$ , so $L[1, 5]$ does not need to be computed before $L[2, 1]$ .

Free practice · Your answers on this page are not saved.

GATE CS 2009 Q54 — Algorithm Design: Dynamic Programming

Dependency Analysis

Elimination of Other Options

Related questions