21.
Consider the Karnaugh map given below, where
X represents

*“don’t care”*and blank represents 0.
Assume for
all inputs (a, b, c, d), the respective complements (a’, b’, c’, d’) are also
available. The above logic is implemented using 2-input NOR gates only. The
minimum number of gates required is....................

Answer: 1.0

22. Consider
the language L given by the regular expression (a + b)*b(a + b) over the
alphabet {a, b}. The smallest number of states needed in a deterministic
finite-state automaton (DFA) accepting L is ..............

Answer: 4.0

23. Consider
a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance
of the schema EMP and a SQL query on it are given below.

The output
of executing the SQL query is ...............

Answer: 2.6

24. Consider
the following CPU processes with arrival times (in milliseconds) and length of
CPU bursts (in milliseconds) as given below:

If the pre-emptive
shortest remaining time first scheduling algorithm is used to schedule the processes,
then the average waiting time across all processes is ................... milliseconds.

Answer: 3.0

25. Consider
a two-level cache hierarchy with L1 and L2 caches. An application incurs 1.4
memory accesses per instruction on average. For this application, the miss rate
of L1 cache is 0.1; the L2 cache experiences, on average, 7 misses per 1000
instructions. The miss rate of L2 expressed correct to two decimal places is ................

Answer: 0.05

26. Let
G = (V, E) be any connected undirected edge-weighted graph. The weights of the
edges in E are positive and distinct. Consider the following statements:

(I) Minimum
Spanning Tree of G is always unique.

(II)
Shortest path between any two vertices of G is always unique.

Which of the
above statements is/are necessarily true?

(A) (I) only

(B) (II)
only

(C) both (I)
and (II)

(D) neither
(I) nor (II)

Answer: A

27. A
multithreaded program P executes with x number of threads and uses v number of
locks for ensuring mutual exclusion while operating on shared memory locations.
All locks in the program are non-reentrant. i.e., if a thread holds a lock l,
then it cannot re-acquire lock I without releasing it. If a thread is unable to
acquire a lock, it blocks until the lock becomes available. The minimum value
of x and the minimum value of y together for which execution of P can result in
a deadlock are:

(A) x=1, y=2

(B) x=2, y=1

(C) x=2, y=2

(D) x=1, y=1

Answer: D

28. The
value of

(A) is 0

(B) is -1

(C) is 1

(D) does not
exist

Answer: C

29. Let
p, q, and r be propositions and the expression (p→q)→r be a contradiction. Then,
the expression (r→p)→q is

(A) a tautology

(B) a
contradiction.

(C) always
TRUE when p is FALSE.

(D) always
TRUE when q is TRUE.

Answer: D

30. Let
u and v be two vectors in

**R**whose Euclidean norms satisfy ||u|| = 2||v||. What is the value of Î± such that w = u + Î±v bisects the angle between u and v?^{2}
(A) 2

(B) 1/2

(C) 1

(D) -1/2

Answer: A

## 0 Comments