GATE Solved Paper 2020 - GATE 2020

42. Which of the following languages are undecidable? Note that 〈M〉 indicates encoding of the Turing machine M.
L1 = {〈M〉⏐L(M) = φ]
L2 = {〈M, w, q〉⏐M on input w reaches state q in exactly 100 steps}
L3 = {〈M〉⏐L(M) is not recursive)
L4 = {〈M〉⏐L(M) contains at least 21 members)

  • Option : C
  • Explanation :
    L1 L(m) = ϕ ⇒ emptiness problem of TM.
    TM is undecidable under emptiness.
    L2 = where a TM visits a particular state in finite steps in decidable, as we can do this with UTM.
    L3 = L(m) is non-Recursive,

    Clearly from the diagram
    L(A) ⇒ non recursive language accepted by TM
    L(B) ⇒ non-recursive language not accepted by TM.
    ∴ it is a non-trivial property, hence undecidable.
    L4 = Undecidable problem using rice-theorem.
    Hence, L1, L3, and L4 are undecidable.
Cancel reply
Cancel reply

43. Consider a double hashing scheme in which the primary hash function h1(k) = k mod 23, and the secondary hash function is h2(k) = 1 + (k mod19) Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key-value k =90 is ________.

  • Option : C
  • Explanation :
    Given Hash Function ⇒ h1(k) = k mod 23
    h2(k) = 1 + (k mod 19)
    Table size = 23
    Key = 90
    h1(k) = 90 mod 23 ≡ 21
    h2(k) = 1 + 90 mod 19 ≡ 1 + 14 = 15
    Double hashing, (h1(k) + i.h2(k)) mod 23
    Asked for probe 1, put i = 1
    (21 + 1. (15)) mod 23
    36 mod 23 = 13
Cancel reply
Cancel reply

44. Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in non-persistent mode. The web page contains text and five very small images. The minimum number of TCP connections required to display the web page completely in your browser is ______.

  • Option : B
  • Explanation :
    In non-persistent HTTP, each packet takes 2 RTT (Round trip Time): one for TCP connection, one or HTTP Text (Image file As, it is given text and 5 images that totals 6 objects.)
    So, it takes 12 RTT in total. But,
    12 RTT includes 6 HTTP connections + 6TCP connections.
    So, the minimum number of TCP connections required is 6.
Cancel reply
Cancel reply

45. Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other G itself is ______.

  • Option : C
  • Explanation :
    According to Lagrange’s theorem, state that for any finite group G, the order (number of element) of every subgroup t1 of G divides the order of G. therefore, possible subgroup of group of 35 elements.
    {1, 5, 7, 35}
Cancel reply
Cancel reply