PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2020

41 An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available address space 202.61.0.0/17. The ISP wants to assign an address space to the organization which will minimize the number of routing entries in the ISP’s router using route aggregation. Which of the following address spaces are potential candidates from which the ISP can allot any one to the organization?
I. 202.61.84.0/21
II. 202.61.104.0/21
III. 202.61.64.0/21
IV. 202.61.144.0/21

No. of host = 1500
No. of host bits = [log₂ 1500] = 11 bits
∴ Total possible hosts = 2¹¹ = 2³ × 2⁸
n is the netmask bits,
Range of addresses is = 2^{32 – n}
2¹¹ = 2^32-n
Available IP address ⇒ 202.61.0.0/17

So the IP address follow the pattern
0.0 to 7.255
8.0 to 15.255
16.0 to 23.255
:
64.0 to ...
:
104.0 to ...
∴ The possible IP addresses are 202.61.64.0/21 & 202.61.104.0/21

42 Which of the following languages are undecidable? Note that 〈M〉 indicates encoding of the Turing machine M.
L₁ = {〈M〉⏐L(M) = φ]
L₂ = {〈M, w, q〉⏐M on input w reaches state q in exactly 100 steps}
L₃ = {〈M〉⏐L(M) is not recursive)
L₄ = {〈M〉⏐L(M) contains at least 21 members)

L₁ L(m) = ϕ ⇒ emptiness problem of TM.
TM is undecidable under emptiness.
L₂ = where a TM visits a particular state in finite steps in decidable, as we can do this with UTM.
L₃ = 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.
L₄ = Undecidable problem using rice-theorem.
Hence, L₁, L₃, and L₄ are undecidable.

43 Consider a double hashing scheme in which the primary hash function h₁(k) = k mod 23, and the secondary hash function is h₂(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 ________.

Note – Numerical Type question

Given Hash Function ⇒ h₁(k) = k mod 23
h₂(k) = 1 + (k mod 19)
Table size = 23
Key = 90
h₁(k) = 90 mod 23 ≡ 21
h₂(k) = 1 + 90 mod 19 ≡ 1 + 14 = 15
Double hashing, (h₁(k) + i.h₂(k)) mod 23
Asked for probe 1, put i = 1
(21 + 1. (15)) mod 23
36 mod 23 = 13

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 ______.

Note – Numerical Type question

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.

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

Note – Numerical Type question

According to Lagrange’s theorem, state that for any finite group G, the order (number of element) of every subgroup t₁ of G divides the order of G. therefore, possible subgroup of group of 35 elements.
{1, 5, 7, 35}

i = 0	i = 1	i = 2
ex = 3 x 3	ex = 9 x 3	tot = t * t *ex
= 9	= 81	= 1 * 81 = 81

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2020

Follow Us :