GATE Solved Paper 2017-19 - GATE 2017 Shift 2

51. A message is made up entirely of characters from the set X= {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:

CharacterProbability
P0.22
Q0.34
R0.17
S0.19
T0.08
Total1.00
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is_____.


Note – Numerical Type question

  • Option : A
  • Explanation :
    By using haffman tree :

    So, number of bit required for each alphabet:
    T = 3 bit, R = 3 bit, Q = 2 bit, S = 2 bit, P = 2 bit
    Then, average length per character is = (number of bits * frequency of occurance of each alphabets)
    = 3 * 0.08 + 3 * 0.17 + 2 * 0.34 + 2 * 0.19 + 2 * 0.22 = 2.25 bits
    And, average length for 100 character = 2.25 * 100 = 225 bits.
    Hence, 225 bits is correct answer
Cancel reply
Cancel reply

53. Consider the set of processes with arrival time (in milliseconds). CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.

ProcessArrival TimeBurst TimePriority
P10112
P25280
P31223
P42101
P59164
The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is ____.

Note – Numerical Type question

  • Option : A
  • Explanation :
    ProcessATBTPriority
    P10 2
    P25 0
    P312 3
    P42 1
    P59 4


    w.t. = 0 + 0 + ( 33 – 5) + (40 – 2) + (49 – 12) + (51 – 9) = 145
    Avg wt = 145/5 = 29
Cancel reply
Cancel reply

54. For any discrete random variable X, with probability mass function

  • Option : B
  • Explanation :
    Derivative of gx(z) evaluated at z=1 gives expectation E(X) of X.
    Therefore, take derivative of gY(z) with respect to z, and plug in z=1
    Derivative is N.β.(1 - β + βz)(N-1), plug in z=1, gives Nβ.
Cancel reply
Cancel reply

55. If the ordinary generating function of a sequence

  • Option : A
  • Explanation :

    = (1+Z) (1+3Z + 6Z2 + 10Z3 +……….∞)
    Using binomial theorem
    = 1 + 4Z + 9Z2 + 16Z3 + …… ∞………(2)
    From (1) and (2), a0 = 1 and a3 = 16
    ∴ a3 – a0 = 15
Cancel reply
Cancel reply