ExamSIDE.Com

GATE CSE 1991 Question

Obtain the optimal binary search tree with equal probabilities for the identifier set (a1, a2, a3) = ( if, stop, while)

GATE CSE 1996 Question

A binary search tree is generated by inserting in order the following integers:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is
A
(4, 7)
B
(7, 4)
C
(8, 3)
D
(3, 8)

GATE CSE 2008 Question

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]