GATE CSE PYQ Mistake Book: Top Exam Traps

The Trap: Believing that $O(n^2)$ automatically means the algorithm takes quadratic time in the worst case.

The Reality: Big-O ($O$) is merely a mathematical upper bound, NOT a synonym for worst case. QuickSort has best-case time $\Omega(n\log n)$, worst-case time $O(n^2)$, but saying "QuickSort is $O(n^3)$" is mathematically TRUE because $O$ is an upper bound! When IIT asks for tight bounds, look for $\Theta(g(n))$.

The Trap: Assuming allocating more physical frames to a process always decreases or preserves page fault frequency.

The Reality: FIFO suffers from Belady's Anomaly, where increasing page frames can lead to more page faults. Stack algorithms like LRU (Least Recently Used) and Optimal Replacement are mathematically immune to Belady's anomaly because the set of pages in an $m$-frame memory is always a strict subset of pages in an $(m+1)$-frame memory ($M(m) \subset M(m+1)$).

The Trap: Setting the congestion window `cwnd` to 1 MSS after 3 duplicate ACKs.

The Reality: - Timeout (Heavy Congestion): $\text{ssthresh} = \lfloor \text{cwnd} / 2 \rfloor$ and $\text{cwnd} = 1\text{ MSS}$. Slow Start begins.
- 3 Duplicate ACKs (Fast Retransmit/Fast Recovery): $\text{ssthresh} = \lfloor \text{cwnd} / 2 \rfloor$ and $\text{cwnd} = \text{ssthresh} + 3\text{ MSS}$ (or $\text{ssthresh}$ in Reno), skipping Slow Start and jumping straight to Congestion Avoidance.

The Trap: Assuming any relational schema can always be decomposed into BCNF while simultaneously preserving all functional dependencies.

The Reality: Lossless join decomposition is guaranteed for both 3NF and BCNF. However, Dependency Preservation is NOT always achievable in BCNF! For relation $R(A, B, C)$ with $F = \{AB \to C, C \to B\}$, candidate keys are $AB$ and $AC$. In $C \to B$, $C$ is not a superkey, but $B$ is prime $\implies$ schema is in 3NF. Any decomposition into BCNF destroys the dependency $AB \to C$.

The Trap: Applying Rice's theorem to prove that checking whether a Turing Machine has more than 10 states is undecidable.

The Reality: Rice's Theorem applies ONLY to non-trivial SEMANTIC properties (properties of the language recognized by the TM, $L(M)$). Syntactic properties (e.g. number of states, tape alphabet size, whether state $q_3$ is reachable in 5 steps) are properties of the machine's description $\langle M \rangle$ and are strictly DECIDABLE.

The Trap: Subtracting 2 for Network ID and Broadcast address in point-to-point /31 links (RFC 3021).

The Reality: In general IPv4 subnets (/30 and below), usable hosts $= 2^{32 - n} - 2$. But in modern point-to-point router links configured under RFC 3021 (/31), there are exactly 2 usable host addresses with no dedicated network or broadcast addresses. Read the GATE question premise carefully!

The Trap: Calculating pipeline cycle time by averaging the stage delays.

The Reality: The clock cycle time of a pipeline is governed strictly by the SLOWEST stage delay plus latch/register delay: $\tau = \max(t_1, t_2, \dots, t_k) + t_{latch}$. Speedup for $n$ instructions is $\frac{n \times \sum t_i}{(k + n - 1)\tau}$, NOT based on average stage delay.

The Trap: Blindly using $e \le 3v - 6$ to check planarity for bipartite or triangle-free graphs.

The Reality: $e \le 3v - 6$ assumes every face has at least 3 boundary edges. If the graph contains NO triangles (e.g., bipartite graphs like $K_{3,3}$), every face is bounded by at least 4 edges ($2e \ge 4f$). The tightened bound becomes: $e \le 2v - 4$!

The Trap: Misinterpreting negative values of counting semaphores.

The Reality: If a counting semaphore initializes to $S = 10$, and $15$ Wait ($P$) operations and $7$ Signal ($V$) operations are executed, the final value is $S = 10 - 15 + 7 = 2$. When a semaphore implementation allows negative values, $|S|$ represents the exact number of processes currently blocked in the waiting queue.

The Trap: Assuming constructing a binary heap of $n$ elements takes $O(n\log n)$ time.

The Reality: The standard bottom-up `Build-Min-Heap` algorithm takes $O(n)$ linear time because most nodes sit near the leaves with tiny subtrees ($\sum \frac{h}{2^h} = 2$). However, inserting $n$ elements one by one into an empty heap takes $O(n\log n)$ worst-case time!