# (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
(B) mask f— 0 x rrrrrrrr >> pos

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)