CS GATE 2014 PAPER 03 - Online Test
Q1. Consider the relational schema given below, where eId of the relation dependentis a foreign
key referring to empId of the relation employee. Assume that every employee has at least one
associated dependent in the dependent relation.
employee (empId, empName, empAge)
dependent (depId, eId, depName, depAge)
Consider the following relational algebra query
The above query evaluates to the set of empIds of employees whose age is greater than that of
Answer : Option D
Explaination / Solution:
Part A of the above given relational algebra query will give the set of empIds of those
employees whose age is less than or equal to the age of some of his/her dependents.
Now when set of empIds of all employees minus set of empIds obtained from part A is done,
then we get the set of empIds of employees whose age is greater than that of all of his/her
dependents.
Q2. Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ* . Which one of the following is TRUE?
Answer : Option C
Explaination / Solution:
2ε* is the power set of ε *
ε * is countabily infinite.
The power set of countabily infinite set is uncountable.
So 2ε* is uncountable, and ε * is countable
Q3. Consider the decision problem 2CNFSAT defined as follows:
{ φ | φ is a satisfiable propositional formula in CNF with at most two literal per clause}
For example, 
is a Boolean formula and it is in 2CNFSAT.
is a Boolean formula and it is in 2CNFSAT.The decision problem 2CNFSAT is
Answer : Option B
Explaination / Solution:
2 SAT is in P. This we can prove by reducing 2 SAT to directed graph reachability problem
which is known to be in P.
Procedure for reducing 2 SAT to reachability problem:
1. Let ϕ be CNF with clauses of length 2 and let P be the set of propositional
variables(literals) in ϕ
2. Build a graph G=(V,E) with V= P { p|p P} ∪ ¬ ∈ and (x, y E )∈ iff there is a clause in ϕ
that is equivalent to x y → (all the clauses are converted to equivalent implications and
the graph built is called as implication graph)
3. Observe that ϕ is unsatisfiable iff there is a p P ∈ such that there is both a path from p to
to ¬p and from ¬p to p in G.
This condition can be tested by running the reachability algorithm several times.
Q4. Which one of the following problems is undecidable?
Answer : Option A
Explaination / Solution:
There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness
of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG,
so it is undecidable.
Q5. 
Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree
languages?
Consider the following languages over the alphabet Σ = {0,1,c}
Answer : Option C
Explaination / Solution:
For the languages L1 and L2 we can have deterministic push down automata, so they are
DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3 is not a
deterministic CFL.
Q6. If she _______________ how to calibrate the instrument, she _______________ done the
experiment.
Answer : Option C
Explaination / Solution:
No Explaination.
Q7. Let A be a square matrix size n × n. Consider the following pseudocode. What is the
expected output?
C = 100;
for i = 1 to n do
for j = 1 to n do
{
Temp = A[ i ] [ j ] + C ;
A [ i ] [ j ] = A [ j ] [ i ] ;
A [ j ] [ i ] = Temp – C ;
}
for i = 1 to n do
for j = 1 to n do
output (A[ i ] [ j ]);
Answer : Option A
Explaination / Solution:
In the computation of given pseudo code for each row and column of Matrix A, each upper
triangular element will be interchanged by its mirror image in the lower triangular and after
that the same lower triangular element will be again re-interchanged by its mirror image in
the upper triangular, resulting the final computed Matrix A same as input Matrix A.
Q8. Consider the following rooted tree with the vertex labelled P as the root
The order in which the nodes are visited during an in-order traversal of the tree is
Answer : Option A
Explaination / Solution:
The In order Traversal of Ternary Tree is done as follows:
Left → Root → Middle → Right
So the nodes are visited in SQPTRWUV order.
Q9. You have an array of n elements. Suppose you implement quick sort by always choosing the
central element of the array as the pivot. Then the tightest upper bound for the worst case
performance is
Answer : Option A
Explaination / Solution:
The Worst case time complexity of quick sort is O(n2). This will happen when the elements
of the input array are already in order (ascending or descending), irrespective of position of
pivot element in array.
Q10. 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
Answer : Option A
Explaination / Solution:
The given basic block can be rewritten as
From above simplification it is visible that e is same as c and final value of a is same as d. So
the final basic block can be written as follows:
The DAG generated for the above basic block in as
Maximum number of modes and edges in above DAG is (6,6)
