Question 1 |

Consider the polynomial p(x)=a_{0}+a_{1}x+a_{2}x^{2} + a_{3}x^{3}, where a_{i}\neq 0,\forall i. The minimum number of multiplications needed to evaluate p on an input x is:

3 | |

5 | |

6 | |

9 |

Question 1 Explanation:

Question 2 |

Let X, Y, Z be sets of sizes x, y and z respectively. Let W=X\timesY and E be the
set of all subsets of W. The number of functions from Z to E is

Z^{2xy} | |

Z*2^{xy} | |

Z^{2x+y} | |

2^{xyz} |

Question 2 Explanation:

Question 3 |

The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false?

It is not closed | |

2 does not have an inverse | |

3 does not have an inverse | |

8 does not have an inverse |

Question 3 Explanation:

Question 4 |

A relation R is defined on ordered pairs of integers as follows:

(x,y)R(u,v) if x\ltu and y\gtv. Then R is

(x,y)R(u,v) if x\ltu and y\gtv. Then R is

Neither a Partial Order nor an Equivalence Relation | |

A Partial Order but not a Total Order | |

A Total Order | |

An Equivalence Relation |

Question 4 Explanation:

Question 5 |

For which one of the following reason does Internet Protocol (IP) use the timeto-live (TTL) field in the IP datagram header?

Ensure packets reach destination within that time | |

Discard packets that reach later than that time | |

Prevent packets from looping indefinitely | |

Limit the time for which a packet gets queued in intermediate routers |

Question 5 Explanation:

Question 6 |

Consider three CPU-intensive processes, which require 10,20 and 30 time units
and arrive at times 0,2, and 6, respectively. How many context switches are needed
if the operating system implements a shortes remaining time first scheduling
algorithm? Do not count the context switches at time zero and at the end

1 | |

2 | |

3 | |

4 |

Question 6 Explanation:

Question 7 |

Consider the following grammar.

S \rightarrow S * E

S \rightarrow E

E \rightarrow F + E

E \rightarrow F

F F \rightarrow id

Consider the following LR(0) items corresponding to the grammar above.

(i) S \rightarrow S * .E

(ii) E \rightarrow F. + E

(iii) E \rightarrow F + .E

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

S \rightarrow S * E

S \rightarrow E

E \rightarrow F + E

E \rightarrow F

F F \rightarrow id

Consider the following LR(0) items corresponding to the grammar above.

(i) S \rightarrow S * .E

(ii) E \rightarrow F. + E

(iii) E \rightarrow F + .E

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

(i) and (ii) | |

(ii) and (iii) | |

(i) and (iii) | |

None of these |

Question 7 Explanation:

Question 8 |

You are given a free running clock with a duty cycle of 50% and a digital waveform
f which changes only at the negative edge of the clock. Which one of the following
circuits (using clocked D flip flops) will delay the phase of f by 180^{\circ} ?

A | |

B | |

C | |

D |

Question 8 Explanation:

Question 9 |

A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?

400 | |

500 | |

600 | |

700 |

Question 9 Explanation:

Question 10 |

In a binary max heap containing n numbers, the smallest element can be found in time

\Theta (n) | |

\Theta (logn) | |

\Theta (log logn) | |

\Theta (1) |

Question 10 Explanation:

There are 10 questions to complete.