# CS GATE 2014 PAPER 03 (Test 3)

Tag: cs gate 2014 paper 03
Q.1
In the context of modular software design, which one of the following combinations is desirable?
A. High cohesion and high coupling
B. High cohesion and low coupling
C. Low cohesion and high coupling
D. Low cohesion and low coupling
Explaination / Solution:

Cohesion is a measure of internal strength within a module, whereas coupling is a measure of inter dependency among the modules. So in the context of modular software design there should be high cohesion and low coupling.

Workspace
Report
Q.2
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 compliers.
D. improve the register allocation.
Explaination / Solution:

Intermediate code is machine independent code which makes it easy to retarget the compiler to generate code for newer and different processors.

Workspace
Report
Q.3
Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ* . Which one of the following is TRUE?
A. Both 2Σ* and Σ * are countable
B. 2Σ* is countable Σ * is uncountable
C. 2Σ* is uncountable and Σ * is countable
D. Both 2Σ* and Σ * are uncountable
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

Workspace
Report
Q.4
Which one of the following problems is undecidable?
A. Deciding if a given context-free grammar is ambiguous.
B. Deciding if a given string is generated by a given context-free grammar.
C. Deciding if the language generated by a given context-free grammar is empty.
D. Deciding if the language generated by a given context-free grammar is finite.
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.

Workspace
Report
Q.5
Consider the following languages over the alphabet Σ = {0,1,c} Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree languages?
A. None of the languages
B. Only L1
C. Only L1 and L2
D. All the three languages
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.

Workspace
Report
Q.6
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 ]);
A. The matrix A itself
B. Transpose of the matrix A
C. Adding 100 to the upper diagonal elements and subtracting 100 from lower diagonal elements of A
D. None of these
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.

Workspace
Report
Q.7
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
A. SQPTRWUV
B. SQPTUWRV
C. SQPTWUVR
D. SQPTRUWV
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.

Workspace
Report
Q.8
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
A. O(n2)
B. O(n log n)
C. θ(n log n)
D. θ(n2)
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.

Workspace
Report
Q.9
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
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)

Workspace
Report
Q.10
Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
Struct treeNode
{
Treeptr leftMostchild, rightSibiling;
};
Int Dosomething (treeptr tree)
{
int value =0;
if (tree ! = NULL) {
If (tree -> leftMostchild = = NULL)
else
value = Dosomething (tree->leftMostchild);
value = value + Dosometing (tree->rightsibiling);
}
return (value);
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
A. number of internal nodes in the tree.
B. height of the tree.
C. number of nodes without a right sibling in the tree.
D. number of leaf nodes in the tree.