G = (V, E ) is an undirected simple graph in which each edge has a distinct weight, and e is a
particular edge of G. Which of the following statements about the minimum spanning trees
(MSTs) of G is/are TRUE? **A. ** I only

**B. ** II only

**C. ** both I and II

**D. ** neither I nor II

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

**Explaination / Solution: **

No Explaination.

I. If e is the lightest edge of some cycle in G, then every MST of G includes e

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

No Explaination.

Workspace

Report

Let X be a recursive language and Y be a recursively enumerable but not recursive language.
Let W and Z be two languages such that Y reduces to W , and Z reduces to X (reduction
means the standard many-one reduction). Which one of the following statements is TRUE?

**A. ** W can be recursively enumerable and Z is recursive.

**B. ** W can be recursive and Z is recursively enumerable.

**C. ** W is not recursively enumerable and Z is recursive.

**D. ** W is not recursively enumerable and Z is not recursive.

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S,
A} and terminals {a, b}.

**A. ** 1 3 2

**B. ** 2 2 3

**C. ** 2 3 1

**D. ** syntax error

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

**Explaination / Solution: **

S → aA {print 1}

S → a {print 2}

A → Sb {print 3}

Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:

Workspace

Report

Consider the following proposed solution for the critical section problem. There are n
processes: P_{0}. . . P_{n-1}. In the code, function pmax returns an integer not smaller than any of
its arguments. For all i, t[i] is initialized to zero.

**A. ** At most one process can be in the critical section at any time

**B. ** The bounded wait condition is satisfied

**C. ** The progress condition is satisfied

**D. ** It cannot cause a deadlock

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

**Explaination / Solution: **

No Explaination.

Code for Pi:

do {

c[i]=1; t[i] = pmax(t[0],. . .,t[n-1])+1; c[i]=0;

for every j = i in {0,. . .,n-1} {

while (c[j]);

while (t[j] != 0 && t[j]<=t[i]);

}

Critical Section;

t[i]=0;

Remainder Section;

} while (true);

Which one of the following is TRUE about the above solution?

No Explaination.

Workspace

Report

Consider a carry look ahead adder for adding two n-bit integers, built using gates of fan-in at
most two. The time to perform addition using this adder is

**A. ** Θ(1)

**B. ** Θ(log(n))

**C. ** Θ(√n)

**D. ** Θ(n)

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Consider the Boolean operator # with the following properties:

**A. **

**B. **

**C. **

**D. **

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

**Explaination / Solution: **

No Explaination.

Then x # y is equivalent to

No Explaination.

Workspace

Report

Consider the two cascaded 2-to-1 multiplexers as shown in the figure.

**A. **

**B. **

**C. **

**D. **

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

**Explaination / Solution: **

The minimal sum of products form of the output X is

Workspace

Report

A shaving set company sells 4 different types of razors, Elegance, Smooth, Soft and
Executive.

**A. ** Elegance

**B. ** Executive

**C. ** Smooth

**D. ** Soft

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

**Explaination / Solution: **

Total income from Elegance=48(27300+25222+28976+21012) = 4920480 Total income from Smooth=63(20009+19392+22429+18229 = 5043717 Total income from Soft=78(17602+18445+19544+16595) =5630508 Total income from Executive=173(9999+8942+10234+10109) =6796132

Elegance sells at Rs. 48, Smooth at Rs. 63, Soft at Rs. 78 and Executive at Rs. 173 per piece.
The table below shows the numbers of each razor sold in each quarter of a year.

Which product contributes the greatest fraction to the revenue of the company in that year?

Total income from Elegance=48(27300+25222+28976+21012) = 4920480 Total income from Smooth=63(20009+19392+22429+18229 = 5043717 Total income from Soft=78(17602+18445+19544+16595) =5630508 Total income from Executive=173(9999+8942+10234+10109) =6796132

Workspace

Report

Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of
the following is the recurrence relation for a_{n}?

**A. ** an = an-1 - 2an-2

**B. ** an = an-1 + 2an-2

**C. ** an = an+1 + 2an-2

**D. ** an = an-1 + 2an+2

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

**Explaination / Solution: **

Workspace

Report