PREVIOUS YEAR SOLVED PAPERS MCQ - 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:

Character	Probability
P	0.22
Q	0.34
R	0.17
S	0.19
T	0.08
Total	1.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

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

52 The next state table of a 2-bit saturating up-counter is given below.

Q₁	Q₀	Q₁⁺	Q₀⁺
0	0	0	1
0	1	1	0
1	0	1	1
1	1	1	1

The counter is built as a synchronous sequential circuit using T flip-flops. The expression for T₁ and T₀ are

Q₁	Q₀	Q₁⁺	Q₀⁺	T₁	T₀
0	0	0	1	0	1
0	1	1	0	1	1
1	0	1	1	0	1
1	1	1	1	0	0

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.

Process	Arrival Time	Burst Time	Priority
P1	0	11	2
P2	5	28	0
P3	12	2	3
P4	2	10	1
P5	9	16	4

The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is ____.

Note – Numerical Type question

Process	AT	BT	Priority
P1	0		2
P2	5		0
P3	12		3
P4	2		1
P5	9		4

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

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

P(X = j) = p_j, p_j ≥ 0, j ∈ {0,....N} and

, define the polynomial function

For a certain discrete random variable Y, there exists a scalar β ∈ [0, 1] such that g_Y(z) = (1 + β + βz)^N. The expectation of Y is

Derivative of g_x(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β.

55 If the ordinary generating function of a sequence

, then a₃ - a₀ is equal to _____.

= (1+Z) (1+3Z + 6Z² + 10Z³ +……….∞)
Using binomial theorem
= 1 + 4Z + 9Z² + 16Z³ + …… ∞………(2)
From (1) and (2), a₀ = 1 and a₃ = 16
∴ a₃ – a₀ = 15

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 2

Follow Us :