GATE 2026 CS (Computer Science) Session 1 question paper with solutions

A protagonist is the leading character of a story, the one the plot follows. The word for the character who opposes the protagonist is antagonist. Agnostic (one unsure about God), arsonist (one who sets fires) and anarchist (one who rejects authority) are unrelated. Answer: (B) antagonist.

Concept: Vocabulary: antonyms built on the same root. 'Pro-' (for) versus 'anti-' (against) attached to 'agonist' (contender). The distractors all end in -ist to look similar.

Every game eliminates exactly one player. To leave one winner out of 64 players, 63 players must be eliminated, so 63 games are played (32 + 16 + 8 + 4 + 2 + 1 = 63). Answer: (C) 63.

Concept: Counting by elimination: in a knock-out with n players, n - 1 games. The trap is 64 (one game per player) or 32 (only the first round).

Maximum total = 70 credits. Fixed: core 15 + project 20 = 35. Specialization at least 10, so take exactly 10 to leave room. Electives at most 70 - 35 - 10 = 25. Answer: (D) 25.

Concept: Maximising one quantity under constraints: push the total to its upper bound and every other component to its lower bound. The 60-credit minimum is irrelevant to the maximum.

The statement is: teacher in room -> all students stand silently. (A) is its contrapositive, so true. (B) and (D) follow because 'stand silently' includes both 'silent' and 'standing'. (C) says all standing -> teacher in room, which is the converse; students could stand while the teacher is absent. Answer: (C).

Concept: Implication p -> q is equivalent to its contrapositive (not q -> not p) but not to its converse (q -> p). The converse is the classic trap.

The passage says combinatorial counting is 'sometimes used' in modeling physical phenomena, so P ('always invoked') is not supported: P is False. It also says that in such models probabilities are assigned to combinatorial possibilities, which enables computing average values of physical quantities: that is exactly Q, so Q is True. Answer: (B) P is False and Q is True.

Concept: Inference questions punish absolute words. 'Always' in P contradicts 'sometimes' in the passage; Q is a restatement of the last sentences.

H₁₀(S) is 0 up to S = 10 and then S - 10 (slope 1). H₂₀(S) is 0 up to S = 20 and then S - 20. For (A): S ≤ 10 gives 0; 10 < S ≤ 20 gives S - 10, rising from 0 to 10; S > 20 gives (S - 10) - (S - 20) = 10. This matches the plot. (B) falls after 20, (C) is negative, (D) starts rising at 15. Answer: (A) H₁₀(S) - H₂₀(S).

Concept: A ramp-then-flat shape is the difference of two shifted 'hinge' functions: the first switches the slope on, the second cancels it. Same idea as a bull call spread payoff.

Neeraj's round-2 throw is the best overall. Vesely's best throw came in rounds 1-4 (he never improved after round 4) but not in rounds 1-2 (no medal throws there), so round 3 or 4. In round 4 Jakub's throw was the best of the round. If Vesely's best were in round 4, Jakub's round-4 throw would exceed it, putting Jakub ahead of Vesely after four rounds, so Vesely could not be second. Hence Vesely's best was in round 3. Answer: (A) Third.

Concept: Ordering puzzle: combine 'best in round 4' with 'second after four rounds'. Students often pick Fourth by not noticing Jakub's round-4 throw beats any Vesely throw that round.

Count ordered pairs (first, second) with second a multiple of first. First = 1: 6 pairs; 2: (2,4,6) 3; 3: (3,6) 2; 4: 1; 5: 1; 6: 1. Total 14 of 36. Probability = 14/36 = 7/18. Answer: (C) 7/18.

Concept: Enumerate favourable outcomes of two independent rolls. A number is a multiple of itself, so pairs like (4,4) count; forgetting them gives 5/18 or less.

Start R=1, B=1. Step 1: red with prob 1/2 gives (2,1); blue gives (1,2). After step 2 there are 4 balls; equal means (2,2). From (2,1), pick blue with prob 1/3 -> (2,2). From (1,2), pick red with prob 1/3 -> (2,2). P = 1/2 x 1/3 + 1/2 x 1/3 = 1/3. Answer: (B) 1/3.

Concept: Polya urn with conditional probabilities along a two-step tree. The composition after k steps is uniform over {1,...,k+1} red balls, here 1, 2 or 3 each with probability 1/3. The trap is assuming each pick is 1/2.

