GATE CSE 2005 | GATE CSE Year Wise Previous Years Questions

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 2005

MCQ (Single Correct Answer)

-0.6

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all these elements is :
(Hint : Use a heap data structure)

$$O(n \log \log n)$$

$$\Theta(n \log n)$$

$$\Omega(n \log n)$$

$$\Omega\left(n^{3/2}\right)$$

PREVIOUS NEXT

GATE CSE Papers

2024