GATE 2018 CS (Computer Science) question paper with solutions

The first blank needs a subject and verb: "They're" (they are) bringing. The second blank needs a possessive before "books": "their". The third blank needs a place, answering "from where": "there". So the sentence reads "They're bringing their books from there." Answer: (B).

Concept: Tests the homophones they're / their / there: contraction of "they are", possessive pronoun, and adverb of place. The trap is choosing by sound; read each blank for its grammatical role.

The word "but" sets up a contrast with "organized" investigations. The blank therefore needs a word meaning the opposite of organized: "meandering" (wandering, without a fixed course). "Systematic" and "consistent" mean organized, and "timely" is unrelated to the contrast. Answer: (A).

Concept: Vocabulary in context with a contrast signal. "But" means the blank opposes "organized". The trap is picking "systematic" because it sounds like a positive word for an investigation.

Side of the square = √d, so the diagonal = √2 · √d = √(2d). This is the circle's diameter, so the radius r = √(2d)/2 and r² = 2d/4 = d/2. Area of the circle = πr² = πd/2. Answer: (D) (1/2)πd.

Concept: Square diagonal = side × √2, and circle area uses the radius, not the diameter. The usual trap is using the diagonal as the radius (giving 2πd) or squaring d itself, which is already an area.

The number is LCM(20, 42, 76) + 7. 20 = 2² · 5, 42 = 2 · 3 · 7, 76 = 2² · 19. LCM = 2² · 3 · 5 · 7 · 19 = 7980. Smallest number = 7980 + 7 = 7987. Check: 7987 = 20 × 399 + 7 = 42 × 190 + 7 = 76 × 105 + 7. Answer: (C) 7987.

Concept: Same remainder for several divisors means number = k × LCM + remainder; the smallest is LCM + remainder. The trap is multiplying the divisors instead of taking the LCM, which overshoots.

Successive ratios: 12/2 = 6, 60/12 = 5, 240/60 = 4, 720/240 = 3, 1440/720 = 2. The next multiplier is 1, so the missing term is 1440 × 1 = 1440, and then 1440 × 0 = 0, which matches the last term. Answer: (B) 1440.

Concept: A multiplicative series with a decreasing multiplier 6, 5, 4, 3, 2, 1, 0. The final 0 confirms the pattern. The trap is assuming the terms keep growing and picking 2880.

Let m men and w women be eligible, m + w = 300. Money given = 750 × (8/9)m + 1000 × (2/3)w = (2000/3)m + (2000/3)w = (2000/3)(m + w) = (2000/3) × 300 = 2,00,000. The split between men and women does not matter. Answer: (B) 2,00,000.

Concept: The per-person effective amounts happen to be equal (750 × 8/9 = 1000 × 2/3), so the total depends only on m + w. The trap is thinking the problem is unsolvable without knowing m and w separately.

p⁻ˣ = 1/q gives pˣ = q. Similarly qʸ = r and rᶻ = p. Substitute: p = rᶻ = (qʸ)ᶻ = q^(yz) = (pˣ)^(yz) = p^(xyz). So p^(xyz) = p¹, giving xyz = 1. Answer: (C) 1.

Concept: Chained exponent substitution: rewrite each relation without negatives and substitute back to the starting base. The trap is getting lost in the reciprocals and choosing -1 or 1/(pqr).

Take 100 invited guests: 60 male, 40 female. Attendees = 80. All 40 females attended, so males attending = 80 - 40 = 40. Ratio of males to females = 40 : 40 = 1 : 1. Answer: (B) 1:1.

Concept: Assume a convenient total (100) for percentage problems. The trap is applying 80% to males alone (48 males, ratio 6:5) instead of to all guests.

Triangle EAB: ∠DEC = 180° - ∠BAD - ∠ABC. Triangle FAD: ∠BFC = 180° - ∠BAD - ∠ADC. Adding: ∠DEC + ∠BFC = 360° - 2∠BAD - (∠ABC + ∠ADC). In quadrilateral ABCD, ∠ABC + ∠ADC = 360° - ∠BAD - ∠BCD. Substituting: ∠DEC + ∠BFC = 360° - 2∠BAD - 360° + ∠BAD + ∠BCD = ∠BCD - ∠BAD. Answer: (A).

Concept: Angle sums in overlapping triangles combined with the quadrilateral angle sum of 360°. The trap is adding instead of subtracting ∠BAD, since it appears in both triangles and once in the quadrilateral.

P(green) = 2/3, P(red) = 1/3. P(k green in 7) = C(7,k)(2/3)^k(1/3)^(7-k), proportional to C(7,k) · 2^k. k=3: 35 × 8 = 280. k=4: 35 × 16 = 560. k=5: 21 × 32 = 672. k=6: 7 × 64 = 448. The largest is k = 5. Answer: (C) Five green faces and two red faces.

