GATE CS 2024 Set 2

(D) holds. Suppose a cycle \(C\) has an even edge \(e\) and an odd edge \(f\). Extend the path \(C - f\) to a spanning tree \(T\); it contains \(e\) but not \(f\). Removing \(e\) splits \(T\) into two parts, and \(f\) must join them, because the rest of the cycle links the ends of \(e\). So \(T - e + f\) is another spanning tree whose weight differs from that of \(T\) by an odd amount, and both cannot be even.

The others fail. A triangle with weights 1, 1, 1 has every spanning tree of weight 2, yet its edges are odd, which rules out (A) and (C). A path with weights 1, 1, 2 is its own only spanning tree (weight 4) and mixes parities, which rules out (B).

Answer: D

Follow the counts through a derivation, which starts with one \(S\). The rule \(S \rightarrow aSbS\) adds one \(a\), one \(b\) and one extra \(S\); \(S \rightarrow aS\) adds one \(a\); \(S \rightarrow c\) turns one \(S\) into \(c\). Every \(S\) must finally become a \(c\), so:

• \(n_c(w) = 1 + n_b(w)\), so (C) is true.
• Every \(b\) arrives with an \(a\), so \(n_a(w) \ge n_b(w) = n_c(w) - 1 \gt n_c(w) - 2\), and (B) is true.

The string \(w = c\) has \(n_a = n_b = 0\) and \(n_c = 1\). It breaks (A), since \(0 \gt 0\) is false, and (D), since \(1 \ne 0\).

Answer: B, C

At 6000 RPM the disk makes 100 rotations per second, so one rotation takes 10 ms.

• Seek time: 5 ms.
• Average rotational latency: half a rotation, 5 ms.
• Transfer time of one sector: \(10 / 500 = 0.02\) ms.

Because the sectors lie at random places, each one needs its own seek and rotational wait: \(5 + 5 + 0.02 = 10.02\) ms per sector. For 3000 sectors the total is \(3000 \times 10.02 = 30060\) ms, that is 30.06 s. The sector size (512 bytes) is not needed. Treating the file as stored on consecutive sectors would give a much smaller time.

Answer: 30.06

On a timeout, TCP sets the slow-start threshold to half the current window, \(12 / 2 = 6\) MSS, and restarts slow start from a window of 1 MSS. In slow start the window doubles every RTT while all segments are acknowledged:

• first RTT after the timeout: 1 MSS;
• second RTT: 2 MSS;
• third RTT: 4 MSS.

The window is still below the threshold of 6, so slow start has not yet given way to linear growth. Continuing from 6 MSS would be the fast-recovery response to triple duplicate ACKs, not to a timeout.

Answer: 4

With CSMA/CD a station detects a collision only while it is still transmitting. In the worst case the collision happens at the far end of the segment, and the noise needs another one-way delay to come back, so a frame must last at least one round-trip propagation time.

• One-way delay: \(500 / (2 \times 10^{8}) = 2.5\ \mu\text{s}\).
• Round trip: \(5\ \mu\text{s}\).
• Minimum frame size: \(10^{8} \times 5 \times 10^{-6} = 500\) bits.

Using the one-way delay alone would give 250 bits, too short to guarantee detection.

Answer: 500

Since \(X\) and \(Y\) must be disjoint, a dependency is fixed by giving each of the 4 attributes one of three roles: in \(X\), in \(Y\), or in neither. That gives \(3^{4} = 81\) assignments. Remove those with an empty side by inclusion–exclusion:

• \(X\) empty: each attribute is in \(Y\) or in neither, \(2^{4} = 16\) ways;
• \(Y\) empty: likewise 16 ways;
• both empty: 1 way, subtracted twice above, so add it back.

Useful dependencies: \(81 - 16 - 16 + 1 = 50\).

Answer: 50

Add up the fixed fields of the 32-bit instruction:

• each register field names one of 16 registers, so it needs \(\log_2 16 = 4\) bits, and the two fields take 8 bits;
• 8 addressing modes need \(\log_2 8 = 3\) bits;
• the scalar field takes 16 bits.

That leaves \(32 - 8 - 3 - 16 = 5\) bits for the opcode, so at most \(2^{5} = 32\) opcodes can be encoded. The mode has its own field, so all 32 opcodes can be combined with each of the 8 addressing modes.

Answer: 32

Both designs run at the same 2 GHz clock, so the speedup is the ratio of their cycles per instruction (CPI).

• Non-pipelined CPI: 6.
• Pipelined CPI: the ideal 1 plus the average stall cycles, \(1 + 0.2 \times 2 + 0.2 \times 3 = 1 + 0.4 + 0.6 = 2\).

Speedup \(= 6 / 2 = 3.0\). The number of stages does not enter the calculation, because the pipelined throughput (1 instruction per cycle) and the non-pipelined cycle count (6) are both given directly.

Answer: 3.0

Think of Kruskal’s algorithm, which takes the cheapest edges first.

• The four weight-1 edges \(ab, af, cd, de\) form no cycle, so every minimum spanning tree contains them. They leave three components: \(\{a, b, f\}\), \(\{c, d, e\}\) and \(\{g\}\).
• Two more edges are needed, and all weight-2 edges meet \(g\): \(ga, gb, gf\) reach the first component and \(gc, gd, ge\) the second. A tree takes exactly one from each group, since two from the same group would close a cycle.
• The weight-3 edges are never used.

So there are \(3 \times 3 = 9\) minimum spanning trees, each of weight 8.

Answer: 9

Any graph with an edge needs at least 2 colours, and exactly 2 suffice when the graph is bipartite. Go round the octagon and colour the corners alternately red and blue; the eight sides are properly coloured because 8 is even.

Every other edge (the two verticals, the two horizontals and the four long diagonals) joins two corners that are three steps apart around the octagon. Three is odd, so each of them joins a red corner to a blue corner.

No edge joins two corners of the same colour, so the graph is bipartite (it is in fact \(K_{4,4}\)) and its chromatic number is 2.

Answer: 2