1
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?
A
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
B
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
C
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
D
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
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 = {a1 ,a2 ,a3 ,…,an} 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 {a1 ,a2 ,…,ai} whose elements sum to j.
Which of the following is valid for 2 <= i <= n and ai <= j <= W?
A
X[i, j] = X[i – 1, j] V X[i, j -ai]
B
X[i, j] = X[i – 1, j] V X[i – 1, j – ai]
C
X[i, j] = X[i – 1, j] V X[i, j – ai]
D
X[i, j] = X[i – 1, j] V X[i -1, j – ai]
3
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 = {a1 ,a2 ,a3 ,…,an} 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 {a1 ,a2 ,…,ai} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
A
X[1, W]
B
X[n, 0]
C
X[n, W]
D
X[n-1, n]
4
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
GATE CSE 2008 Algorithms - Greedy Method Question 25 English Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
A
only vertex a
B
only vertices a,e,f,g,h
C
only vertices a,b,c,d
D
all the vertices
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12