GATE Solved Paper 2017-19 - GATE 2019

56. Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________.

  • Option : A
  • Explanation :
    No. of pairs with path length 0=8.0=8.
    No. of pairs with path length 1=0.1=0.
    No. of pairs with path length 2=8.2=8.
    No. of pairs with path length 3=0.3=0.
    No. of pairs with path length 4=16.4=16.
    No. of pairs with path length 5=0.5=0.
    No. of pairs with path length 6=32.6=32.
    Total number of possible pairs =8×8=64=8×8=64
    So, expected path length,E(x),
    =0×864+2×864+4×1664+6×3264=27264=4.25
Cancel reply
Cancel reply

57. Suppose Y is distributed uniformly in the open interval (1, 6). The probability that the polynomial 3x2 + 6xy + 3Y + 6 has only real roots is (rounded off to 1 decimal place) ________.

  • Option : A
  • Explanation :
    It is given that, Polynomial 3x2 + 6xY + 3Y + 6 has only real roots
    b2 – 4ax ≥ 0
    (6Y)2 – 4(3) (3Y+ 6) ≥ 0
    Y2 – Y - 2 ≥ 0<
    >Y ∈ (–∞, – 1] ∩ [2, ∞)
    ⇒ Y ∈ [2, 6)
    Since y is uniformly distributed in (1, 6)
    Probability distributed function,
    Gate2019 cs
Cancel reply
Cancel reply

58. Let Σ be the set of all bijections from {1,…,5} to {1,…,5}, where 𝑖𝑑 denotes the identity function, i.e. id(j) =j,∀j. Let ∘ denote composition on functions. For a string 𝑥 = 𝑥1 𝑥2 ⋯ 𝑥n ∈ Σsup>1, 𝑛 ≥ 0, let (𝑥) = 𝑥1 ∘ 𝑥2 ∘ ⋯ ∘ 𝑥n.
Consider the language 𝐿 = {𝑥 ∈ Σ∗| (𝑥) = 𝑖𝑑}. The minimum number of states in any DFA accepting L is _________.

  • Option : A
  • Explanation :
    The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements. The starting state will be “id” state, named as Gate2017 cs and from there
    n! arrows will go the n! states each named with a distinct permutation of the set {1, 2, 3, 4, 5}. Since composition of permutation function is closed every arrow has to go to some permutation and hence some state.
    Since the language only has those strings where π(x) = id only the starting state (“id” state) will be the final state. Sample machine with only 2 states is shown below
    Gate2017 cs
Cancel reply
Cancel reply

59. Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is__________.

  • Option : A
  • Explanation :
    If a switch has 8 ports then it means it can connect maximum 8 host. and 2 switch can connect 16 hosts independently. but we need one port for both of them to connect with each other. so now one- one port is used from both the switches for connecting then total port available free on both the switch is 7. so maximum 14 host can be connected but for the 15th host we need another switch.
    3 switches of ethernet are required to connect 15 computers.
    Hence, 3 is correct answer.
Cancel reply
Cancel reply

60. What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as f = Σ (0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available.

  • Option : A
  • Explanation :
    f = Σm(0, 2, 5, 7, 8, 10, 13, 15)
    f = ΠM(1, 3, 4, 6, 9, 11, 12, 14)
    Gate 2019cs
    f can be implemented using 3 NOR gates.
    So, option (A) is correct
Cancel reply
Cancel reply