Concept: Binomial mode: compare C(n,k)p^k q^(n-k) across k (mode is near (n+1)p = 5.33, so k = 5). The trap is picking six green because green is more likely per roll, ignoring the C(7,k) factor.

Σ aₙxⁿ = 2 Σ n xⁿ + 3 Σ xⁿ. Known forms: Σ xⁿ = 1/(1 - x), Σ n xⁿ = x/(1 - x)². So G(x) = 2x/(1 - x)² + 3/(1 - x) = [2x + 3(1 - x)]/(1 - x)² = (3 - x)/(1 - x)². Check: at x = 0 this gives 3 = a₀. Answer: (D).

Concept: Uses the standard generating functions for 1 and n and linearity. A quick check is G(0) = a₀ = 3, which eliminates (B) and (C). The trap is forgetting to bring 3/(1 - x) to the common denominator.

The struct holds three chars x = '1', y = '0', z = 'a' + 2 = 'c'. Chars have no padding between them, so (char*)q points at x, (char*)q + 1 at y and (char*)q + 2 at z. %c prints the character itself without quotes: 0 and c. Output: 0, c. Answer: (A).

Concept: Casting a struct pointer to char* and doing byte arithmetic; 'a'+2 is evaluated as the character 'c'. Traps: thinking %c prints quotes, or that 'a'+2 is stored as text.

Enqueue at the head: create a node, point its next to the old head, update head. θ(1). Dequeue at the tail: the last node must be removed and tail moved to its predecessor, but a singly linked list has no back pointer, so we must walk from head to the second-last node. θ(n). Answer: (B) θ(1), θ(n).

Concept: Deleting from the end of a singly linked list needs the predecessor, which costs a traversal even with a tail pointer. The trap is assuming the tail pointer alone makes deletion O(1); it only makes insertion at the tail O(1).

(A) XNOR is the complement of XOR: correct. (B) Complementing one input of XOR complements the output: P̄ ⊕ Q = ¬(P ⊕ Q) = P ⊙ Q: correct. (C) Complementing both inputs leaves XOR unchanged: correct. (D) Left: P ⊕ P̄ = 1, and 1 ⊕ Q = Q̄. Right: P ⊙ P̄ = 0, and 0 ⊙ Q̄ = ¬(0 ⊕ Q̄) = ¬Q̄ = Q. Q̄ ≠ Q, so (D) is NOT correct. Answer: (D).

Concept: XOR/XNOR identities: x ⊕ 1 = x̄, x ⊙ 0 = x̄, and complementing one input flips the result. The trap is mis-evaluating 0 ⊙ Q̄; XNOR with 0 inverts its other input.

RISC uses a load-store architecture, so arithmetic operates only on registers (I). Instructions have a fixed length to simplify fetch, decode and pipelining (II). The small, simple instruction set allows a fast hardwired control unit instead of microprogramming (III). All three are RISC characteristics. Answer: (D) I, II and III.

Concept: RISC traits: load-store, fixed-length simple instructions, hardwired control, many registers, pipelining. Microprogrammed control and variable-length formats are CISC traits. The trap is thinking hardwired control is optional for RISC.

The subset construction turns an n-state NFA into a DFA whose states are subsets of the NFA's states, at most 2ⁿ of them. The minimal DFA can be no larger than this DFA, so k ≤ 2ⁿ always. k can be much smaller than n (an NFA can have redundant states), so (A) and (B) fail, and some languages need exactly 2ⁿ states, so (C) fails. Answer: (D) k ≤ 2ⁿ.

Concept: Subset construction gives the 2ⁿ upper bound; there is no lower bound in terms of n because the NFA itself may be non-minimal. The trap is reading the exponential blow-up as always happening (k ≥ 2ⁿ).

(A) False: the complement of the halting language is not RE. (B) True: run the two recognizing TMs in parallel (or one after the other) and accept when both accept. (C) False: recursive languages are a subset of RE, not the other way round. (D) False: each RE language has a Turing machine, and TMs can be encoded as finite strings, so there are only countably many. Answer: (B).

Concept: RE languages are closed under union and intersection but not complement. The number of TMs is countable, so RE is countable. The trap is reversing the subset relation between recursive and RE.

(A) True: lexical rules are regular, and every regular language is context-free. (B) False: type checking is part of semantic analysis, which works on the parse tree produced by the parser, so it is done after parsing. (C) True: three-address code, syntax trees, SSA and so on. (D) True: activation records on the stack commonly hold arguments. Answer: (B).

Concept: Compiler phase order: lexical analysis, parsing, semantic analysis (type checking), IR generation. The trap is option (A); CFGs can describe tokens because regular is a subset of context-free, even though lexers use regular expressions in practice.

