GATE 2017 Solved Paper CS: Set – 2 | xlvii

∞
Question Number: 50 Question Type: NAT
= (1 + z ) ∑ C (2 + r , r ) z r
r =0 A message is made up entirely of characters from the set X
= (1 + z ) C (2, 0) z 0 + C (3,1) z + C (4, 2) z 2 + C (5,3) z 3 + ... = {P, Q, R, S,T}. The table of probabilities for each of the
characters is shown below:
= (1 + z ) 1 + 3 z + 6 z 2 + 10 z 3 + ......
Character Probability
= (1 + 3 z + 6 z + 10 z + ...) + ( z + 3 z + 6 z + 10 z + ...)
2 3 2 3 4
P 0.22

= 1 + 4 z + 9 z 2 + 16 z 3 + ....... Q 0.34

∴ a0 = constant term of the generating function R 0.17

⇒ a0 = 1 S 0.19

a3 = The coefficient of z in the generating function.

3 T 0.08

⇒ a3 = 16 Total 1.00

∴ a3 −a0 = 16 −1 = 15 If a message of 100 characters over X is encoded using

Hence, the correct answer is (15). Huffman coding, then the expected length of the encoded
message in bits is _________.
Question Number: 48 Question Type: NAT
If a random variable X has a Poisson distribution with mean Solution: Message of 100 characters contains letters P, Q,
5. then the expectation E[(X + 2)2] equals _________. R, S, T with their frequencies 22, 34, 17, 19, 8.
The Huffman tree for the above is:
Solution: Given X is a Poisson random variable and mean
of X = E(X) = 5 I4

∴ Variance of X = Var (X) = 5

Consider E ( X + 2)  = E  X 2 + 4 X + 4
2

 
= E ( X 2 ) + 4E ( X ) + 4
1
=  var ( X ) + ( E ( X )) + 4 E ( X ) + 4
2 0
 
= 5 + 52 + 4×5 + 4 = 54
Hence, the correct answer is (54). I3 (59)

Question Number: 49 Question Type: NAT

In a B+ tree, if the search-key value is 8 bytes long, the 0
1
block size is 512 bytes and the block pointer size is 2 bytes,
then the maximum order of the B+ tree is __________.

Solution: Given, I2 (41) Q I1 (25)

Search key value V = 8 B (34)

Block Size B = 512 B

Block pointer size P = 2B 0 1
1
0
If the maximum order is m, then
(m × P) + ((m – 1) × V) ≤ B
⇒ m * 2 + ((m – 1) × 8) ≤ 512 P S T
R
⇒ 2 m + 8m – 8 ≤ 512 (22) (19) (17) (8)

⇒ 10m ≤ 520 Number of bits required for each character is

⇒ m ≤ 52 P – 00 – 2 bits × 22 ⇒ 44
∴ maximum order is 52. Q – 10 – 2 bits × 34 ⇒ 68
Hence, the correct answer is (52). R – 110 – 3 bits × 17 ⇒ 51
xlviii | GATE 2017 Solved Paper CS: Set – 2

S – 01 – 2 bits × 19 ⇒ 38 one eigenvalue of M is 2, then the largest among the abso-

T – 111 – 3 bits x 8 ⇒ 24 lute values of the eigenvalues of M is__________.
Total bits required = 225 Solution: Given the characteristic polynomial of a 3 × 3
Hence, the correct answer is (225). matrix M is λ3 − 4λ2 +aλ + 30, a ∈ 
Also given one eigen value of M is 2.
Question Number: 51 Question Type: NAT
Let λ1 and λ2 be the other two eigen values of M.
Consider the set of processes with arrival time (in millisec-
onds). CPU burst time (in milliseconds). and priority (0 is The characteristic equation of M is
the highest priority) shown below. None of the processes λ3 − 4λ2 + aλ + 30 = 0
have I/O burst time.
We know that,
Process Arrival Time Burst Time Priority Sum of the eigen values of M = − (The coefficient of λ2
P1 0 11 2 in its characteristic equation)
⇒ 2 × λ1 +λ2 = − (−4)
P2 5 28 0
⇒ λ1 + λ2 = 2 (1)
P3 12 2 3
and product of the eigen values of M = −(constant term of
P4 2 10 1 the characteristic equation of M).
P5 9 16 4 ⇒ 2 + λ1 × λ2 = −30
⇒ λ1λ2 = −15(2)
The average waiting time (in milliseconds) of all the pro-
We know that the quadratic equation with λ1 and λ2 as roots
cesses using preemptive priority scheduling algorithm
is
is________.
λ2 − (λ1 + λ2) λ + λ1 λ2 = 0
Solution: Using preemptive priority scheduling algrithm,
the Gantt chart is as below: ⇒ λ2 − (2) λ − 15 = 0 (From (1) and (2))
⇒ λ − 2λ − 15 = 0
2

P1 P1 P4 P4 P4 P2 P4 P1 P3 P5
⇒ (λ − 5) (λ + 3) = 0
0 1 2 3 4 5 33 40 49 51 67
⇒ λ = 5; λ = −3
i.e., λ1 = 5 and λ2 = −3
P2 (Priority 0)
P4 (Priority 1) ∴ The eigen values of M are −3, 2 and 5.
At time 33 ∴ The largest among the absolute values of the eigen values
of M is 5.
P2 completed, P4 Left with 7 units of burst time.
Hence, the correct answer is (5).
At time 40
Question Number: 53 Question Type: NAT
P4 completed, P1 Left with 9 units of burst time
Consider a machine with a byte addressable main memory
After completion of process execution: of 232 bytes divided into blocks of size 32 bytes. Assume that
waiting time of P1 = 40 – 2 = 38 a direct mapped cache having 512 cache lines is used with
this machine. The size of the tag field in bits is_______.
waiting time of P2 = 0
waiting time of P3 = 49 – 12 = 37 Solution: Main memory capacity = 232 B
Waiting time of P4 = 33 – 5 = 28 Block size = 32B = 25B
waiting time of P5 = 51 – 9 = 42 Number of lines in cache = 512 = 29
38 + 0 + 37 + 28 + 42 9 5
∴ Average waiting time =
5 Tag Line offset
= 29 ms 
32−bits
Hence, the correct answer is (29).
Tag = 32 − (9 + 5)
Question Number: 52 Question Type: NAT = 18
If the characteristic polynomial of a 3 × 3 matrix M over  Hence, the correct answer is (18).
(the set of real numbers) is λ3 − 4 λ2 + aλ + 30, a ∈ , and