GATE CSE 2009 | GATE CSE Year Wise Previous Years Questions

PREVIOUS NEXT

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

Consider the following graph: GATE CSE 2009 Algorithms - Greedy Method Question 20 English

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?

(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)

(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)

(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)

(b,e)(e,f)(b,c)(a,c)(f,g)(c,d)

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]

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

All elements of L should be initialized to 0 for the values of l(i, j) to be properly computed.

The values of l(i,j) may be computed in a row major order or column major order of L[M, N].

The values of l(i, j) cannot be computed in either row major order or column major order of L[M, N].

L[p, q] needs to be computed before L[r, s] if either p < r or q < s.

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

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 2009

MCQ (Single Correct Answer)

-0.3

Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

There is no polynomial time algorithm for $${\pi _A}$$

If $${\pi _A}$$ can be solved deterministically in polynomial time, then P = NP

If $${\pi _A}$$ is NP-hard, then it is NP-complete.

$${\pi _A}$$ may be undecidable.

PREVIOUS NEXT

GATE CSE Papers

2023