GATE-CS-2006

Consider the polynomial p(x) = a0 + a1x + a2x² + a3x³ , where ai ≠ 0 ∀i. The minimum number of multiplications needed to evaluate p on an input x is:

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

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?

A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is:

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

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 shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

Consider the following grammar.

S -> S * E
S -> E
E -> F + E
E -> F
F -> id

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

(i) S -> S * .E
(ii) E -> F. + E
(iii) E -> 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?

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°? 

[caption width="800"] [/caption][caption width="800"] [/caption]

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)?

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