GATE CSE 2003 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?

Π is NP-hard but not NP-complete

Π is in NP, but is not NP-complete

Π is NP-complete

Π is neither NP-hard, nor in NP

GATE CSE 2003

MCQ (Single Correct Answer)

-0.6

What is the weight of a minimum spanning tree of the following graph? GATE CSE 2003 Algorithms - Greedy Method Question 10 English

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

Removing left recursion alone

Factoring the grammar alone

Removing left recursion and factoring the grammar

None of the above

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

always be evaluated

be evaluated only if the definition is L- attributed

be evaluated only if the definition has synthesized attributes

never be evaluated

PREVIOUS NEXT

GATE CSE Papers

2023