GATE CS 2025 Set 2

Search in three binary-search phases:

1. Find the peak: compare \(A[m]\) with \(A[m+1]\). If \(A[m] < A[m+1]\) the peak is to the right, otherwise at \(m\) or to its left. Each comparison halves the range: \(O(\log n)\).
2. Binary search the increasing part \(A[1..i]\).
3. Binary search the decreasing part \(A[i+1..n]\).

That is \(O(\log n)\) comparisons in all, and no algorithm can do better: a sorted array is itself bitonic (take \(i = n\)), and searching a sorted array needs \(\Omega(\log n)\) comparisons. So the bound is \(\Theta(\log n)\); \(\Theta(\log^{2} n)\) is achievable but not the best, and \(\Theta(1)\) is impossible.

Answer: D

Each \(f \in \mathcal{F}\) is an \(n\)-bit vector, and \(f \preccurlyeq g\) compares the vectors position by position.

• Reflexive: \(f(x) \le f(x)\). Antisymmetric: \(f \preccurlyeq g\) and \(g \preccurlyeq f\) force \(f(x) = g(x)\) for every \(x\). Transitive, because \(\le\) is. So it is a partial order (B).
• Any two functions have a greatest lower bound, the pointwise minimum, and a least upper bound, the pointwise maximum, so it is a lattice (C): the Boolean lattice of subsets of \(\{1, \ldots, n\}\).
• It is not symmetric: the all-0 function is \(\preccurlyeq\) the all-1 function, but not the other way round. So A is false, and D is false because an equivalence relation must be symmetric.

Answer: B, C

Read the map with the usual Gray-code order (00, 01, 11, 10) for \(wx\) and \(yz\). The four corner 1s are the cells with \(x = 0, z = 0\), and the central block of four 1s has \(x = 1, z = 1\). So \(F = \overline{x}\,\overline{z} + xz\), which is option D.

• A: its four 4-literal terms are exactly the four corner cells, and \(\overline{x}\,\overline{z}(\overline{w}\,\overline{y} + w\overline{y} + \overline{w}y + wy) = \overline{x}\,\overline{z}\), so A equals D.
• B: \(w\overline{x}yz\) has \(x = 0, z = 1\), a 0 cell, and two corner cells are missing.
• C: \(w\overline{x}\,\overline{y}z\) is also a 0 cell, and two corner cells are missing.

Answer: A, D

• A true. \(PX = Q\) is \(L(UX) = Q\). Put \(Y = UX\): solve \(LY = Q\) by forward substitution, then \(UX = Y\) by back substitution.
• B true. \(L\) has a unit diagonal, so \(\det L = 1\) and \(\det P = \det L \cdot \det U = u_{11}u_{22}u_{33}\). If \(P\) is invertible this is non-zero, so \(U\) is invertible, and \(L\) always is.
• C true. If \(P\) is singular, \(u_{11}u_{22}u_{33} = \det P = 0\), so some \(u_{ii} = 0\).
• D false. A triangular matrix is symmetric only if it is diagonal. The symmetric \(P = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}\) has \(l_{21} = 1\) and \(u_{12} = 1\) with \(l_{12} = u_{21} = 0\), so neither factor is symmetric.

Answer: A, B, C

• A works. On PUSH, the new record stores a pointer to the minimum of the records below it: the smaller of the old top and the record the old top points to, found in \(O(1)\). MIN compares the top with the record its pointer names, also \(O(1)\). POP just removes the top, and the pointers in the records left behind are still correct.
• B fails. Once the minimum is popped, finding the new minimum needs an \(O(n)\) scan, so POP gets slower.
• C fails. Keeping an array sorted costs \(O(n)\) shifting on each PUSH and POP.
• D fails. Heap insertion and deletion take \(O(\log n)\), so PUSH and POP are no longer \(O(1)\).

Answer: A

A relation is in 3NF if, for every non-trivial FD \(X \to Y\), either \(X\) is a superkey or every attribute of \(Y\) is prime (part of some candidate key).

