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.