GATE CSE 2006 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2006

MCQ (Single Correct Answer)

-0.3

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Solves it in linear time using a left to right pass of the array

Solves it in linear time using a right to left pass of the array

Solves it using divide and conquer in time $$\theta \left( {n\log n} \right)$$

Solves it in time $$\theta \left( {{n^2}} \right)$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Let SHAM₃ be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM₃ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Both DHAM₃ and SHAM₃ are NP-hard

SHAM₃ is NP-hard, but DHAM₃ is not

DHAM₃ is NP-hard, but SHAM₃ is not

Neither DHAM₃ nor SHAM₃ is NP-hard

GATE CSE 2006

MCQ (Single Correct Answer)

-0.3

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

R is NP-complete

R is NP-hard

Q is NP-complete

Q is NP-hard

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Consider the following graph: GATE CSE 2006 Algorithms - Greedy Method Question 29 English

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

$$(a-b),(d-f),(b-f),(d-c),(d-e)$$

$$(a-b),(d-f),(d-c),(b-f),(d-e)$$

$$(d-f),(a-b),(d-c),(b-f),(d-e)$$

$$(d-f),(a-b),(b-f),(d-e),(d-c)$$

PREVIOUS NEXT

GATE CSE Papers

2024