Fill the top-left 3 × 3 block freely: 2⁹ ways. The last entry of each of the first three rows is forced to make the row parity even; the last entry of each of the first three columns is forced likewise. The bottom-right entry is then forced by row 4, and it automatically makes column 4 even too, because the total number of 1s is even from both views. So the count is 2⁹ = 512. Answer: (A) 512.

Concept: Parity-constrained counting: an n × n binary matrix with all row and column sums even has 2^((n-1)²) choices. Options near 2¹⁰ tempt those who think only rows constrain.

The characteristic polynomial of an n × n matrix has degree n, so the sum of algebraic multiplicities of all eigenvalues is n, and one eigenvalue can take all of it. Example: the identity matrix I has eigenvalue 1 with multiplicity n. Answer: (A) n.

Concept: Multiplicity is bounded by the degree of the characteristic polynomial. n + 1 is impossible; 1 confuses this with distinct-eigenvalue matrices.

Immediate: the operand value is inside the instruction, i.e. a constant (P-4). Indirect: the instruction names a location that holds the address of the operand, i.e. a pointer (Q-2). Base with index: base = array start, index register = variable subscript, i.e. array element (R-1). Base with fixed offset: base = record start, constant displacement = field offset, i.e. record element (S-3). Answer: (B) P-4, Q-2, R-1, S-3.

Concept: Addressing modes map to high-level constructs. The trap is mixing index (variable offset, arrays) with displacement (fixed offset, struct fields).

In a load-store architecture only LOAD and STORE access memory; ALU instructions operate on registers only. (A), (B) and (C) all give an ALU instruction a memory operand, which is not allowed. (D) loads X and Y into registers, adds register to register, then stores the result to Z. Answer: (D).

Concept: Load-store (RISC) ISAs forbid memory operands in arithmetic instructions. Options that look shorter are tempting but violate that rule.

A data hazard arises when an instruction needs a value that an earlier instruction has not yet produced: a read after write (true dependence). Read-after-read never conflicts since nothing changes. WAR and WAW are name dependences that cannot cause a hazard in the standard in-order pipeline where reads happen in an early stage and writes in the last stage, in program order. Answer: (B) Read-after-write.

Concept: RAW is the true data dependence. WAR/WAW matter only with out-of-order execution or writes in different stages; RAR is never a hazard.

T₂: a = 5, b = 4, n^(log₄ 5) ≈ n^1.16, which dominates log n polynomially, so T₂(n) = Θ(n^(log₄ 5)) by Master theorem case 1. T₁: a = 4, b = 2, n^(log₂ 4) = n². The driving term n^1.16 is polynomially smaller than n², so case 1 again: T₁(n) = Θ(n²). Answer: (A) T₁(n) = Θ(n²).

Concept: Nested Master theorem: solve the inner recurrence first, then use it as f(n). Options (C)/(D) are the trap of reporting T₂ instead of T₁, since log₄ 5 < 2.

TCP uses a three-way handshake, not two-way (A false). Either side may send FIN first (B false). TCP is full-duplex (C false). Both sides can send FIN at the same moment; TCP defines simultaneous close (both go FIN_WAIT_1 -> CLOSING -> TIME_WAIT). Answer: (D).

Concept: TCP connection management: three-way open, full-duplex data, and a close that either side or both at once may start. Simultaneous close is a defined state transition.

HTTP 1.1 uses persistent connections: one TCP connection to a server carries many requests, so multiple objects (A) and multiple pages (D) from the same server can share it. A TCP connection is between two hosts, so objects on a different server need another connection (B false). HTTP 1.1 supports pipelining: send the next request before the previous response completes (C true). Answer: (A), (C), (D).

Concept: Persistent connections and pipelining are the HTTP 1.1 features. The trap is (B): a TCP connection cannot span servers.

M·e₂ = 0 with e₂ ≠ 0, so M has a non-trivial null space and is singular: det M = 0 (B true, A false). Rank is at most n - 1 but need not be 1, e.g. M with a zero second column and identity elsewhere has rank n - 1 (C false). The null space is a subspace containing e₂, so it also contains 2e₂, -e₂ and so on: at least two non-zero vectors (D true). Answer: (B), (D).

Concept: A non-zero null vector means singular, det 0. Any non-trivial subspace contains infinitely many vectors; (C) confuses 'rank deficient' with 'rank 1'.

