1
GATE CSE 2014 Set 3
+1
-0.3
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
A
O(n2)
B
O(n log n)
C
$$\Theta (n \log n)$$
D
O(n3)
2
GATE CSE 2014 Set 3
+2
-0.6
Consider the decision problem 2CNFSAT defined as follows:

{ $$\Phi$$ | $$\Phi$$ is a satisfiable propositional formula in CNF with at most two literal per clause}

For example, $$\Phi = \left( {{x_1} \vee {x_2}} \right) \wedge \left( {{x_1} \vee {{\overline x }_3}} \right) \wedge \left( {{x_2} \vee {x_4}} \right)$$ is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

A
NP-Complete.
B
Solvable in polynomial time by reduction to directed graph reachability.
C
Solvable in constant time since any input instance is satisfiable.
D
NP-Hard, but not NP-complete.
3
GATE CSE 2014 Set 3
+1
-0.3
One of the purposes of using intermediate code in compilers is to
A
make parsing and semantic analysis simpler.
B
improve error recovery and error reporting.
C
increase the chances of reusing the machine-independent code optimizer in other compilers.
D
improve the register allocation.
4
GATE CSE 2014 Set 3
+2
-0.6

Consider the basic block given below.

a = b + c
c = a + d
d = b + c
e = d - b
a = e + b

The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

A
6 and 6
B
8 and 10
C
9 and 12
D
4 and 4
GATE CSE Papers
2023
2022
2020
2019
2018
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Medical
NEET