# GATE CSE 2006

 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:
 A 3 B 5 C 6 D 9
Engineering Mathematics   Linear Algebra
Question 1 Explanation:
 Question 2
Let X, Y, Z be sets of sizes x, y and z respectively. Let W=X$\times$Y and E be the set of all subsets of W. The number of functions from Z to E is
 A $Z^{2xy}$ B $Z*2^{xy}$ C $Z^{2x+y}$ D $2^{xyz}$
Discrete Mathematics   Set Theory
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?
 A It is not closed B 2 does not have an inverse C 3 does not have an inverse D 8 does not have an inverse
Discrete Mathematics   Group Theory
Question 3 Explanation:
 Question 4
A relation R is defined on ordered pairs of integers as follows:
(x,y)R(u,v) if x$\lt$u and y$\gt$v. Then R is
 A Neither a Partial Order nor an Equivalence Relation B A Partial Order but not a Total Order C A Total Order D An Equivalence Relation
Discrete Mathematics   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?
 A Ensure packets reach destination within that time B Discard packets that reach later than that time C Prevent packets from looping indefinitely D Limit the time for which a packet gets queued in intermediate routers
Computer Network   Network Layer Protocol
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
 A 1 B 2 C 3 D 4
Operating System   CPU Scheduling
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?
 A (i) and (ii) B (ii) and (iii) C (i) and (iii) D None of these
Compiler Design   Parsing
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 A B B C C D D
Digital Logic   Sequential Circuit
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)?
 A 400 B 500 C 600 D 700
Computer Organization   Machine Instruction
Question 9 Explanation:
 Question 10
In a binary max heap containing n numbers, the smallest element can be found in time
 A $\Theta (n)$ B $\Theta (logn)$ C $\Theta (log logn)$ D $\Theta (1)$
Data Structure   Heap Tree
Question 10 Explanation:
There are 10 questions to complete.