Follow Us :

PREVIOUS YEAR SOLVED PAPERS - GATE 2017 Shift 1

Avatto > > GATE COMPUTER SCIENCE > > PREVIOUS YEAR SOLVED PAPERS > > GATE 2017 Shift 1

41. Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B*. We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language {x ≠ f(x) | x ∈ A*}. Which of the following statements is true:

  • Option : A
  • Explanation :
    A TM is recursive iff it halts for every input string (either in accept or reject state). Here, a computable function is defined in a similar way.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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

  • Option : A
  • Explanation :

    Shortest path from B to C are two B-A-C and B-C both of weight '3'
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


43. A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-re-entrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l 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:

  • Option : D
  • Explanation : Reentrant property is provided, so that a process who owns a lock, can acquire same lock multiple times. Here it is non-reentrant as given, process cant own same lock multiple times. So if a thread tries to acquire already owned lock, will get blocked, and this is a deadlock.
    Hence correct answer is x=1, y=1.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


44. A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses x3 + x + 1 as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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

  • Option : D
  • Explanation : (p → q) → r is contradiction only when
    Pqr
    TTF
    FTF
    FFF
    And now for the above combination, the expression is always true when q is true. When q is false in the above combination (third one) will be false.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


Related Quiz.
GATE 2017 Shift 1