Truth table (P,Q): (0,0): P̄+Q = 1, P̄Q = 0, F = 1. (0,1): 1 xor 1 = 0. (1,0): 0 xor 0 = 0. (1,1): 1 xor 0 = 1. So F = 1 exactly when P = Q: F is XNOR, the complement of P ⊕ Q. Complementing one input of XOR gives XNOR, so P̄ ⊕ Q also equals F. Complementing both inputs gives back P ⊕ Q. Answer: (A), (C).

Concept: XOR identities: x̄ ⊕ y = complement of (x ⊕ y), and x̄ ⊕ ȳ = x ⊕ y. A four-row truth table settles it faster than algebra.

8-bit sign-magnitude range is -127 to +127. X: sign 1, magnitude 0110100 = 52, so X = -52. Y: sign 0, magnitude 1001100 = 76, so Y = 76. X + Y = 24 (fine). X - Y = -128 (overflow). -X + Y = 128 (overflow). -X - Y = -24 (fine). Answer: (B), (C).

Concept: Sign-magnitude has two zeros and no -128, unlike two's complement. Students who use the two's-complement range think -128 fits.

In a 1-indexed heap, node i has a left child 2i if 2i ≤ n. Internal nodes are 1..floor(n/2); leaves are floor(n/2)+1..n. For odd n, floor(n/2) = (n - 1)/2, so leaves start at (n + 1)/2. Hence (n - 1)/2 and (n - 3)/2 are internal; (n + 1)/2 and n are leaves. Answer: (B), (C).

Concept: Heap array indexing: a node is a leaf iff 2i > n. The question asks for NON-leaves; misreading that flips the answer.

1 -> 8. 13 -> 20 mod 11 = 9. 22 -> 29 mod 11 = 7. 15 -> 22 mod 11 = 0. 11 -> 18 mod 11 = 7, occupied; probe 8, 9 occupied; 10 free. 24 -> 31 mod 11 = 9, occupied; 10, 0 occupied; 1 free. Occupied: 0, 1, 7, 8, 9, 10. Of the options only position 2 is empty. Answer: (C) 2.

Concept: Linear probing wraps around from the last slot to slot 0, which is how 24 ends up at 1. Forgetting the wrap leaves 1 wrongly empty.

abb via S → aSbS: either the first S → bS → b and the second S → ε (a·b·b·ε), or the first S → ε and the second S → bS → b (a·ε·b·b). Two parse trees, so (B) and (A) are true. abab via S → aSbS needs a w b w' = abab. w = ε, w' = ab works (ab = aεbε). w = ba would need S ⇒ ba, impossible since every a produced is followed later by its b. So only one parse tree and one rightmost derivation (C true). Every CFL is decidable (D false). Answer: (A), (B), (C).

Concept: Ambiguity means two parse trees (equivalently two leftmost or two rightmost derivations) for one string. Membership of any CFL is decidable via CYK.

Subset construction turns an n-state NFA into a DFA with at most 2ⁿ states; the minimal DFA is no larger. With n = 6, at most 2⁶ = 64 states. 32 and 1 are achievable (1 for Σ* or ∅), but 65 and 128 exceed 64. Answer: (B), (D).

Concept: The 2ⁿ blow-up bound of subset construction. The minimal DFA can be much smaller than the NFA, so small numbers are always possible.

S1 opens a string literal that never closes on the line: the lexer cannot form a valid token, a lexical error. S2 is a valid string literal "Hello;" followed by ';': no error. S3 is syntactically a valid declaration but assigns a char* (string literal) to an int*: a type mismatch, found during semantic analysis. Answer: (C) S1 has a lexical error and S3 has a semantic error.

Concept: Classify errors by compiler phase: bad tokens are lexical, bad structure is syntactic, type rules are semantic. The ';' inside quotes in S2 is just a character.

LL(1) is predictive and never backtracks (A false). An LL(1) grammar cannot be left-recursive (B false). Common prefixes make two productions share a FIRST symbol, so an LL(1) grammar must be left-factored (C true). Every LL(1) grammar is not necessarily SLR and vice versa, and LR-family parsers are in general the more powerful; LL(1) is not more powerful than SLR (D false). Answer: (C).

Concept: LL(1) prerequisites: no left recursion, left-factored, disjoint FIRST/FOLLOW sets. Bottom-up parsers handle left recursion that LL(1) cannot.

