GATE CSE 2009 | Dynamic Programming Question 13 | Algorithms

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

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]

Which one of the following options is correct?

expr1 = l(i − 1, j) + 1

expr1 = l(i, j − 1)

expr2 = max( l(i − 1, j), l(i, j − 1))

expr2 = max( l(i − 1,j − 1),l (i, j))

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁ ,a₂ ,a₃ ,…,a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a₁ ,a₂ ,…,a_i} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

X[1, W]

X[n, 0]

X[n, W]

X[n-1, n]

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁ ,a₂ ,a₃ ,…,a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a₁ ,a₂ ,…,a_i} whose elements sum to j.
Which of the following is valid for 2 <= i <= n and ai <= j <= W?

X[i, j] = X[i – 1, j] V X[i, j -a_i]

X[i, j] = X[i – 1, j] V X[i – 1, j – a_i]

X[i, j] = X[i – 1, j] V X[i, j – a_i]

X[i, j] = X[i – 1, j] V X[i -1, j – a_i]

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.

1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10.  }

On which of the following contents of Y and x does the program fail?

Y is [1 2 3 4 5 6 7 8 9 10] and x < 10

Y is [1 3 5 7 9 11 13 15 17 19] and x < 1

Y is [2 2 2 2 2 2 2 2 2 2] and x > 2

Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

PREVIOUS NEXT