# GATE Computer Science Solved Paper 2017 Session I - Part 3

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....................
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 ..............
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 ...............
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.
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 ................

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)
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
28.       The value of
(A) is 0
(B) is -1
(C) is 1
(D) does not exist
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
(C) always TRUE when p is FALSE.
(D) always TRUE when q is TRUE.