1
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source.
GATE CSE 2004 Algorithms - Greedy Method Question 26 English In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?
A
$$P,Q,R,S,T,U$$
B
$$P,Q,R,U,S,T$$
C
$$P,Q,R,U,T,S$$
D
$$P,Q,T,R,U,S$$
2
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of
A
n
B
n2
C
n log n
D
$$n \log^2n$$
3
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
The problems 3-SAT and 2-SAT are
A
both in P
B
both NP-complete
C
NP-complete and in P respectively
D
undecidable and NP-complete respectively
4
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6

Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r, s, t are terminals.

$$\eqalign{ & 1.\,P \to QR \cr & 2.\,P \to QsR \cr & 3.\,P \to \varepsilon \cr & 4.\,P \to QtRr \cr} $$
A
1 only
B
1 and 3 only
C
2 and 3 only
D
3 and 4 only
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12