# (Paper) GATE: Computer Science (CS) Question Paper Year 2006 (2)

26. Which one of the first order predicate calculus statements given below
correctly expresses the following English statement? Tigers and lions attack if
they are hungry or threatened.

(A) vx[(tiger(x) A lion(x)) — {(hungry(x) v threatened(x)) — attacks(x))1

(B) Vx [(tiger (x) v lion (x)) — {(hungry (x) v threatened (x)) A attacks (x)j

(C) Vx[(tiger(x) v lion(x)) — {attacks(x) — (hungry(x) v threatened(x)))1

(D) vx[(tiger(x) v lion(x)) — {(hungry(x) v threatened(x)) — attacks(x))1

27. Consider the following propositional statements:

Pl:((AAB)C))((AC)A(BC))

P2:((AvB)C))((A—C)v(B_C))

Which one of the following is true?

(A) P1 is a tautology, but not P2

(B) P2 is a tautology, but not P1

(C) P1 and P2 are both tautologies

(D) Both P1 and P2 are not tautologies

28. A logical binary relation a, is defined as follows:

Let be the unary negation (NOT) operator, with higher precedence then o. Which
one of the following is equivalent to A A B?

(A) ('-'.'AOB)

(B) -'.'(AO'-..'B)

(C) ".'(".'Ao".'B)

(D) AOB)

29. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0's
in s and n1 (s)the number of l's in s. Which one of the following languages is
not regular?

(A) L = {s (0 + 1)*n0 (s) is a 3-digit prime

(B) L = {s E (0 + 1)* for every prefix s' of s, fl0 (s') — n1 (s') 2}

(C) L={sE(0+1)*n0(s)_n1(s)4}

(D) L = {s E (0 + 1) j n0 (s) mod 7 = n1 (s) mod 5 = 0)

30. For SE (0+1)*let d(s)denote the decimal value of s(e.g.d(101)= 5). Let L
= {s E (0 + 1) j d (s) mod 5 = 2 and d (s) mod 7 = 4) Which one of the following
statements is true?

(A) L is recursively enumerable, but not recursive

(B) L is recursive, but not context-free

(C) L is context-free, but not regular

(D) L is regular

31. Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

A B AoB

True True True

True False True

False True False

False False True

(A) Both DHAM3 and SHAM3 are NP-hard

(B) SHAM3 is NP-hard, but DHAM3 is not

(C) DHAM3 is NP-hard, but SHAM3 is not

(D) Neither DHAM3 nor SHAM3 is NP-hard

32. Consider the following statements about the context free grammar G = {S -
SS, S - ab, S- ba, S -}

I. G is ambiguous

II. G produces all strings with equal number of a's and b's

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?

(A) I only

(B) I and III only

(C) II and III only

(D) I, II and III

33. Let L1 be a regular language, L2 be a deterministic context-free language
and L3 a recursively enumerable, but not recursive, language. Which one of the
following statements is false?

(A) L1 fl L is a deterministic CFL

(B) L3 fl L is recursive

(C) L1 U L2 is context free

(D) L1 fl L fl L3 is recursively enumerable

36. Given two three bit numbers a2a1a0 and b2b1b0 and c, the carry in, the
function that represents the carry generate function when these two numbers are
added is:

(A) a2b2 + a2a1b1 + a2a1a0b0 + a2a0b1b0 + a1b2b1 + a1a0b2b0 + a0b2b1b0

(B) a2b2 + a2b1b0 + a2a1b1b0 + a1a0b2b1 + a1a0b2 + a1a0b2b0 + a2a0b1b0

(C) a2 +b2 +(a2 $b2)(a1 +b1 +(a1 $b1) (a0 +b0))

(D) a2b2 + a2a1b1 + a2 a1a0b0 + a2 a0 b1b0 + a1 b2 b1 + a1a0 b2b0 + a0 b2b1b0

37. Consider the circuit in the diagram. The $ operator represents Ex-OR. The
D flip- flops are initialized to zeroes (cleared). The following data: 100110000
is supplied to the "data" terminal in nine clock cycles. After that the values
of q2q1q0 are:

(A) 000

(B) 001

(C) 010

(D) 101

39. We consider the addition of two 2's complement numbers b 1b 2 .b0 and a
1a 2....a0. A binary adder for adding unsigned binary numbers is used to add the
two numbers. The sum is denoted by c 1c 2....c0 and the carry-out by cQLJ. Which
one of the following options correctly identifies the overflow condition?

(A) c0(a1sb1)

(B) a 1b 1c+a 1b 1C

(C) cQLJ 1

(D) a1$b1$c1

40. Consider numbers represented in 4-bit gray code. Let h3h2h1h0 be the gray
code representation of a number nand let g3g2g1g0be the gray code of (n+1)
(modulo 16) value of the number. Which one of the following functions is
correct?

(A) g0(h3h2h1h0)=(1,2,3,6,1O,13,14,15)

(B) g1(h3h2h1h0)= (4,9,10,11,12,13,14,15)

(C) g2(h3h2h1h0)=(2,4,5,6,7,12,13,15)

(D) g3(h3h2h1h0)=(0,1,6,7,10,11,12,13)

41. A CPU has a cache with block size 64 bytes. The main memory has kbanks,
each bank being cbytes wide. Consecutive c—byte chunks are mapped on consecutive
banks with wraparound.

All the kbanks can be accessed in parallel, but two accesses to the same bank
must be serialized. A cache block access may involve multiple iterations of
parallel bank accesses depending on the amount of data obtained by accessing all
the kbanks in parallel. Each iteration requires decoding the bank numbers to be
accessed in parallel and this takes --ns.

The latency of one bank access is 80 ns. If c = 2 and k = 24, the latency of
retrieving a cache block starting at address zero from main memory is:

(A) 92 ns

(B) 104 ns

(C) 172 ns

(D) 184 ns

42. A CPU has a five-stage pipeline and runs at 1 GHz frequency. Instruction
fetch happens in the first stage of the pipeline. A conditional branch
instruction computes the target address and evaluates the condition in the third
stage of the pipeline. The processor stops fetching new instructions following a
conditional branch until the branch outcome is known. A program executes io
instructions out of which 20% are conditional branches. If each instruction
takes one cycle to complete on average, the total execution time of the program
is:

(A) 1.0 second

(B) 1.2 seconds

(C) 1.4 seconds

(D) 1.6 seconds

43. Consider a new instruction named branch-on-bit-set (mnemonic bbs). The
instruction "bbs reg, pos, label" jumps to label if bit in position pos of
register operand reg is one. A register is 32 bits wide and the bits are
numbered 0 to 31, bit in position 0 being the least significant. Consider the
following emulation of this instruction on a processor that does not have bbs
implemented. temp — reg & mask Branch to label if temp is non-zero. The variable
temp is a temporary register. For correct emulation, the variable mask must be
generated by

(A) mask —0x1<<pos

(B) mask f— 0 x rrrrrrrr >> pos

(C) mask—pos

(D) mask —0xf

44. Station A uses 32 byte packets to transmit messages to Station B using a
sliding window protocol. The round trip delay between A and B is 80 milliseconds
and the bottleneck bandwidth on the path between A and B is 128 kbps. What is
the optimal window size that A should use?

(A) 20

(B) 40

(C) 160

(D) 320

45. Two computers Cl and C2 are configured as follows. Cl has IP address
203.197.2.53 and netmask 255.255.128.0. C2 has IP address 203.197.75.201 and
netmask 255.255.192.0. which one of the following statements is true?

(A) Cl and C2 both assume they are on the same network

(B) C2 assumes Cl is on same network, but Cl assumes C2 is on a different
network

(C) Cl assumes C2 is on same network, but C2 assumes Cl is on a different
network

(D) Cl and C2 both assume they are on different networks.

46. Station A needs to send a message consisting of 9 packets to Station B
using a sliding window (window size 3) and go-back-n error control strategy. All
packets are ready and immediately available for transmission. If every 5th
packet that A transmits gets lost (but no acks from B ever get lost), then what
is the number of packets that A will transmit for sending the message to B?

(A) 12

(B) 14

(C) 16

(D) 18

48. Let T be a depth first search tree in an undirected graph G. Vertices u
and v are leaves of this tree T. The degrees of both u and v in G are at least
2. which one of the following statements is true?

(A) There must exist a vertex w adjacent to both u and v in G

(B) There must exist a vertex w whose removal disconnects u and v in G

(C) There must exist a cycle in G containing u and v

(D) There must exist a cycle in G containing uand all its neighbours in G.

49. An implementation of a queue Q, using two stacks Si and S2, is given
below:

void insert (Q, x)

push (Si, x);

void delete (Q)

if (stack—empty(52)) then

if (stack—empty(Si)) then

print("Q is empty");

return;

else while (! (stack—empty (Si)))

x=pop (Si);

push(52,x)

x=pop (S2);

Let flinsert and m( n)delete operations be performed in an arbitrary order on
an empty queue **Q.** Let x and y be the number of push and pop operations
performed respectively in the process. Which one of the following is true for
all m and n?

(A) n+m x<2n and 2m<y<n+m

(B) n+m x<2n and 2m<y<2n

(C) 2m x<2n and 2m<y<n+m

(D) 2m x<2n and 2m<y<2n

50. A set X can be represented by an array x[nl as follows:

Ii ifx[i1]=O

otherwise

Consider the following algorithm in which x,y and z are Boolean arrays of
size n:

algorithm zzz(x[ 1, y[ 1, z [

mt i;

for (i=O; i<n; ++i)

z[i] = (x[i] Ay[i]) V (x[i] A y[i])

}

The set Z computed by the algorithm is:

(A) (XUY)

(B) (xflY)

(C) (X-Y)fl(Y-X)

(D) (x-Y)U(Y-x)

## Previous Page

| Next Page