GATE CSE 2006 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2006

MCQ (Single Correct Answer)

-0.3

Consider the following C-program fragment in which i, j and n are integer variables.
for (i = n, j = 0; i > 0; i /= 2, j += i);
let val (j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

val (j) = $$\theta $$ (log n)

val (j) = ($$\sqrt n $$)

val (j) = $$\theta $$ (n)

val (j) = $$\theta $$ (n log n)

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 Papers

2024