1

GATE CSE 2008

MCQ (Single Correct Answer)

+2

-0.6

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a

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

_{1},a_{2},a_{3},…,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_{1},a_{2},…,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?

2

GATE CSE 2008

MCQ (Single Correct Answer)

+2

-0.6

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a

Which of the following is valid for 2 <= i <= n and ai <= j <= W?

_{1},a_{2},a_{3},…,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_{1},a_{2},…,a_{i}} whose elements sum to j.Which of the following is valid for 2 <= i <= n and ai <= j <= W?

3

GATE CSE 2008

MCQ (Single Correct Answer)

+2

-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?4

GATE CSE 2008

MCQ (Single Correct Answer)

+2

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

The correction needed in the program to make it work properly is Questions Asked from Dynamic Programming (Marks 2)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages