2.1 How many 4-digit even numbers have all 4 digits distinct?

(a) 2240 (b) 2296

(c) 2620 (d) 4536

2.2 Consider the following statements:

S1 : There exist infinite sets A, B, C such that A Ç (B È C) is finite.

S2: There exist two irrational numbers x and y such that (x +y) is rational. Which of the following is true about S1 and S2 ?

• Only S1 is correct
• Only S2 is correct
• Both S1 and S2 are correct
• None of S1 and S2 is correct

2.3 Let f : A ® B be a function, and let E and F be subsets of A. Consider the following statements about images.

S1 :f (E È F)=f (E) È f (F)

S2 :f (E Ç F)=f(E) Ç f (F)

Which of the following is true about S1 and S2 ?

• Only S1 is correct
• Only S2 is correct
• Both S1 and S2 are correct
• None of S1 and S2 is correct

2.4 Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?

• 1/7 7
• 1/7 6
• 1/2 7
• 7/2 7

2.5 Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

• 8
• 14
• 15
• 48

• Consider the following languages:

L1={w w l w Î {a,b}*}

L2={ww R | w Î {a, b}*, w R is the reverse of w}

L3 = { 0 2i | i is an integer}

L4 = {O i2| i is an integer}

Which of the languages are regular?

• Only L1 and L2
• Only L2, L3, and L4
• Only L3 and L4
• Only L3

2.7 Consider the following problem X .

Given a Turing machine M over the input alphabet å , any state q of M

and a word W Î S *, does the computation of M on w visit the state q ?

Which of the following statements about X is correct?

• X is decidable
• X is undecidable but partially decidable
• X is undecidable and not even partially decidable.
• X is not a decision problem

2.8 Consider the following circuit with initial state Q o = Q 1 = 0. The D Flip-Flops are positive edge triggered and have set up times 20 nanosecond and hold times 0.

Consider the following timing diagrams of X and C; the clock period of C ³ 40 nanosecond. Which one is the correct plot of Y?

2.9 Which is the most appropriate match for the items in the first column with the items in the second column ?

X Indirect Addressing I. Array implementation

Y Indexed Addressing II. Writing relocatable code

Z. Base Register Addressing III. Passing array as parameter

• (X. III), (Y, I), (Z, II)
• (X, II), (Y, III), (Z, I)
• (X, III), (Y, II), (Z, I)
• (x, I), (Y, III), (Z, II)

2.10 The 2's complement representation of (-539) 10 in hexadecimal is

• ABE
• DBC
• DE5
• 9E7

• Consider the circuit shown below. The output of a 2:1 Mux is given by the function (ac' + bc).

Which of the following is true?

• f=x1'+x2
• f=x1 ’ x 2+xlx2'
• f=x1x2+x1 ‘x2'
• f=x1 +x2'

2.12 Consider the circuit given below with initial state Q 0 = 1, Q 1 = Q 2 = O. The state of the circuit is given by the value 4Q 2 + 2Q 1 +Q 0

Which one of the following is the correct state sequence of the circuit?

(a) 1,3,4,6,7,5,2 (b) 1,2,5,3,7,6,4

(c) 1,2,7,3,5,6,4 (d) 1,6,5,7,2,3,4.

2.13 Consider the following data path of a simple non-pipelined CPU. The registers A, B, A 1, A 2, MDR, the bus and the ALU are 8-bit wide. SP and MAR are 16-bit registers. The MUX is of size 8 x (2:1) and the DEMUX is of size 8 x (1: 2). Each memory operation takes 2 CPU clock cycles and uses MAR (Memory Address Register) and MDR(Memory Date Register). SP can be decremented locally.

The CPU instruction "push r". where = A or B, has the specification

M[SP] ¬ r

SP ¬ SP-l

How many CPU clock cycles are needed to execute the "push r" instruction?

• 2
• 3
• 4
• 5

2.14 Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct?

• d(r, u) < d (r, v)
• d(r, u) > d(r, v)
• d(r, u) £ d (r, v)
• None of the above