1 X, Y and Z are closed intervals of unit length on the real line. The overlap of X and Y is half a unit. The overlap of Y and Z is also half a, unit. Let the overlap of X and Z be k units. Which of the following is true?

• k must be 1
• k must be 0­
• k can take any value between 0 and 1
• None of the above

• E 1 and E 2 are events in a probability space satisfying the following constraints:
• Pr (E I) = Pr (E 2)
• Pr (E I U E 2) = 1
• E 1 and E 2 are independent

The value of Pr (E 1), the probability of the event E p is

• 0
• 
• 
• 1

3 Let

and

Which of the following statements is true?

• S > T
• S = T
• S < T and 2S > T
• 2S £ T

4 A polynomial p(x) satisfies the following:

p (1) = p(3) = p(5) = 1

p(2) = p(4) = -1

The minimum degree of such a polynomial is

• 1
• 2
• 3
• 4

5 A relation R is defined on the set of integers as x Ry if f(x + y) is even. Which of the following state­ments is true?

• R is not an equivalence relation
• R is an equivalence relation having 1 equivalence class
• R is an equivalence relation having 2 equivalence classes
• R is an equivalence relation having 3 equivalence classes

6 Let P(S) denotes the power set of set S. Which of the following is always true?

• P(P (S)) = P(S)
• P(S) Ç P(P(S)) = { f }
• P(S) Ç S = P(S)
• S Ï P(S)

7 Let a, b, c, d be propositions. Assume that the equivalences a « (b V-b) and b « c hold. Then the truth value of the formula (a Ù b) -J. (a Ù c) Ù d) is always

• True
• False
• Same as the truth value of b
• Same as the truth value of d

8 What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

• L must be {a n| n is odd}
• L must be {a n| n is even}
• L must be {a n| ³ O}
• Either L must be {a n | n is odd}, or L must be {a n | n is even}

9 Consider the following decision problems :

(PI) Does a given finite state machine accept a given string

(P2) Does a given context free grammar generate an infinite number of stings

Which of the following statements is true?

(a) Both (PI) and (P2) are decidable (b) Neither (PI) nor (P2) are decidable

(c) Only (PI) is decidable (d) Only (P2) is decidable

10 The simultaneous equations on the Boolean variables x, y, z and w,

x+y+z=l

xy =0

xz+w = l

x+ =0

have the following solution for x, y, z and w, respectively.

(a) 0 1 0 0 (b) 1 1 0 1

(c) 1 0 1 1 (d) 1 0 0 0

11 Which function does NOT implement the Karnaugh map given below?

(a) (w + x) y (b) xy + yw

(c) (w + x) (w + y) (x + y) (d) None of the above

• The following arrangement of master-slave flip flops has the initial state of P, Q as 0, 1 (respectively). After three clock cycles the output state P, Q is (re­spectively),
• 1,0
• 1,1
• 0,0
• 0,1

­

13 A graphics card has on board memory of 1 MB. Which of the following modes can the card not support?

(a) 1600 x 400 resolution with 256 colours on a 17-inch monitor

(b) 1600 x 400 resolution with 16 million colours on a 14-inch monitor

(c) 800 x 400 resolution with 16 million colours on a 17-inch monitor

(d) 800 x 800 resolution with 256 colours on a 14-inch monitor

14 Consider the values A = 2.0 x 10 30, B =-2.0 x 10 30 , C= 1.0, and the sequence

X: =A+B Y: =A+C

X: = X + C Y: =Y+B

executed on a computer where floating-point numbers are represented with 32 bits. The values for X and Y will be

• X = 1.0, Y = 1.0
• X = 1.0, Y = 0.0
• X = 0.0, Y = 1.0
• X = 0.0, Y = 0.0

15 Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 £ k £ n:

reverse (s, 1, k) ;

reverse (s, k + 1, n);

reverse (s, l, n) ;

(a) Rotates s left by k positions (b) Leaves s unchanged

(c) Reverses all elements of s (d) None of the above

16 Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal, respectively, of a complete binary tree. Which of the following is always true?

(a) LASTIN = LASTPOST (b) LASTIN = LASTPRE

(c) LASTPRE = LASTPOST (d) None of the above

17 Consider the following functions

Which of the following is true?

(a) h (n) is O (f (n) ) (b) h (n) is O (g (n))

(c) g (n) is not O (f (n) ) (d) f(n) is O(g (n))