1
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-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?
A
val (j) = $$\theta $$ (log n)
B
val (j) = ($$\sqrt n $$)
C
val (j) = $$\theta $$ (n)
D
val (j) = $$\theta $$ (n log n)
2
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-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
A
Solves it in linear time using a left to right pass of the array
B
Solves it in linear time using a right to left pass of the array
C
Solves it using divide and conquer in time $$\theta \left( {n\log n} \right)$$
D
Solves it in time $$\theta \left( {{n^2}} \right)$$
3
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
A
Both DHAM3 and SHAM3 are NP-hard
B
SHAM3 is NP-hard, but DHAM3 is not
C
DHAM3 is NP-hard, but SHAM3 is not
D
Neither DHAM3 nor SHAM3 is NP-hard
4
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-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?
A
R is NP-complete
B
R is NP-hard
C
Q is NP-complete
D
Q is NP-hard
EXAM MAP