Interrupts are checked at instruction boundaries, so the current instruction finishes first (Q). The state of L is saved on the stack (P) before the PC is overwritten with the ISR address (T). The ISR runs (R), and on return the saved status is popped (S). Order: Q P T R S. Answer: (A).

Concept: Interrupt handling sequence: complete instruction, save context, vector to ISR, run ISR, restore context. The trap is (D), loading the new PC before saving the old state, which would lose L's return address.

Let p be the page fault rate. Effective access time X = (1 - p)M + pD = M + p(D - M). Solving, p = (X - M)/(D - M). Sanity check: X = M gives p = 0 and X = D gives p = 1. Answer: (B).

Concept: Effective memory access time is a weighted average of hit and fault times. The trap is inverting the fraction; checking the limits p = 0 and p = 1 catches it immediately.

Many-to-one from E1 to E2 means each E1 entity relates to at most one E2 entity; total participation of E1 makes it at least one, so exactly one (A true, B false). Since |E1| > |E2| and every E1 entity maps into E2, by pigeonhole some E2 entity is associated with more than one E1 entity, so (C) and (D) are false. Answer: (A).

Concept: Combining mapping cardinality (at most one) with total participation (at least one) gives exactly one. The trap is reading "many-to-one" backwards and picking (B).

The inner join returns the matching rows. The left outer join adds Book rows with no match (copies NULL); the right outer join adds Stock rows with no match (B.isbn NULL). The full outer join contains the matching rows plus both sets of unmatched rows, so it always contains the output of each of the other three. Answer: (D) Query 4.

Concept: FULL OUTER JOIN = INNER JOIN rows plus unmatched rows from both sides, so it is a superset of LEFT, RIGHT and INNER joins. The trap is choosing LEFT or RIGHT, which each miss the other side's unmatched rows.

UDP port numbers are 16 bits (P-IV). An Ethernet MAC address is 48 bits (Q-I). The IPv6 Next Header field is 8 bits (R-II). The TCP sequence number is 32 bits (S-III). Answer: (C) P-IV, Q-I, R-II, S-III.

