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

**Answer : ****Option B**

**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.

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

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.

**Answer : ****Option C**

**Explaination / Solution: **

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

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

Workspace

Report

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

**Answer : ****Option C**

**Explaination / Solution: **

2^{ε*} is the power set of ε *

2

ε * is countabily infinite.

The power set of countabily infinite set is uncountable.

So 2^{ε*} is uncountable, and ε * is countable

Workspace

Report

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.

**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.

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

Consider the following languages over the alphabet Σ = {0,1,c}

For the languages L

Workspace

Report

Let A be a square matrix size n × n. Consider the following pseudocode. What is the
expected output?

**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

**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.

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 ]);

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

Consider the following rooted tree with the vertex labelled P as the root

**A. ** SQPTRWUV

**B. ** SQPTUWRV

**C. ** SQPTWUVR

**D. ** SQPTRUWV

**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.

The order in which the nodes are visited during an in-order traversal of the tree is

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

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(n^{2})

**B. ** O(n log n)
**C. ** θ(n log n)

**D. ** θ(n2)

**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.

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

Consider the basic block given below.

**A. ** 6 and 6

**B. ** 8 and 10

**C. ** 9 and 12

**D. ** 4 and 4

**Answer : ****Option A**

**Explaination / Solution: **

The given basic block can be rewritten as

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

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

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.

**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.

**Answer : ****Option D**

**Explaination / Solution: **

The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time. Here, that condition is if (tree→leftMostchild == Null) ⇒ Which means if there is no left most child of the tree (or the sub-tree or the current nodeas called in recursion) ⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all). ⇒ Which means the node under consideration is a leaf node. ⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered. ⇒ The function returns the number of leaf nodes in the tree.

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

The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time. Here, that condition is if (tree→leftMostchild == Null) ⇒ Which means if there is no left most child of the tree (or the sub-tree or the current nodeas called in recursion) ⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all). ⇒ Which means the node under consideration is a leaf node. ⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered. ⇒ The function returns the number of leaf nodes in the tree.

Workspace

Report