• R1: \(A\) and \(D\) appear on no right-hand side, so every key contains both, and \(\{A, D\}^{+} = \{A, B, C, D, E\}\). The only key is \(AD\). In \(D \to E\), \(D\) is not a superkey and \(E\) is not prime, so R1 is NOT in 3NF (it is not even in 2NF).
• R2: \(C\) appears on no right-hand side and \(C^{+} = \{A, B, C, D\}\), so \(C\) is the only key. In \(A \to D\), \(A\) is not a superkey and \(D\) is not prime: the transitive dependency \(C \to A \to D\). So R2 is NOT in 3NF.

Answer: C, D

The table replaces page 2 at the 4th reference, 3 at the 5th, 1 at the 8th, and then 4, 5 and 6 at the last three.

• Optimal fits. At the 4th reference the frames hold 1, 2, 3, next used at references 7, 13 and 12, so 2, needed farthest ahead, goes. Likewise 3 goes at the 5th reference and 1 at the 8th. At the last three faults no page in memory is used again, so any victim is optimal.
• LRU fails: at the 4th reference it would evict 1, the least recently used page.
• LFU fails: at the 8th reference page 5 has one use and pages 1 and 4 have two, so it would evict 5.
• MFU fails: at the 4th reference pages 1, 2 and 3 have one use each, and a first-in or least-recently-used tie-break evicts 1, not 2.

Answer: D

Every resource has a single instance, so a cycle means deadlock. Turn each edge pair into a waits-for edge between processes: \(P_1 \to P_2\) (for \(R_2\)), \(P_2 \to P_3\) (for \(R_3\)), \(P_2 \to P_4\) (for \(R_4\)), \(P_3 \to P_1\) (for \(R_1\)) and \(P_4 \to P_2\) (for \(R_2\)). That gives two cycles, \(P_1 \to P_2 \to P_3 \to P_1\) and \(P_2 \to P_4 \to P_2\), and both pass through \(P_2\).

• Aborting \(P_1\) leaves the cycle \(P_2 \to P_4 \to P_2\) (A false).
• Aborting \(P_3\) leaves the same cycle (B false).
• Aborting \(P_2\) breaks both cycles (C true).
• Aborting \(P_1\) and \(P_4\) removes a process from each cycle; only \(P_2 \to P_3\) remains (D true).

Answer: C, D

Read each word as sign (1 bit), biased exponent (8 bits) and fraction (23 bits); the value is \((-1)^{s} \times 1.f \times 2^{e - 127}\).

• 0xC1100000: sign 1, exponent 10000010 = 130, fraction 001000…, so \(X = -1.125 \times 2^{3} = -9\).
• 0x40C00000: sign 0, exponent 10000001 = 129, fraction 100000…, so \(Y = 1.5 \times 2^{2} = 6\).
• 0x41400000: sign 0, exponent 10000010 = 130, fraction 100000…, so \(Z = 1.5 \times 2^{3} = 12\).

Now check each option: (A) \(4(-9 + 6) + 12 = 0\); (B) \(12 - 12 = 0\); (C) \(-36 + 36 = 0\). (D) fails because \(-9 + 6 + 12 = 9\).

Answer: A, B, C

• (A) is wrong. The left side is \(\sum m(0, 3, 4, 5, 7)\) over \(ABC\). On the right, \(B\,C\) gives \(m_3, m_7\), \(\overline{B}\,\overline{C}\) gives \(m_0, m_4\) and \(\overline{A}\,\overline{B}\) gives \(m_0, m_1\): it contains 001 and misses 101. With \(A\,\overline{B}\) as the last term it would hold.
• (B) is the consensus theorem: \(BC = ABC + \overline{A}BC\), and these two terms are absorbed by \(AB\) and \(\overline{A}C\).
• (C) Expanding gives \(A\overline{A} + AB + \overline{A}C + BC = AB + \overline{A}C + BC\), which reduces to \(AB + \overline{A}C\) by (B).
• (D) By De Morgan, the complement of the product is the sum of the complemented factors: \(\overline{A}BD + \overline{C}\,\overline{D} + A\overline{C}\,\overline{D} + \overline{A}\,\overline{B}D\). The first and last terms combine to \(\overline{A}D\), and \(A\overline{C}\,\overline{D}\) is absorbed by \(\overline{C}\,\overline{D}\).

Answer: B, C, D