Concept: Recall of standard header field sizes. Ports are 16 bits (0 to 65535), MAC 48, TCP sequence 32, IPv6 Next Header 8 (it plays the role of IPv4's Protocol field). The trap is confusing the 8-bit Next Header with the 32-bit sequence number.

In slow start, cwnd grows by 1 MSS for every ACK received, so (i) and (ii) are false. If cwnd is W segments, one RTT brings about W ACKs and adds W MSS, so cwnd roughly doubles each RTT: (iv) true. Growth of 1 MSS per RTT is congestion avoidance (additive increase), not slow start, so (iii) is false. Answer: (C) Only (iv) is true.

Concept: Slow start is exponential per RTT (+1 MSS per ACK); congestion avoidance is linear (+1 MSS per RTT). The trap is mixing the per-ACK and per-RTT descriptions of the two phases.

A trial is a tie when both show the same number: P(tie) = 6/36 = 1/6, so P(someone wins) = 5/6. Winning on the third trial needs ties on trials 1 and 2 and no tie on trial 3: (1/6)(1/6)(5/6) = 5/216 ≈ 0.0231. Answer: 0.023 (accepted range 0.021 to 0.024).

Concept: A geometric distribution: first success on trial k has probability (1 - p)^(k-1) p with p = 5/6. The trap is computing the probability that a particular person (say P) wins, which would halve the answer.

Substitute u = x², du = 2x dx. The limits become 0 to (π/4)² = π²/16. Integral = (1/2)∫₀^(π²/16) cos u du = (1/2) sin(π²/16). With π = 3.14: π² = 9.8596, π²/16 = 0.61623 rad, sin(0.61623) ≈ 0.5780. Value ≈ 0.289. Answer: 0.289 (accepted range 0.27 to 0.30).

Concept: Simple substitution; the derivative of x² appears in the integrand. Traps: forgetting to change the upper limit to (π/4)², and evaluating the sine in degrees instead of radians.

A = uvᵀ = [[1, 1], [2, 2]]. It has rank 1, so one eigenvalue is 0. The other equals the trace, 1 + 2 = 3 (equivalently vᵀu = 1 + 2 = 3, since A u = u(vᵀu) = 3u). Eigenvalues are 0 and 3. Answer: 3.

Concept: An outer product uvᵀ has rank 1; its only nonzero eigenvalue is vᵀu with eigenvector u. The trap is confusing uvᵀ (a 2×2 matrix) with vᵀu (a scalar) when forming A.

a, b, c form a triangle (a-b, b-c, a-c), so at least 3 colours are needed. A 3-colouring exists: a = 1, b = 2, c = 3; e (adjacent to a, c) = 2; d (adjacent to b, c) = 1; f (adjacent to b, d, e, which use 2, 1, 2) = 3. Every edge joins different colours. Chromatic number = 3.

Concept: Lower bound from a clique (here a triangle), upper bound from an explicit colouring. The trap is stopping at the lower bound without checking that 3 colours suffice, or assuming 4 because the graph looks dense.

By Lagrange's theorem the order of a subgroup divides 84. The proper divisors of 84 are 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, and the largest is 42. It is attained, for example the cyclic group Z₈₄ has a subgroup of order 42 (generated by 2). Answer: 42.

Concept: Lagrange's theorem limits subgroup orders to divisors of the group order; a proper subgroup excludes the whole group. The trap is answering 84 (not proper) or thinking the bound may not be reachable.

The last postorder element, 1, is the root. Inorder splits into left {8,6,9,4,7,2,5} and right {3}. In the left part the postorder ends with 2, so 2 is its root, with left {8,6,9,4,7} and right {5}. Next root is 4, with left {8,6,9} and right {7}. Then 6 is the root of {8,6,9}, with children 8 and 9. Longest path: 1-2-4-6-8, which has 4 edges. Answer: 4.

Concept: Rebuild the tree recursively: postorder gives the root (last element), inorder splits left and right subtrees. The trap is counting nodes (5) instead of edges, since height here is a path length.

Each call increments counter once. Calls: calc(4, 81) calls calc(4, 27), which calls calc(4, 9), which calls calc(4, 3); that one hits b == 3 and returns. That is 4 calls in total, so counter = 4 and the program prints 4. (The returned value overflows int, but it is never printed.) Answer: 4.

Concept: Count recursive calls, not the computed value: b goes 81, 27, 9, 3. The trap is getting distracted by the cube computations or stopping the count before the base-case call.

This is a 2-bit shift register. State (Q1, Q2); on a clock edge the next state is (in, Q1). A self-loop needs (in, Q1) = (Q1, Q2), that is Q1 = Q2 and in = Q1. State 00 stays 00 on in = 0, state 11 stays 11 on in = 1. State 01 goes to 00 or 10, and 10 goes to 01 or 11, never itself. So 2 states have a self-loop. Answer: 2.

Concept: Derive next-state equations from the D inputs and check which states can map to themselves. The trap is assuming every state can hold its value, as with an enable-controlled register.

Each chip is 256M × 4 bits = 128 MB, so 1 GB needs 8 chips, and a 32-bit word needs 32/4 = 8 chips side by side: all 8 form one bank and are refreshed in parallel. Refreshing all 2¹⁴ rows takes 16384 × 50 ns = 819.2 µs in every 2 ms. Fraction spent refreshing = 0.8192/2 = 40.96%. Available = 59.04%, about 59. Answer: 59 (accepted range 59 to 60).

Concept: Refresh overhead = rows × refresh time / refresh period, with chips in a bank refreshed together. The trap is multiplying by the number of chips, as though they refreshed one after another.

The worst case is every process holding K - 1 instances and waiting for one more. Deadlock is impossible if even then one instance is free: 3(K - 1) + 1 ≤ 4, so K ≤ 2. With K = 3, two processes could hold 2 each, leaving 0 free, and both wait forever. Answer: 2.

Concept: For n processes each needing at most K of R instances, deadlock freedom needs n(K - 1) + 1 ≤ R. The trap is using n × K ≤ R, which is sufficient but far too strict.

TCP numbers bytes with a 32-bit sequence number, so 2³² bytes are sent before a number repeats. At 10⁹ bits/s = 1.25 × 10⁸ bytes/s, the wrap-around time = 2³² / 1.25 × 10⁸ = 4294967296 / 125000000 ≈ 34.36 s. Answer: 34 (accepted range 34 to 35).

Concept: Sequence-number wrap-around time = 2³² bytes / bandwidth in bytes per second. The trap is forgetting that sequence numbers count bytes, not bits (which gives about 4.3 s).

P is 2×2 with only one independent eigenvector. Two distinct eigenvalues would give two independent eigenvectors, so the eigenvalue is repeated (II true). Diagonalization needs 2 independent eigenvectors, so P cannot be diagonalized (III true). Invertibility depends on whether the repeated eigenvalue is 0. With N = [[4, -1], [16, -4]] (N² = 0, only eigenvectors multiples of [1, 4]ᵀ), P = N is singular but P = 2I + N is invertible, and both satisfy the condition, so (I) is not necessarily true. Answer: (D).

Concept: Geometric multiplicity 1 in a 2×2 matrix forces algebraic multiplicity 2 and a defective (non-diagonalizable) matrix. The trap is assuming singularity; a matrix is singular only if 0 is an eigenvalue.

P: rationals are countable (enumerate p/q by |p| + q). Q: a function from {0, 1} to N is a pair (f(0), f(1)), so Q is in bijection with N × N, which is countable. R: functions N → {0, 1} correspond to subsets of N (characteristic functions), i.e. the power set of N, which is uncountable by Cantor's diagonal argument. S: finite subsets of N can be listed by size and largest element (a countable union of finite sets), so countable. Answer: (D) P, Q and S only.

Concept: Finite products and countable unions of countable sets are countable; the power set of N (or infinite binary sequences) is not. The trap is confusing functions from {0, 1} to N with functions from N to {0, 1}.

In the 7-element model pick witnesses a, b, c for s, t, u. Restrict the model to the universe {a, b, c} (at most 3 elements), keeping the predicates' truth values on these elements. With no function symbols this restriction is a valid structure. ψ(a, b, c, v, w, x, y) held for all v, w, x, y in the large universe, so it holds in particular for all choices from {a, b, c}, since ψ is quantifier-free and its truth depends only on the chosen elements. Hence the restriction is a model of φ of size at most 3. Answer: (A).

Concept: Universal sentences are preserved under substructures, and an ∃³∀* sentence (Bernays-Schönfinkel class) has a model of size at most the number of existential variables. Options (B), (C), (D) cannot be guaranteed. The trap is thinking the 7-element model fixes the size.

fun1 receives copies of the pointers and swaps only its local copies, so str1 and str2 in main are unchanged: prints "Hi Bye ". fun2 receives the addresses of str1 and str2 and swaps the pointers they hold, so now str1 points to "Bye" and str2 to "Hi": prints "Bye Hi". Output: Hi Bye Bye Hi. Answer: (A).

Concept: C passes everything by value; to change a caller's pointer you must pass a pointer to it (char**). The trap is believing fun1 swaps because it takes pointers.

(I) In an undirected DFS, when an edge (u, v) is examined from u and v is unvisited, v becomes a descendant of u; if v is already visited it must be an ancestor or descendant, since u's subtree is finished before DFS backs out. So every non-tree edge is a back edge and there are no cross edges: true. (II) In BFS, edge endpoints differ in depth by at most 1, but can be at the same depth: in a triangle x-y-z rooted at x, y and z are both at depth 1 and the edge y-z has |i - j| = 0. False. Answer: (A) I only.

Concept: Undirected DFS has only tree and back edges; BFS non-tree edges join the same or adjacent levels. The trap is reading BFS's "at most 1" as "exactly 1".

Dimensions p = 2, 25, 3, 16, 1, 1000. Pairs: m12 = 150, m23 = 1200, m34 = 48, m45 = 16000. m13 = min(150 + 96, 1200 + 800) = 246. m24 = min(48 + 75, 1200 + 400) = 123, via F₂(F₃F₄). m35 = min(16000 + 48000, 48 + 3000) = 3048. m14 = min(123 + 50, 150 + 48 + 6, 246 + 32) = 173, via F₁(F₂(F₃F₄)). m15: split after F₄ gives 173 + 2·1·1000 = 2173; after F₂ gives 150 + 3048 + 6000 = 9198; others are larger. Optimum ((F₁(F₂(F₃F₄)))F₅) = 2173. The only directly multiplied adjacent pair is F₃F₄. Answer: (C).

Concept: Matrix chain multiplication DP. The 16×1 and 1×1000 shapes make it cheap to collapse everything to a 2×1 matrix first, then multiply by F₅ once. The trap is greedily multiplying the cheapest-looking pairs, such as F₁F₂.

First loop: i halves from 2⁴⁰ down to 1, running 40 times, so j = 40 (j = log₂ n). Second loop: j goes 40 → 20 → 10 → 5 → 2 → 1, incrementing sum each time while j > 1: 5 iterations. sum = 5 (that is floor(log₂ 40)). Answer: (B) 5.

Concept: Nested logarithms: the result is floor(log₂(log₂ n)). The trap is computing log₂ 40 ≈ 5.3 and rounding to 6, or stopping the trace one step early.

5 integer bits give 0 to 31, and 3 fraction bits give multiples of 1/8 = 0.125. (i) 31.5 = 11111.100: representable. (ii) 0.875 = 7/8 = 00000.111: representable. (iii) 0.1 is not a multiple of 1/8, so 12.1 is not exact. (iv) 0.001 is not a multiple of 1/8, so 3.001 is not exact. Answer: (C) Only (iii) and (iv) cannot be exactly represented.

Concept: With f fraction bits, exactly representable fractions are multiples of 2^(-f). The trap is thinking 31.5 overflows; 31 is exactly the 5-bit maximum.

Block size = 2ᴹ words × 2ᵂ bytes = 2^(M+W) bytes, so the offset is M + W bits. Number of blocks = 2^(N-M-W); number of sets = 2^(N-M-W)/K, so the set index is N - M - W - log₂K bits. Tag = P - (N - M - W - log₂K) - (M + W) = P - N + log₂K. Answer: (B).

Concept: Address = tag + set index + block offset; higher associativity means fewer sets and a longer tag. The trap is the sign of log₂K, or forgetting to convert block size from words to bytes.

I: the condition is m - n + p - q = 0. A PDA keeps a signed counter on the stack (push for a and c, pop for b and d, switching to a negative marker when the count goes below zero) and accepts if it ends at zero: CFL. II: aᵐbᵐ followed by cᵖdᵖ is the concatenation of two CFLs: CFL. III: requires m = n = p, i.e. it contains the comparison aⁿbⁿcⁿ, which a single stack cannot do (pumping lemma): not CFL. IV: mn = p + q needs multiplication of two counts: not CFL. Answer: (B) I and II only.

Concept: A PDA can do one linear count (including signed sums) or nested matching, but not three-way equality or products. The trap is thinking I needs two stacks because it mentions four counts.

(I) Membership for unrestricted (type-0) grammars is equivalent to TM acceptance: undecidable. (II) Regularity of L(M) for a TM is a non-trivial semantic property: undecidable by Rice's theorem. (III) Equivalence of grammars is undecidable even for context-free grammars, so for arbitrary grammars too. (IV) An NFA accepts a regular language, and every regular language is accepted by some DPDA (a DFA is a DPDA that ignores its stack), so the answer is always yes: decidable. Answer: (D) Only I, II and III are undecidable.

Concept: Rice's theorem for TM language properties; CFG equivalence is undecidable. The trap is (IV): it sounds like a hard question about DPDAs, but its answer is always yes, which makes it trivially decidable.

Input bbaacabc. Longest matches from the start: T₂ matches "bb" (length 2); T₁ matches "bba" ((b|c)* = bb, then a; length 3); T₃ matches "bbaac" (c? empty, (b|a)* = bbaa, then c; length 5). Longest is T₃ on "bbaac". Remaining "abc": T₁ matches only "a" (length 1), T₂ matches "ab" (length 2), T₃ matches "abc" ((b|a)* = ab, then c; length 3). Longest is T₃. Output: T₃T₃. Answer: (D).

Concept: Maximal munch: at each position try all patterns and take the longest match. The trap is committing to the first pattern that matches (T₁ or T₂ on "bb...") instead of checking which one reaches furthest.

Operators lower in the tree are applied first. The $ operations (b $ c, then $ d) sit below every #, so $ binds tighter: $ has higher precedence. b$c$d is grouped as (b $ c) $ d, so $ is left associative. The # operations group as a # (X # (e # f)), each # taking the rest of the expression on its right, so # is right associative. Answer: (A).

Concept: Reading precedence and associativity from a parse tree: deeper means higher precedence; a left-leaning chain means left associative, a right-leaning chain means right associative. The trap is reading associativity of # from the top-level split alone.

Need = Max - Allocation: P₀ (3,3,0), P₁ (1,0,2), P₂ (0,3,0), P₃ (3,4,1). Available (3,3,0). P₀'s need (3,3,0) fits; it finishes and releases (1,0,1): Available (4,3,1). P₂ needs (0,3,0): fits; releases (1,0,3): Available (5,3,4). P₁ needs (1,0,2): fits; releases (1,1,2): Available (6,4,6). P₃ needs (3,4,1): fits. Safe sequence P₀, P₂, P₁, P₃ exists, so the state is safe. Answer: (A).

Concept: Banker's safety algorithm: compute Need, then repeatedly run any process whose Need fits Available and reclaim its Allocation. The trap is comparing Max (not Need) with Available, which makes the state look unsafe.

Here the names are swapped from the textbook: full (initial N) counts free slots and empty (initial 0) counts filled slots. The producer must wait for a free slot, wait(full), so P = full, and after adding announce a filled slot, signal(empty), so Q = empty. The consumer waits for a filled slot, wait(empty), so R = empty, and then frees a slot, signal(full), so S = full. Answer: (C).

Concept: Bounded-buffer pattern: each side waits on the counter of what it consumes and signals the counter of what it produces. The trap is going by the usual names; read the initial values and definitions given in the question.

Q returns the r tuples with B < 5 joined with their s tuple. Because r.B is a foreign key into s, every r tuple has a matching s tuple, so r LOJ s = r ⋈ s. (A) Selection pushed past the join on the join attribute: equivalent. (B) r LOJ s = r ⋈ s, then select: equivalent. (D) σ_(B<5)(r) LOJ s = σ_(B<5)(r) ⋈ s: equivalent. (C) r LOJ σ_(B<5)(s) keeps every r tuple with B ≥ 5 too, padded with C = NULL, so it has extra rows: NOT equivalent. Answer: (C).

Concept: Foreign keys guarantee matches, so a left outer join from the referencing side behaves like a natural join, unless the referenced side is filtered first. The trap is assuming the filter position never matters in outer joins.

I: a set-valued attribute violates 1NF, so it is not in 3NF. II: candidate keys are {rollno, courseid} and {email, courseid}. email → rollno has a non-superkey left side, so not BCNF, but rollno is a prime attribute, so 3NF holds. III: marks → grade is a transitive dependency of a non-prime attribute: not 3NF. IV: courseid → credit is a partial dependency: not even 2NF. Answer: (B) Schema II.

Concept: 3NF allows X → A with X not a superkey only when A is prime; BCNF does not. The classic 3NF-not-BCNF case is a non-key attribute determining part of a key. The trap is missing the second candidate key {email, courseid}.

A permutation of 100 numbers has 99 adjacent positions, and each adjacent swap gives a different permutation, so every vertex has degree y = 99. Any permutation can be sorted by adjacent swaps (bubble sort), so every vertex is connected to the identity permutation: the graph is connected, z = 1. y + 10z = 99 + 10 = 109. Answer: 109.

Concept: Adjacent transpositions generate all permutations, which is why bubble sort always works. The trap is counting all C(100,2) swaps for the degree, or thinking parity splits the graph into two components (that happens only if moves preserve parity, and adjacent swaps flip it).

Total probability: P(H_D) = 0.2 × 0.40 + 0.5 × 0.10 + 0.3 × 0.01 = 0.08 + 0.05 + 0.003 = 0.133. Bayes: P(H_G | H_D) = P(H_D | H_G) P(H_G) / P(H_D) = 0.08 / 0.133 ≈ 0.6015. Answer: 0.60 (accepted range 0.60 to 0.62).

Concept: Bayes' theorem with the law of total probability for the denominator. The trap is answering 0.40, which is P(H_D | H_G), the reverse conditional.

For a fixed y ≠ 1, x halves from 1024 down to 1, printing once for each x in 1024, 512, ..., 2: that is 10 prints. When x reaches 1, y drops by one and x resets to 1024. This repeats for y = 1024, 1023, ..., 2, which is 1023 values; at y = 1 the function stops without printing. Total = 1023 × 10 = 10230. Answer: 10230.

Concept: Nested iteration written as recursion: an outer counter y and an inner halving x (log₂ 1024 = 10 prints). The trap is using 1024 rounds instead of 1023, since y = 1 prints nothing.

A 7-node heap is a complete tree: a root with two subtrees of 3 nodes each. The root must be 1. Choose which 3 of the remaining 6 values go to the left subtree: C(6,3) = 20. In a 3-node subtree the smallest value must be its root and the other two can be in either order: 2 ways for each subtree. Total = 20 × 2 × 2 = 80. Answer: 80.

Concept: Recurrence H(n) = C(n - 1, L) × H(L) × H(R), where L and R are the fixed subtree sizes of the complete tree. The trap is forcing 2 and 3 to be the root's children; 3 can sit below 2 in the same subtree.

Edges T-B (1) and T-C (3) are the two cheapest and form no cycle, so every MST contains them. Vertex A joins through T-A or A-B, both weight 4, giving 2 choices (B-C, also 4, would close the cycle T-B-C and is never needed). Vertex R joins only through T-R (x) or C-R (5). If x = 5 both are equally cheap, giving 2 choices; any other x gives 1. Maximum number of MSTs = 2 × 2 = 4 with x = 5. Answer: 4.

Concept: Multiple MSTs arise from ties among the cheapest edges crossing a cut. Choosing x equal to the competing edge (5) creates a tie for R. The trap is counting B-C as a third option for A; it never crosses the cut that separates A.

Ratios: item 4 = 12, item 1 = 6, item 3 = 5, item 2 = 4. Greedy takes item 4 (2 kg, 24); item 1 (10 kg) would make 12 kg, so it is skipped; item 3 (4 kg) fits, total 6 kg, 44; item 2 (7 kg) would make 13 kg, skipped. V_greedy = 44. Optimal: item 1 alone gives 60; no other item fits with it (10 + 2 = 12). Other subsets: 2 + 4 = 52, 2 + 3 = 48, 3 + 4 = 44. V_opt = 60. Difference = 60 - 44 = 16. Answer: 16.

Concept: Greedy by value/weight is optimal only for fractional knapsack; 0/1 knapsack needs DP or exhaustive search. The trap is letting greedy stop at the first item that does not fit; it continues down the list.

Prime implicants (using don't cares): Q'S' = {0, 2, 8, 10}; PQ' = {8, 9, 10, 11}; Q'R = {2, 3, 10, 11}; P'QS = {5, 7}; P'RS = {3, 7}; PS' = {8, 10, 12, 14} (only don't cares plus none of the minterms, so irrelevant). Minterm 0 is covered only by Q'S', minterm 5 only by P'QS, and minterm 9 only by PQ', so these three are essential. Together they cover 0, 2, 5, 7, 9, 11, i.e. the whole function. Number of essential prime implicants = 3.

Concept: An essential prime implicant is the only prime implicant covering some required minterm; don't cares help form implicants but never need covering. The trap is counting implicants made only of don't cares, or treating don't-care cells as minterms that make a prime essential.

PO is the only multi-cycle stage, and the 1-cycle stages before it always have the next instruction ready, so PO is busy continuously once it starts. The first instruction spends 3 cycles in IF, ID, OF before reaching PO. PO then needs 40 × 3 + 35 × 2 + 25 × 1 = 120 + 70 + 25 = 215 cycles for all instructions back to back. The last instruction needs 1 more cycle in WB. Total = 3 + 215 + 1 = 219. Answer: 219.

Concept: With one variable-latency stage, total time = fill time before it + sum of its busy times + drain time after it. The trap is using the standard (k + n - 1) formula with the slowest stage time, which gives 3 × 104 = 312.

An integer register needs 4 bits, a floating point register 6 bits; there are 2¹⁶ = 65536 encodings. Type-1: 4 instructions × 2¹² operand combinations = 16384. Type-2: 8 × 2¹² = 32768. Type-3: 14 × 2¹⁰ = 14336. Used = 63488, leaving 65536 - 63488 = 2048 encodings. Each Type-4 instruction uses 2⁶ = 64 encodings, so N = 2048 / 64 = 32. Answer: 32.

Concept: Expanding-opcode problems are solved by counting encodings: each instruction consumes 2^(operand bits) codes out of 2^(instruction length). The trap is assigning fixed opcode widths per category instead of counting the shared code space.

Accepted strings: ε (at q0) and strings of odd length (ending at q1), so L₁ = {ε} ∪ {0^(2j+1) | j ≥ 0}. L⁰ = {ε}, which differs from L¹. L¹ = L₁ lacks even-length strings of length ≥ 2. L² = L₁ · L₁ contains ε, every odd string (odd · ε) and every even string of length ≥ 2 (odd · odd), so L² = 0*. Then L³ = L² · L₁ = 0*. The smallest k with Lᵏ = Lᵏ⁺¹ is 2. Answer: 2.

Concept: Powers of a language containing ε form an increasing chain; the order is where the chain stabilises. The trap is answering 1 by missing that ε ∈ L₁ means L¹ ⊆ L², and checking whether they are actually equal (they are not, since 00 ∉ L₁).

Cylinders requested: 72, 134, 20, 86, 116, 16. SSTF from 80: 86 (6), then 72 (14), then 116 (44, closer than 20 at 52), then 134 (18), then 20 (114), then 16 (4). Total movement = 6 + 14 + 44 + 18 + 114 + 4 = 200 cylinders, costing 200/100 × 20 = 40 mW. Direction: up to 86 (already moving up), down to 72 (reversal 1), up to 116 and 134 (reversal 2), down to 20 and 16 (reversal 3). Reversals cost 3 × 15 = 45 mW. Total = 40 + 45 = 85. Answer: 85.

Concept: SSTF picks the nearest pending cylinder each time; sector and platter numbers are distractors here. The trap is miscounting reversals: the initial move to 86 continues the current upward direction, so it is not a reversal.

IP payload = 4500 - 20 = 4480 bytes (the TCP header is part of the IP payload). Each fragment may carry at most 600 - 20 = 580 bytes, rounded down to a multiple of 8: 576 bytes. Offsets are stored in 8-byte units: fragment 1 starts at byte 0 (offset 0), fragment 2 at byte 576 (offset 72), fragment 3 at byte 1152 (offset 144). Answer: 144.

Concept: Fragment data sizes must be multiples of 8 (except the last), and the offset field counts 8-byte units. Traps: subtracting the TCP header from every fragment, or reporting the byte offset 1152 instead of 144.

Q senses the medium from t = 0 to t = 5. To avoid colliding it must detect P's signal within that window, after which it defers until P finishes. P's signal reaches Q at t = d/10. The condition d/10 ≤ 5 gives d ≤ 50 m. For any larger d, Q hears nothing during sensing, starts transmitting and collides with P's 20-unit transmission. Answer: 50.

Concept: Carrier sensing only works if the other station's signal arrives within the sensing interval: propagation delay ≤ sensing time. The trap is involving the 20-unit transmission time, which matters for collision detection but not for this deferral condition.