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

21.       Consider the set X = {a,b,c,d,e} under the partial ordering
R = {(a, a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e)}.
The Hasse diagram of the partial order (X, R) is shown below.
The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is ..................
22.       Let
be two matrices.
Then the rank of P + Q is ..................
23.       G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ...............
24.       Consider a quadratic equation x2 - 13x + 36 = 0 with coefficients in a base b. The solutions of this equation in the same base b are x = 5 and x = 6. Then b = ...................
25.       The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = {w1aw2 | w1, w2 Ïµ {a, b}*, |w1| = 2, |w2| ≥ 3} is ................

26.       P and Q are considering to apply for a job. The probability that P applies for the job is ¼, the probability that P applies for the job given that Q applies for the job is ½, and the probability that Q applies for the job given that P applies for the job is 1/3. Then the probability that P does not apply for the job given that Q does not apply for the job is
(A) 4/5
(B) 5/6
(C) 7/8
(D) 11/12
27.       If w, x, y, z are Boolean variables, then which one of the following is INCORREC’T?
28.       Given f(w,x,y,z) = ∑m(0,1,2,3,7,8,10) + ∑d(5,6,11,15), where d represents the don’t-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w, x, y, z)?
(A) f = (w’ + z’)(x’ + z)
(B) f = (w’ + z)(x + z)
(C) f = (w + z)(x’ + z)
(D) f = (w + z’)(x’ + z)
29.       In a two-level cache system, the access times of L1 and L2 caches are 1 and 8 clock cycles, respectively. The miss penalty from the L2 cache to main memory is 18 clock cycles. The miss rate of L1 cache is twice that of L2. The average memory access time (AMAT) of this cache system is 2 cycles. The miss rates of L1 and L2 respectively are:
(A) 0.111 and 0.056
(B) 0.056 and 0.111
(C) 0.0892 and 0.1784
(D) 0.1784 and 0.0892