GATE CSE 2005 | GATE CSE Year Wise Previous Years Questions

GATE CSE

GATE CSE 2005

MCQ (Single Correct Answer)

-0.3

The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:

O (n)

O (n log n)

O (n^3/2)

O (n³)

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

P₃ is decidable if P₁ is reducible to P₃

P₃ is undecidable if P₃ is reducible to P₂

P₃ is undecidable if P₂ is reducible to P₃

P₃ is decidable if P₃ is reducible to P₂ 's complement

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?

T(n) = O(n²)

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \left( {n{\rm{ }}\,log\,{\rm{ }}n} \right)$$

$$T\left( n \right){\rm{ }} = {\rm{ }}\Omega ({n^2})$$

T(n) = O(n log n)

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

$$O\left( {{{\left| V \right|}^2}} \right)$$

$$O\left(|E|+|V|\log |V|\right)$$

$$O\left(|V|\log|V|\right)$$

$$O\left(\left(|E|+|V|\right)\log|V|\right)$$

GATE CSE Papers

2024