(A) Banker's algorithm is deadlock avoidance (grants only requests that keep a safe state), not prevention: FALSE. (B) Denying hold-and-wait removes a necessary condition, which is prevention: true. (C) An assignment edge goes from a resource to a process; a request edge goes from process to resource: FALSE. (D) A safe state has a safe sequence in which all processes can finish: true. Answer: (A), (C).

Concept: Prevention breaks a Coffman condition; avoidance (Banker's) checks safety at run time. Edge direction in RAG: request P -> R, assignment R -> P.

(A) P → R says nothing about Q alone; counterexample: Q constant across tuples with different R. False. (B) A composite determinant need not have a single-attribute determinant (e.g. date and room determine booking). False. (C) Augment P → R with Q: PQ → RQ, so PQ → R; similarly PQ → S; union gives PQ → RS. True. (D) Augmentation (or adding attributes to the left side) preserves the FD: PQ → R. True. Answer: (C), (D).

Concept: Armstrong's axioms: you may enlarge the left side (augmentation) but never shrink it. (A) and (B) both try to shrink a determinant.

3NF synthesis always yields a lossless, dependency-preserving decomposition (A true). Any relation is in 1NF already (atomic values), so the trivial decomposition preserves all dependencies (B true). BCNF decomposition is always lossless but may lose dependencies, e.g. R(A,B,C) with AB → C, C → B (C true). Since a 3NF dependency-preserving decomposition always exists and 3NF implies 2NF, a dependency-preserving 2NF decomposition always exists, so (D) is false. Answer: (A), (B), (C).

Concept: Dependency preservation is guaranteed up to 3NF and can fail only at BCNF. (D) is false because the 3NF result is also in 2NF.

For x > 0, f(x) = c₁eˣ - c₂ ln(1/x) = c₁eˣ + c₂ ln x. As x → 0⁺, ln x → -∞, so the right limit is finite only if c₂ = 0. Then the right limit is c₁e⁰ = c₁. Continuity at 0 needs c₁ = f(0) = 3. So c₁ + c₂ = 3 + 0 = 3. Answer: 3.

Concept: A one-sided limit must be finite and equal to f(0). The log term diverges, forcing its coefficient to zero; missing that leaves the problem looking underdetermined.

A full binary tree (every node has 0 or 2 children) with n nodes has (n - 1)/2 = 11 internal nodes. Height is maximised by a 'caterpillar' where each level has one internal node and one leaf, so each internal node adds one edge of depth. Height = number of internal nodes = 11. Answer: 11.

Concept: Full binary tree facts: internal i, leaves i + 1, n = 2i + 1. Maximum height is i, minimum is about log₂ n. Do not confuse with a complete tree.

func is called with i = 9, j = 10. Since 9 < 10 the block runs, but it declares a new local int i that shadows the parameter; the loop changes only that inner i (and j). When the block ends the inner i goes out of scope, and printf uses the parameter i, still 9. Answer: 9.

Concept: Block scope and shadowing in C. The trap is answering 10 by assuming the loop modified the parameter i.

Worst case: every process holds one instance and waits for its second. With k = 5 all five hold one each and none can proceed: deadlock. With k = 6, after each holds one, one instance remains; some process gets its second, finishes and releases two, and the rest follow. Generally k ≥ Σ(maxᵢ - 1) + 1 = 5 × 1 + 1 = 6. Answer: 6.

Concept: Deadlock-freedom bound: give each process one less than its maximum, then add one. Answering 10 (everyone's full maximum) is the usual over-count.

X = 0011 0101 1100 0...: sign 0, exponent 01101011 = 107, fraction .1000 -> X = 1.1₂ × 2^(107-127) = 1.5 × 2⁻²⁰. Y = 0011 0100 1010 0...: exponent 01101001 = 105, fraction .0100 -> Y = 1.01₂ × 2⁻²² = 0.0101₂ × 2⁻²⁰. Sum: 1.1000₂ + 0.0101₂ = 1.1101₂, so Z = 1.1101₂ × 2⁻²⁰, exponent field 107 = 01101011, fraction 1101 0... Bits: 0 01101011 1101000... = 0011 0101 1110 1000 0... = 35E80000. Answer: (C) 35E80000.

Concept: IEEE 754 addition: align the smaller operand's significand to the larger exponent (including the hidden 1), add, renormalise. Forgetting the hidden bit of Y gives 35C80000-style answers.

For D flip-flops D = next state. D1 = 1 on rows (P Q1 Q0) 001, 010, 011, 111. P̄Q1 covers 010, 011; P̄Q0 covers 001, 011; Q1Q0 covers 011, 111. Union = {001, 010, 011, 111}, exact. D0 = 1 on rows 000, 010, 011, 110. P̄Q̄0 covers 000, 010; P̄Q1 covers 010, 011; Q1Q̄0 covers 010, 110. Union = {000, 010, 011, 110}, exact. Option (B) matches both; (A) has PQ1, which would set D1 at 110 where it must be 0. Answer: (B).

Concept: With D flip-flops the excitation equals the next-state column, so this is just two 3-variable K-maps. Check each candidate term against the 0 rows to eliminate options fast.

Offset = log₂128 = 7 bits. Lines = 2²³/2⁷ = 2¹⁶. Direct mapped: index 16 bits, tag M = 32 - 16 - 7 = 9. K-way with K = 2^L: sets = 2¹⁶/2^L, index 16 - L bits, tag N = 32 - (16 - L) - 7 = 9 + L. So N = M + L. Answer: (A) N = M + L.

Concept: Doubling associativity halves the number of sets: one index bit moves into the tag. The trap is adding K (the number of ways) instead of log₂K.

The base case returns 1, so it must fire at the last node: head->next == NULL. The recursive case counts this node and recurses on the rest: 1 + getListSize(head->next). Option (C) returns 1 for an empty list and over-counts by one (and with head == NULL it would return 1 at the end, giving n + 1). Options (A) and (D) recurse on head itself and never terminate. Answer: (B).

Concept: Recursive list length: the base case must match the return value. Returning 1 means stop at the last node, not at NULL.

A complete BST on 1..15 is the perfect tree with root 8, level-2 nodes 4 and 12, level-3 nodes 2, 6, 10, 14, leaves the odd numbers. In any insertion order a parent must be inserted before its children, so the first element is 8 and the second is 4 or 12. The third is either the other of 4/12 or a child of the second (2 or 6 if second is 4; 10 or 14 if second is 12). So the third element is in {2, 4, 6, 10, 12, 14}. 5 is a leaf, needing 8, 4 and 6 before it. Answer: (D) 5.

Concept: BST shape is fixed by the set of ancestors inserted first. Count how many ancestors an element has: a node at depth d can appear no earlier than position d + 1.

S1: every path of length at most k is also of length at most k + 1, so the minimum over the larger set cannot be larger: true. S2: weights are integers and may be negative. Let s-u have weight 5 and u-v weight -3 with no other edges. The shortest s to v path is s-u-v using (u, v), with weight 2. For k = 2, d₂(u) = 5 > d₂(v) = 2. Also for k = 1, d₁(v) = ∞ while d₁(u) = 5, but the k = 2 case already breaks S2. So S2 is false. Answer: (A) Only S1 is true.

Concept: Hop-bounded distances (as in Bellman-Ford rounds) are monotone non-increasing in k. 'Predecessor is closer' fails once negative edges are allowed, which 'integer weights' quietly permits.

An expression is redundant at a point if it is available: computed on every path reaching it with no later redefinition of its operands. g * k: computed in B2 and in B3, and neither g nor k is redefined afterwards, so it is available at B4 entry: redundant in B4. b + i: computed in B1, but B3 redefines b, so on the B3 path it is killed: not redundant. c + m: computed in B3 only, not on the path B1 → B2 → B4, so not available at B5: not redundant. Answer: (D) B4: { g * k }, B5: { }.

Concept: Global CSE uses available-expressions analysis, an all-paths (intersection) problem. Traps: b + i looks repeated but b is reassigned; c + m appears earlier but only on one branch.

⟨u, v⟩ ∈ R binds u to P and v to Q. ⟨v, w⟩ ∈ S binds the same v to X. So we need R tuples whose Q value equals some S tuple's X value, and we output P. That is Π_P(R ⋈_(R.Q = S.X) S), and join is commutative, so Π_P(S ⋈_(S.X = R.Q) R). Answer: (B).

Concept: Translate shared variables into join conditions by position. The trap is joining on P (the projected attribute) or on S.Y (the existentially discarded w).

In slow start the window starts at 1 segment and doubles each RTT (ssthresh 10000 is never reached here). Segments sent in RTT round k (starting at time k ms) are numbered 2ᵏ to 2ᵏ⁺¹ - 1: round 0 sends 1, round 1 sends 2-3, round 2 sends 4-7, and so on. Segment 2000 lies in 1024..2047, which is round 10, so its transmission starts at some time in [10, 11) ms. Answer: (B) 10 ≤ t < 11.

Concept: Slow start doubles cwnd per RTT, so the cumulative segments after k rounds are 2ᵏ - 1. Off-by-one errors in numbering the rounds give (A) or (C).

Transmission time per frame Tt = 1000 bits / 100 kbps = 10 ms. Propagation delay Tp = 100 ms. For 100% utilisation the sender must keep transmitting until the first ACK arrives, which is after Tt + 2Tp = 210 ms. Window W ≥ 210/10 = 21 frames. Answer: (B) 21.

Concept: Sliding window efficiency = W·Tt / (Tt + 2Tp). Forgetting the first frame's own Tt gives 20; using one-way delay gives 11.

f(x) = -(x - |x|/2)². For x ≥ 0: x - x/2 = x/2, so f = -x²/4. For x < 0: x + x/2 = 3x/2, so f = -9x²/4. f(0) = 0 and f < 0 elsewhere: local (global) maximum at 0, no local minimum. f′(x) = -x/2 for x > 0, -9x/2 for x < 0, and both one-sided derivatives at 0 are 0, so f′ is continuous. f″ is -1/2 on the right and -9/2 on the left, so f′ is not differentiable at 0. Answer: (A), (C), (D).

Concept: Split |x| into cases. A function can be C¹ but not C²: matching slopes at the joint, different curvatures. Students often assume an |x| term breaks f′ itself.

(A) If v ∉ S, every edge at v must be covered by its other endpoint, so all of v's at least k + 1 neighbours are in S, giving |S| ≥ k + 1, a contradiction. So v ∈ S. (B) Path a-b-c: k = 1, S = {b}; a lies on the path of length 2 but a ∉ S. (C) Triangle: k = 2, S = {a, b}; c is on the 3-cycle but c ∉ S. (D) Single edge u-v: k = 1, S = {u}; v is a clique of size 1 but v ∉ S. Answer: (A).

Concept: Classic kernel rule from parameterised vertex cover (Buss): a vertex of degree > k must be in every cover of size k. Small counterexamples kill the other options.

Essential prime implicants: P̄S = {1, 3, 5, 7} (only cover of 1 and 7) and QR̄ = {4, 5, 12, 13} (only cover of 4 and 13). Left: 2, 10, 14. Prime implicants covering them: P̄Q̄R {2, 3}, Q̄RS̄ {2, 10}, PRS̄ {10, 14}, PQS̄ {12, 14}. RS̄ would need 6, which is absent, so two more terms are required. Covers: P̄Q̄R + PRS̄ (2, 10, 14) and Q̄RS̄ + PQS̄ (2, 10, 14) both work with 3 literals each. (A) misses 14, (C) misses 2. Answer: (B), (D).

Concept: Pick essential prime implicants first, then solve the remaining cover. Multiple minimal SOPs exist when the leftover minterms can be paired in more than one way.

(A) Cycle property: with distinct weights the heaviest edge on any cycle is in no MST. True. (B) False: vertices a, b, c, d with ab = 5, bc = 6, ca = 7, ad = 1, db = 2. In cycle a-b-c, ab is the lightest, but ab is the heaviest on cycle a-b-d, so it is in no MST. (C) False: if v has degree 1, its only edge is both the heaviest and lightest at v and must be in every MST. (D) Cut property on the cut ({v}, V - {v}): the lightest crossing edge is in every MST. True. Answer: (A), (D).

Concept: Cycle property excludes the heaviest edge of a cycle; cut property includes the lightest edge across a cut. The lightest edge of a cycle has no such guarantee.

By the parenthesis theorem, two DFS intervals are either nested or disjoint, so the overlapping pattern (D) can never occur in any graph. (A): v nested in u, a tree or forward edge, fine in a DAG. (C): v finished before u was discovered, a cross edge, fine. (B): u nested inside v means u is a descendant of v, so (u, v) is a back edge, which implies a cycle, impossible in a DAG. Answer: (B), (D).

Concept: Parenthesis theorem plus edge classification: a directed graph is acyclic iff DFS finds no back edge. That is also why reverse finishing order is a topological sort.

Take L₂ = ∅ (regular). Then L₁ ∩ L₂ = ∅ is regular for every L₁, so L₁ can be non-regular, or even not context-free (e.g. {aⁿbⁿcⁿ}). That falsifies (A), (D), and (B) since L₁ ∪ ∅ = L₁. Regular languages are closed under complement, so the complement of L₂ is regular and hence context-free: (C) is always true. Answer: (C).

Concept: Knowing L₁ ∩ L₂ says nothing about the part of L₁ outside L₂. Choosing L₂ = ∅ is the quick counterexample; every regular language is context-free.

B always derives aᵐbᵐ (m ≥ 1): equal numbers of a and b. Each A-rule adds terminals with exactly one more a than b (aaBBAb: 2 a, 1 b; bBabaa: 3 a, 2 b) plus balanced Bs, and every A-derivation ends with bBabaa, so each A-string has a-surplus ≥ 1. S → abaABAbba: the frame aba...bba is balanced (3 a, 3 b), B is balanced, and there are two As, so n₁ - n₂ ≥ 2 and n₁ > n₂ always: (B) true, (A) false. For the ratio, every piece satisfies a ≤ 2b: frame 3 ≤ 6, B m ≤ 2m, aaBBAb terminals 2 ≤ 2, bBabaa terminals 3 ≤ 4. Summing, n₁ ≤ 2n₂ for every string: (D) true, (C) false. (Shortest string: 12 a, 10 b.) Answer: (B), (D).

Concept: Count letters per production instead of generating strings: track the a-minus-b surplus each rule adds. Balanced sub-derivations (B gives aᵐbᵐ) can be ignored for the difference.

G1: D → T V with V → V id | id gives T id id ... id (one or more ids). G2: D → D id | T id gives the same T id⁺. So P = Q (A true). In SDD2, D.type and T.type are both computed from children only: synthesized, S-attributed (B true). In SDD1, V.type is inherited (from parent D or V), but T.type and D.type are synthesized, so SDD1 is L-attributed but does not contain only inherited attributes (C false). Both put every id with the declared type, so the symbol table gets the same entries (D true). Answer: (A), (B), (D).

Concept: Synthesized attributes flow up from children; inherited ones flow down or across from parent/left siblings. SDD1 mixes both, so 'only inherited' is the trap.

The TLB caches only translations of resident pages, so a TLB hit implies a valid page table entry: 'TLB hit, page table miss' can never happen (B). A page table miss (page fault) means the page is not in memory; since evicting a page invalidates its cache blocks and the cache is physically addressed, no block of that page can hit: 'TLB miss, page table miss, cache hit' can never happen (C). (A) is a normal TLB miss on a resident, cached page. (D) is a page fault followed by a cache miss after the page is brought in. Answer: (B), (C).

Concept: Order of lookups: TLB, then page table, then physically addressed cache. A page fault implies nothing about that page can be in the TLB or (here) the cache.

2-colorable means bipartite, and a graph is bipartite iff it has no odd cycle: (A) false. Even cycles such as C₄ are bipartite: (B) true. BFS or DFS colouring alternately and checking every edge decides it in Θ(|V| + |E|) with adjacency lists, and every vertex and edge must be read, so this is optimal: (C) true, (D) false. Answer: (B), (C).

Concept: Bipartite iff no odd cycle; test by BFS layering in linear time. The log factor in (D) belongs to sorting or heap-based algorithms, not to this check.

6000 addresses need the next power of two, 8192 = 2¹³, so a /19 block. The ISP owns 202.16.0.0/15 = 202.16.0.0 to 202.17.255.255. A /19 block must start where the third octet is a multiple of 32 (2¹³ = 32 × 256). 202.16.0.0 (0) valid; 202.17.64.0 (64) valid; 202.16.32.0 (32) valid; 202.17.24.0 (24) is not a multiple of 32, so not a valid /19 boundary. Answer: (A), (B), (C).

Concept: A CIDR block must be aligned to its own size. Check both containment in the parent block and alignment; (D) fails on alignment.

Let M(n) be the number of matchings (including the empty one) in a path on n vertices. For the last vertex: either it is unmatched, giving M(n - 1), or it is matched with its neighbour, giving M(n - 2). So M(n) = M(n - 1) + M(n - 2) with M(1) = 1, M(2) = 2. Sequence: 1, 2, 3, 5, 8, 13, 21, 34. M(8) = 34. Answer: 34.

Concept: Matchings in a path follow the Fibonacci recurrence. The usual trap is forgetting the empty matching (giving 33) or counting only maximum matchings.

Probabilities sum to 4/6 + 4/12 = 1. E[X] = (1 + 2 + 5 + 7)/6 + (3 + 4 + 6 + 8)/12 = 15/6 + 21/12 = 2.5 + 1.75 = 4.25. Answer: 4.25.

Concept: Expectation of a discrete random variable is Σ x·p(x). Grouping values with equal probability keeps the arithmetic short.

15000 rpm gives one rotation in 4 ms, so average rotational latency = 2 ms and transfer of one sector = 4/400 = 0.01 ms. Seek: track 0 → 5 = 5 ms, 5 → 12 = 7 ms, 12 → 7 = 5 ms, total 17 ms. Each of the 30 randomly located sectors costs an average latency plus its transfer: 30 × (2 + 0.01) = 60.3 ms. Total = 17 + 60.3 = 77.3 ms. Answer: 77.3.

Concept: Disk access = seek + rotational latency + transfer. Random sectors on the same track each pay half a rotation on average; sector size in bytes is a distractor.

With a 1 ns clock, an instruction occupies EX for ceil(t_EX) cycles, stalling the following instruction for ceil(t_EX) - 1 cycles. LOAD 2 cycles: 1 × 15 = 15. IMUL 2: 1 × 10 = 10. IDIV 3: 2 × 5 = 10. FADD 2: 1 × 10 = 10. FSUB 2: 1 × 5 = 5. FMUL 3: 2 × 15 = 30. FDIV 4: 3 × 5 = 15. Others 1 cycle: 0. Total = 15 + 10 + 10 + 10 + 5 + 30 + 15 = 95. Answer: 95.

Concept: A multi-cycle, non-pipelined functional unit is a structural hazard: extra cycles = ceil(t/clock) - 1 per instruction. Rounding 1.5 or 2.5 down is the usual slip.

bar(n) = floor(log₂ n). foo(1) = 1 and foo(n) = 1 + foo(floor(log₂ n)). Smallest n with foo = 2: need bar(n) = 1, n = 2. foo = 3: bar(n) = 2 (smallest m with foo(m) = 2), n = 4. foo = 4: bar(n) = 4, n = 2⁴ = 16. foo = 5: bar(n) = 16, n = 2¹⁶ = 65536. Answer: 65536.

Concept: foo counts how many times floor(log₂) must be applied to reach 1 (an iterated logarithm). Working backwards from the base case gives a tower of powers of two.

Build the BST from the preorder: root 50; left subtree from 25, 13, 40, 30, 47 (25 with left 13 and right 40, 40 with children 30 and 47); right subtree from 75, 60, 70, 80, 77 (75 with left 60 whose right child is 70, and right 80 whose left child is 77). Postorder: 13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50. 60 is at position 7. Answer: 7.

Concept: Preorder of a BST determines the tree: the first element is the root, smaller elements form the left subtree. Postorder lists children before parents.

At each iteration the parent (fork returns non-zero) breaks out and prints; only the child continues to the next iteration. i = 0: original forks, original prints (1). i = 1: child 1 forks, child 1 prints (2). i = 2: child 2 forks, child 2 prints (3). Child 3 continues, i becomes 3, loop ends, child 3 prints (4). This is a chain of 4 processes, each printing once. Answer: 4.

Concept: fork() returns 0 in the child. Here only children keep looping, giving a chain rather than a tree; assuming 2³ = 8 processes is the trap.

FCFS order by arrival: A10, C11, A20, C22, A30, C33, A40, C44, A50, C55. Start/finish: A10 10-16 (wait 0), C11 16-24 (5), A20 24-30 (4), C22 30-38 (8), A30 38-44 (8), C33 44-52 (11), A40 52-58 (12), C44 58-66 (14), A50 66-72 (16), C55 72-80 (17). Total waiting = 95. Average = 95/10 = 9.5 s. Answer: 9.5.

Concept: Waiting time = start time - arrival time under FCFS (non-preemptive). A Gantt chart avoids errors; the CPU is never idle here, so queueing builds up.

A superkey must contain a candidate key: it must include A and at least one of B, C. Choices for {B, C}: {B}, {C}, {B, C} (3 ways); D in or out (2 ways). Total 3 × 2 = 6: AB, AC, ABC, ABD, ACD, ABCD. Check by inclusion-exclusion: 2² + 2² - 2¹ = 6. Answer: 6.

Concept: Superkeys = supersets of some candidate key; count with inclusion-exclusion over the keys. Double-counting supersets of both AB and AC (ABC, ABCD) gives 8.