1. Let (S, £ ) be a partial order with two minimal elements a and b, and a maximum element c. Let P : S ® {True, False} be a predicate defined on S. Suppose that p(a) = True, P(b) = False and P(x) Þ P(y) for all x, y Î S satisfying x £ y, where Þ stands for logical implication. Which of the following statements CANNOT be true?

(a) P(x) = True for all X Î S such that x ¹ b

(b) P(x) = False for all X Î S such that x ¹ a and x ¹ c

(c) P(x) = False for all X Î S such that b £ x and x ¹ c

(d) P(x) = False for all X Î S such that a £ and b £ x

 

2. Which of the following is a valid first order formula? (Here a and b are first order formulae with x as their only free variable)

(a) (( " x) [ a ] Þ ( " x)[ b ]) Þ ( " x) [ a Þ b ]

(b) ( " x) [ a ] Þ ( $ x) [ a Ù b ]

(c) (( " x) [ a v b ] Þ ( $ x)[ a ]) Þ ( " x) [ a ]

(d) ( " x) [ a Þ b ] Þ (( " x)[ a ] Þ ( " x) [ b ])

 

3. Consider the following formula a and its two interpretations I 1 and I 2

a: ( " x) [P x Û ( " y) [Q xy Û Ø Q yy]] ==> ( " x) [ Ø P x]

I 1: Domain: the set of natural numbers

P x == 'x is a prime number

Q xy == 'y divides x'

I 2: same as I 2 except that Px = 'x is a composite number'.

Which of the following statements is true?

(a) I 1 satisfies a , I 2 does not

(b) I 2 satisfies a , I 1 does not

(c) Neither I 1 nor I­ 2 satisfies a

(d) Both I 1 and I 2 satisfy a

 

4. m identical balls are to be placed in n distinct bags. You are given that m ³ kn, where k is a natural number ³ 1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?

(a)

(b)

(c)

(d)

 

5. Consider the following recurrence relation

T(1) = 1

T(n + 1) = T(n) + for all n ³ 1

The value of T(m 2) for m ³ 1 is

(a)

(b)

(c)

(d)

 

6. How many perfect matchings are there in a complete graph of 6 vertices?

• 15
• 24
• 30
• 60

 

7. Let f: A ® B be an injective (one-to-one) function. Define g: 2 A ® 2 B as:

g(C) = (f(x) \x Î C}, for all subsets C of A.

Define h: 2 B ® 2 A as: h(D) = { x\x Î A, f(x) Î D}, for all subsets D of B.

Which of the following statements is always true?

• g(h(D)) Í D
• g(h(D)) Ê D
• g(h(D)) Ç D = f
• g(h(D)) Ç (B-D) ¹ f

 

8. Consider the set {a, b, c} with binary operators + and x defined as follows:

+ a b c x a b c

a b a c a a b c

b a b c b b c a

c a c b c c c b

For example, a + c = c, c + a = a, c x b = c and b x c = a. Given the following set of equations:

 

(a x x)+(a x y)=c

(b x x)+(c x y)=c

the number of solution(s) (i.e., pair(s) (x, y) that satisfy the equations) is

(a) 0 (b) 1

(c) 2 (d) 3

 

9. Let å = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows:

g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11.

Let P i denote the i-th prime number (p 1 = 2)

For a non-empty string s = a 1...a n where each a i Î å , define f(s) = Õ n i= 1p i g(ai). For

a non-empty sequence (< Sl…Sn>) of strings from å + , define

 

h(<s l…s n>) = Õ n i = 1 p i f(si)

Which of the following numbers is the encoding, h of a non-empty sequence of strigs ?

• 2 73 75 7
• 2 83 85 8
• 2 93 95 9
• 2 105 107 10

 

10. A graph G = (V,E) satisfies | E | £ 3 | V | - 6. The min-degree of G is defined as

min {degree (v)}. Therefore, min-degree of G cannot be

v Î V

• 3
• 4
• 5
• 6

 

11. Consider the following system of linear equations

Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of a , does this system of equations have infinitely many solutions?

• 0
• 1
• 2
• infinitely many

 

12. A piecewise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale).

 

I f we use the Newton-Raphson method to find the roots of f(x) = 0 using x 0, x 1 and x 2 respectively as initial guesses, the roots obtained would be

(a) 1.3, 0.6, and 0.6 respectively

(b) 0.6, 0.6, and 1.3respectively

(c) 1.3, 1.3, and 0.6 respectively

(d) 1.3,0.6, and 1.3 respectively

 

13. The following is a scheme for floating point number representation using 16 bits.

Bit Position 15 14 … … 9 8 … … … 0

s

e

m

Sign Exponent Mantissa

 

Let s, e, and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is:

 

 

What is the maximum difference between two successive real numbers representable in this system?

• 2 –40
• 2-9
• 2 22
• 2 31

 

14. A 1-input, 2-output synchronous sequential circuit behaves as follows:

Let Z k n k denote the number of O's and 1's respectively in initial k bits of the input

(Z k + n k = k). The circuit outputs 00 until one of the following conditions holds.

• Z k – n k = 2. In this case, the output at the k-th and all subsequent clock ticks Is 10
• N k – Z k = 2. In this case, the output at the k-th and all subsequent clock ticks is 01.

What is the minimum number of states required in the state transition graph of the above circuit? ­

• 5
• 6
• 7
• 8

 

15. The literal count of a boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz') is 4. What are the minimum possible literal counts of the product-or-sum and sum-of ­product representations respectively of the function given by the following Karnaugh map? Here, X denotes "don't care"

 

xy ®	00	01	11	10
Zw ¯
00	X	1	0	1
01	0	1	X	0
11	1	X	X	0
10	X	0	0	X

 

  

• (11, 9)
• (9, 13)
• (9, 10)
• (11, 11)

16. Consider the ALU shown below.

If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C o only (+ and -denote addition and subtraction respectively)?

• A+ B, and A-B, but not A+ 1
• A+B, and A+ 1, but not A-B
• A + B, but not A - B, or A + 1

(d) A+ B, and A-B, and A+ 1

17. Consider the following circuit composed of XOR gates and non-inverting buffers.

The non-inverting buffers have delays d 1 = 2 ns and d 2 = 4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If the following waveform is applied at input A, how many transition(s) (change of logic levels) occur(s) at B during the interval from 0 to 10 ns ?

• 1
• 2
• 3
• 4

 

THE FOLLOWING INFORMATION PERTAINS TO below Qns.  

Consider the following assembly language program for a hypothetical processor. A, B and C are 8 bit registers. The meanings of various instructions are shown as comments.

 

MOVB, #0 ; B ¬ O

MOVC, #8 ; C ¬ 8

Z: CMP C, # 0 ; compare C with 0

JZX ; jump to X if zero flag is set

SUB C, # 1 ; C ¬ C-l

RRCA, # 1 ; right rotate A through carry by one bit. Thus:

; if the initial values of A and the carry

flag are a 7...a O and

; Co respectively, their values after the execution

of this

; instruction will be C 0a 7...a 1 and a 0 respectively.

JCY ; jump to Y if carry flag is set

JMPZ ; jump to Z

Y: ADD B, # 1 ; B ¬ B+l

JMPZ ; jump to Z

X:

 

18. If the initial value of register A is A 0, the value of register B after the program execution will be

• the number of 0 bits in A 0
• the number of 1 bits in A 0
• A 0
• 8

 

19. Which of the following instructions when inserted at location X will ensure that the value of register A after program execution is the same as its initial value?

• RRCA, #
• NOP ; no operation
• LRC A, # 1 ; left rotate A through carry flag by one bit
• ADD A, # 1

 

20. Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

(a) 1 (b) 5

(c) 7 (d) 8