PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2018

61 Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carrier-sense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium.
Assume that the system has two nodes P and Q, located at a distance d meters from each other. P starts transmitting a packet at time t = 0 after successfully completing its carrier-sense phase. Node Q has a packet to transmit at time t = 0 and begins to carrier-sense the medium.
The maximum distance d (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P’s ongoing transmission is __________.

Note – Numerical Type question

Node that receives the packet to transmit will carrier-sense the medium for 5 units. Any packet which arrives within 5 unit will be sensed and keep the channel busy. Given that Signal speed is 10 meter/time.
Which means in 5 unit of time packet can travel 50 meters in max, that allow Q to successfully avoid the collision.
So, option (A) is correct.

62 Consider the weights and values of items listed below. Note that there is only one unit of each item.

Item Number	Weight in (kgs)	Value in Rupees)
1	10	60
2	7	28
3	4	20
4	2	24

The task is to pick a subset of these items such that their total weight is not more than 11 kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by V_greedy.

The value of V_opt − V_greedy is ______ .

Note – Numerical Type question

Item No.	Weight	Value	Value/Weight
1	10	60	6
2	7	28	4
3	4	20	5
4	2	24	12

After Sorting

Item No.	Weight	Value	Value/Weight
1	2	24	12
2	10	60	6
3	4	20	5
4	7	28	4

First, we have to Pick item_1 (Value weight ratio is highest).
After that Second highest is item_1. but cannot be picked because of its weight.
Now item_3 shall be picked. item_2 cannot be included because of its weight.
Therefore, overall profit by V_greedy = 20+24 = 44
Hence, V_opt – V_greedy = 60-44 = 16
So, answer is 16.

63 Consider the following program written in pseudo-code. Assume that x and y are integers:

Count (x, y) {
if (y ! = 1) {
if (x ! = 1) {
print(“*”);
Count (x/2, y);
}
else {
y = y – 1;
Count (1024, y);
}
}
}
The number of times that the print statement is executed by the call Count (1024, 1024) is __________.

Note – Numerical Type question

Count(1024, 1024) will be called and value of x will be deducted by x/2. ‘x’ will be printed 10 times. On count=10, value of x will become 1.
For every recursively for every y=1023 and count() is called 10times for each y. So, 1023 x 10 = 10230
Answer is 10230.

64 Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (H), medium (M) and low (L). Let P(H_G) denote the probability that Guwahati has high temperature. Similarly, P(M_G) and P(L_G) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use P(H_D), P(M_D) and P(L_D) for Delhi.

The following table gives the conditional probabilities for Delhi’s temperature given Guwahati’s temperature.

	H_D	M_D	L_D
H_G	0.40	0.48	0.12
M_G	0.10	0.65	0.25
L_G	0.01	0.50	0.49

Consider the first row in the table above. The first entry denotes that if Guwahati has high temperature (H_G) then the probability of Delhi also having a high temperature (H_D) is 0.40; i.e., P(H_D ∣ H_G) = 0.40. Similarly, the next two entries are P(M_D ∣ H_G) = 0.48 and P(L_D ∣ H_G) = 0.12. Similarly for the other rows.

If it is known that P(H_G) = 0.2, P(M_G) = 0.5, and P(L_G) = 0.3, then the probability (correct to two decimal places) that Guwahati has high temperature given that Delhi has high temperature is _______ .

Note – Numerical Type question.

The condition probability table given is

	H_D	M_D	L_D
H_G	0.40	0.48	0.12
M_G	0.10	0.65	0.25
L_G	0.01	0.50	0.49

P(H_G) = 0.2
P(M_G) = 0.5
P(L_G) = 0.3
Drawing the tree diagram for HD we get,

From diagram, P(H_G ∩ H_D) = 0.2x0.4
P(H_D) = 0.2x0.4+0.5x0.1+0.3x0.01 = 0.133
Required probability,
P(H_G | H_D) = (0.2x0.4)/0.133 = 0.60

65 Consider an IP packet with a length of 4500 bytes that includes a 20-byte IPv4 header and a 40-byte TCP header. The packet is forwarded to an IPv4 router that supports a Maximum Transmission Unit (MTU) of 600 bytes. Assume that the length of the IP header in all the outgoing fragments of this packet is 20 bytes. Assume that the fragmentation offset value stored in the first fragment offset value stored in the first fragment is 0.
The fragmentation offset value stored in the third fragment is _________.

Note – Numerical Type question