GATE CS 2025 Set 2

Reading the three gates that feed the OR gate:

• the NAND gate gives \(\overline{XY}\);
• the NOT gate on \(X\) gives \(\overline{X}\);
• the AND gate gives \(X\overline{Y}\).

So \(F = \overline{XY} + \overline{X} + X\overline{Y}\), which is option C as written. By De Morgan's law \(\overline{XY} = \overline{X} + \overline{Y}\); the term \(\overline{X}\) repeats part of this and \(X\overline{Y}\) is absorbed by \(\overline{Y}\), so \(F = \overline{X} + \overline{Y} = \overline{XY}\). That is option A, and option B reduces to it the same way.

D is wrong: at \(X = Y = 1\), \(F = 0\) but \(X + \overline{Y} = 1\).

Answer: A, B, C

Booth's algorithm looks at each multiplier bit \(Q_i\) together with the bit to its right, \(Q_{i-1}\), taking \(Q_{-1} = 0\). The pair 10 subtracts M, the pair 01 adds M, and 00 or 11 only shifts. So the number of operations is the number of adjacent bit pairs that differ once a 0 is appended to Q; the multiplicand M plays no part.

Q with the extra bit is 1010 0100 1010 1010 0. Of its 16 adjacent pairs, only 3 are equal (the three 00 pairs). The other 13 each cost one operation: 7 subtractions (pair 10) and 6 additions (pair 01).

Answer: 13

The loop is the subtraction form of Euclid’s algorithm. Replacing the larger number by the difference of the two never changes their greatest common divisor, and the values keep shrinking until they are equal, so both end up as \(\gcd(126, 105)\).

Trace of \((x, y)\): \((126, 105) \to (21, 105) \to (21, 84) \to (21, 63) \to (21, 42) \to (21, 21)\). Now x!=y is false, the do-while loop exits and 21 is printed.

Answer: 21

Each flip-flop in a ripple counter toggles on every active edge it receives, so its output completes one cycle for every two input cycles: each stage halves the frequency. The output of the 4th (last) flip-flop therefore runs at \(f_{clk}/2^{4} = f_{clk}/16\), and its period is 16 clock periods.

\(16\,T_{clk} = 64\ \mu\text{s} \Rightarrow T_{clk} = 4\ \mu\text{s} \Rightarrow f_{clk} = \frac{1}{4\ \mu\text{s}} = 250\ \text{kHz}\).

The counter’s frequency is its input clock frequency. Taking the last stage’s own frequency, \(1/64\ \mu\text{s} \approx 15.6\) kHz, is the usual slip.

Answer: 250

Insert the keys in order, going left for a smaller key and right for a larger one:

• 10 is the root; \(-4\) goes left of 10 and 15 right of 10.
• 30 goes right of 15, and 20 goes left of 30.
• 5 goes right of \(-4\), and 60 goes right of 30.
• 19 is larger than 10 and 15 but smaller than 30 and 20, so it becomes the left child of 20.

The path from 19 up to the root is \(19 \to 20 \to 30 \to 15 \to 10\): 4 edges, i.e. 19 sits at depth 4.

Answer: 4

In Stop-and-Wait the sender transmits one frame and then waits idle until the acknowledgement comes back, so one cycle lasts \(T_t + 2T_p\) (the ACK and processing times are negligible).

• Transmission time: \(T_t = \frac{3000}{2000} = 1.5\) s.
• Round-trip propagation: \(2T_p = 2 \times 0.1 = 0.2\) s.

Utilization \(= \frac{T_t}{T_t + 2T_p} = \frac{1.5}{1.7} \approx 0.8824\), about 88.2%, which is option A. Option B (93.75) comes from counting the propagation delay only one way: \(\frac{1.5}{1.6} = 0.9375\).

Answer: A

MSTs stay. Every spanning tree of a connected graph with \(n\) vertices has exactly \(n - 1\) edges, so every spanning tree gets heavier by the same amount, \((n - 1)\alpha\). Their order by weight does not change, so every MST remains an MST.

SPs can change. A path with \(k\) edges gets heavier by \(k\alpha\), so paths with more edges are penalised more. Take edges \(uv\) and \(vw\) of weight 1 and an edge \(uw\) of weight 3. The shortest path from \(u\) to \(w\) is \(u, v, w\) with weight 2. After adding \(\alpha = 2\) it weighs 6, while the single edge \(uw\) weighs 5, so the old SP is no longer shortest.

Answer: C

• P: link the tail of one list to the head of the other and update the tail pointer. That is a fixed number of pointer changes: \(\Theta(1)\).
• Q: copy both arrays into one array of size \(2n\) and run bottom-up build-heap, which takes linear time: \(\Theta(n)\). Inserting the \(n\) keys one at a time would cost \(\Theta(n \log n)\), so that bound (B, C) is not the best.
• R: an in-order traversal of each tree gives two sorted lists in \(\Theta(n)\). Merge them in \(\Theta(n)\), then build a BST from the merged list (middle element as root, recursively) in \(\Theta(n)\). Inserting one tree’s keys into the other would give the slower \(\Theta(n \log n)\) or \(\Theta(n^{2})\) of D and C.

Answer: A

Each block holds one byte, so the address has no offset field: it is just tag plus index, \(4 + 12 = 16\) bits.

• Main memory: \(2^{16}\) bytes = 64 KB.
• Cache: the index picks one of \(2^{12}\) blocks of 1 byte each, so the cache holds \(2^{12}\) bytes = 4 KB.

Option D’s 6 KB would add the 4-bit tags to the data (12 bits per block), and its 128 KB would need a 17-bit address, so it does not fit.

Answer: A

\(\text{FOLLOW}(A) = \{a, c\}\), since \(A\) is followed by \(a\) in \(S \to Aa\) and by \(c\) in \(S \to bAc\).

• Not SLR(1). From the start state, reading \(d\) gives the items \(S \to d \cdot c\) and \(A \to d \cdot\). SLR reduces by \(A \to d\) on every symbol of \(\text{FOLLOW}(A)\), including \(c\), where the first item shifts: a shift-reduce conflict. The state after \(bd\) clashes the same way on \(a\).
• LALR(1). With LR(1) lookaheads, \(A \to d \cdot\) has lookahead \(a\) only in the first state and \(c\) only in the second, so neither conflicts. No two LR(1) states share a core, so the LALR(1) table equals the conflict-free CLR(1) table.

So \(G\) is LALR(1) (and CLR(1)) but not SLR(1).

Answer: C