GATE 2024 CS (Computer Science) Session 2 question paper with solutions

Walk, jog and sprint are the same action at rising intensity. The second series must go from mildly troubled (bothered) to intimidated into losing courage (daunted). 'Fazed' means disturbed or disconcerted - stronger than bothered, weaker than daunted. 'Phased' (done in stages), 'phrased' (worded) and 'fused' (joined) are sound-alike distractors with unrelated meanings. Answer: (C) fazed.

Concept: Intensity analogy combined with a homophone trap: phased, fazed and phrased sound alike, but only 'fazed' belongs to the bothered-daunted scale. Read the meaning, not the sound.

Each wizard mixes all four elements in every possible order, so each tries every permutation of 4 distinct items: 4! = 4 × 3 × 2 × 1 = 24. They work independently, so each makes 24 attempts on his own (the combined 48 is not asked). Answer: (A) 24.

Concept: Order matters, so this is a permutation count 4!. The trap is doubling to 48 for two wizards - the question asks for attempts by each wizard.

Students who like at least one = 10,000 − 1,500 = 8,500. Let O = students liking other branches and C = O/4 liking core branches. By inclusion-exclusion, C + O − 500 = 8,500, so O/4 + O = 9,000, giving 5O/4 = 9,000, O = 7,200 and C = 1,800. Answer: (A) 1,800.

Concept: Two-set inclusion-exclusion: |C ∪ O| = |C| + |O| − |C ∩ O|. Forgetting to account for the 500 who like both gives a wrong total.

The right side is (1/2) ln(xy) = ln √(xy). So ln((x + y)/2) = ln √(xy), giving (x + y)/2 = √(xy). The arithmetic mean equals the geometric mean only when x = y (equivalently (√x − √y)² = 0). Then x/y + y/x = 1 + 1 = 2. Answer: (C) 2.

Concept: Log rules turn the equation into AM = GM, whose equality case forces x = y. Spotting the equality case avoids messy algebra.

Differences of the known terms: 9 − 6 = 3, 14 − 9 = 5, and 41 − 30 = 11. The differences are consecutive odd numbers 3, 5, 7, 9, 11. So x = 14 + 7 = 21, and indeed 30 − 21 = 9. Answer: (B) 21.

Concept: First-difference pattern (consecutive odd numbers). Check that the chosen value also fits the gap to the next term.

S opens the story with a time marker ('Many millennia ago') and introduces the collision. P refers back to it as 'this fortuitous geological event' and describes the rocks rising. R refers to 'this massive edifice' (the risen rock mass) cooling. Q begins with 'Thus' and draws the conclusion. Order: S P R Q. Answer: (C) SPRQ.

Concept: Para-jumble: find the opener with no back-reference, then chain demonstratives ('this event', 'this edifice') to their antecedents; a 'Thus' sentence concludes, it does not open.

Let each selling price be 99. Cost of the first item = 99/1.1 = 90; cost of the second = 99/0.9 = 110. Total cost 200, total selling price 198. Loss = 2 on 200 = 1%. In general the loss is (10/10)² % = 1%. Answer: (C) 1% loss.

Concept: Equal selling prices with equal percentage profit and loss always give a net loss of (x/10)² %. The trap is assuming the profit and loss cancel.

Renewable share in 2007 = 30 + 5 + 5 = 40%. In 2023 = 35 + 20 + 10 = 65%. Since the total is unchanged, the increase is (65 − 40)/40 × 100 = 25/40 × 100 = 62.5%. Answer: (D) 62.5%.

Concept: Percentage increase is relative to the starting value. Reporting the 25 percentage-point rise as 25% is the trap (option A).

Each full straight cut can at most double the number of pieces (pieces are not rearranged), so at least 3 cuts are needed since 2³ = 8. Three mutually perpendicular cuts through the centre, parallel to the three pairs of faces, give 8 identical smaller cubes. Answer: (A) 3.

Concept: Spatial reasoning: three orthogonal planes through the centre split a cube into 8 congruent cubes; fewer than 3 cuts cannot produce 8 pieces.

Row 3 is 3, X, 6, X and row 4 has no crosses. Count the non-X neighbours of each row-4 cell. Cell (4,1): neighbours (3,1), (3,2)=X, (4,2) - count 2. Cell (4,2): (3,1), (3,2)=X, (3,3), (4,1), (4,3) - count 4. Cell (4,3): (3,2)=X, (3,3), (3,4)=X, (4,2), (4,4) - count 3. Cell (4,4): (3,3), (3,4)=X, (4,3) - count 2. Sum = 2 + 4 + 3 + 2 = 11. Answer: (A) 11.

Concept: Neighbour counting with diagonals included. Only row 3 and row 4 matter for the last row; the usual slips are dropping diagonal neighbours or counting the X cells.

Processor cycles per second = 4 × 10⁶. DMA steals 1% of them: 4 × 10⁴ cycles per second. Each cycle moves 8 bytes = 64 bits. Rate = 4 × 10⁴ × 64 = 2,560,000 bits per second, written in Indian digit grouping as 25,60,000. Answer: (C) 25,60,000.

Concept: Cycle-stealing DMA rate = fraction of cycles × clock rate × bits per cycle. Traps: forgetting to convert bytes to bits, or misreading the Indian digit grouping in the options.

"A when B" means "if B then A". Here B = student scores more than 50% marks (q) and A = fail grade cannot be given (¬p). So the statement is q → ¬p. Answer: (A) q → ¬p.

Concept: Translating 'when'/'if' clauses: the condition after 'when' is the antecedent. The trap is reversing the implication or dropping the negation.

Evaluating f's arguments right to left: h(20) runs first and prints 20, then g(10) prints 10. Output so far: 2010. Inside f, x = 10 and y = 20; g(x) prints 10 and then h(y) prints 20. Full output: 20101020. Answer: (A) 20101020.

Concept: Argument evaluation order (given here as right to left) versus statement order inside the body, which is always sequential. The trap is applying right-to-left to the body too.

Exponent 1111 1111 (255) is reserved: with a non-zero mantissa, option (C) is NaN, not a number at all. Among the valid numbers the larger biased exponent wins. (A) and (D) have exponent 127 (unbiased 0), values 2 − 2⁻²³ and 1.0. (B) has exponent 254 (unbiased 127) with an all-ones mantissa: (2 − 2⁻²³) × 2¹²⁷, the largest finite single-precision value. Answer: (B).

Concept: IEEE 754 special values: exponent all ones means infinity (mantissa 0) or NaN (mantissa non-zero). The trap is picking the all-ones pattern as the largest.

Characteristic equation r² − 5r + 6 = 0 gives r = 2, 3, so T(n) = a·2ⁿ + b·3ⁿ. From T(0) = 1: a + b = 1. From T(1) = 2: 2a + 3b = 2. Subtracting twice the first equation: b = 0, so a = 1. Hence T(n) = 2ⁿ exactly (check: T(2) = 10 − 6 = 4) and T(n) = Θ(2ⁿ). Answer: (A).

Concept: Linear homogeneous recurrence: the initial conditions decide which root survives. The trap is taking the dominant root 3 without solving for the constants, which here make the 3ⁿ coefficient zero.

Let I = ∫₀² f(x) dx. Substituting x → 2 − x gives I = ∫₀² f(2 − x) dx. Adding the two forms: 2I = ∫₀² [f(x) + f(2 − x)] dx = ∫₀² 1 dx = 2. So I = 1. Answer: (B) 1.

Concept: The property ∫ₐᵇ f(x) dx = ∫ₐᵇ f(a + b − x) dx turns the functional equation into a constant integrand.

A is its own inverse means A² = I. Since A is a symmetric 0/1 matrix, the diagonal entry (A²)ᵢᵢ equals the degree of vertex i, so every vertex has degree exactly 1. A graph in which every vertex has degree 1 is a set of disjoint edges covering all vertices - a perfect matching. Conversely, for a perfect matching no two edges share a vertex, so A² = I holds. Answer: (B).

Concept: (A²)ᵢⱼ counts walks of length 2 from i to j; diagonal entries are degrees. A cycle has degree 2 everywhere, so it fails.

Total outcomes = 6⁶ = 46656. Favourable outcomes: the six dice show 1 to 6 in some order, 6! = 720 ways. Probability = 720/46656 = 5/324. Answer: (B) 5/324.

Concept: The dice are distinguishable, so favourable outcomes are permutations (6!), not a single arrangement. Using 1/6⁶ is the trap.

The ACID property that guarantees committed changes survive failures (via the log and redo during recovery) is durability. Atomicity is all-or-nothing execution, consistency is preserving integrity constraints, isolation is non-interference of concurrent transactions. Answer: (A) durability.

Concept: Distinguishing the ACID properties. Durability is about committed work surviving crashes; atomicity is about undoing partial work.

A weak entity cannot be identified without its owner, so every weak entity must take part in the identifying relationship: total participation on the weak side. An owner may have no weak entities at all (an employee with no dependents), so its participation need not be total. Answer: (A).

Concept: Weak entity sets depend on an identifying owner, hence total participation (double line) on the weak side only.

The lexical analyzer produces tokens (P-2). The syntax analyzer builds the parse tree (Q-3). The intermediate code generator works with the abstract syntax tree as an intermediate representation (R-1). Constant folding is a code optimization (S-4). Answer: (B) P - 2; Q - 3; R - 1; S - 4.

Concept: Phases of a compiler and their artefacts. Parse tree versus AST is the usual confusion: the parser gives the concrete parse tree, the AST serves as an intermediate representation.

0 never changes state and 1 toggles between A and B, so the DFA accepts exactly the strings with an odd number of 1s. (A) 0*1(0 + 10*1)*: 0*1 reaches B; each further block 0 stays at B and 10*1 leaves B and returns. It generates exactly the odd-1 strings. (B) generates ε (zero 1s). (C) cannot generate 111. (D) forces a leading 0, so it misses 1. Answer: (A).

Concept: Converting a two-state parity DFA to a regular expression. Testing options on short strings such as ε, 1, 111 and 010 eliminates the wrong ones fast.

The IP destination is end-to-end, so it is Y's IP (B true, A false). The MAC destination is the next layer-3 hop: Y is on another network, so X sends the frame to its gateway R's MAC. A switch is transparent at layer 2 and is never addressed, so neither S's MAC (C) nor Y's MAC (D) is the destination. Answer: (B).

Concept: IP addresses are end-to-end, MAC addresses are hop-by-hop to the next router. Switches never appear as frame destinations.

The MMU is hardware: it uses the page table to translate virtual to physical addresses (B), raises a page-fault trap when the mapping is absent or invalid (C), and raises a protection trap on a write to a read-only page (D). Allocating a page table for a new process is a software task of the OS kernel, so (A) is not the MMU's job. Answer: (B), (C), (D).

Concept: Division of labour: the hardware MMU translates, checks and traps; the OS allocates, sets up tables and handles the traps.

(A) A blocking disk read must wait for I/O, so P is always blocked. (B) The page is in swap space, so it must be read from disk and P blocks until it arrives. (C) The disk interrupt is serviced and the other process becomes ready, but P may simply resume - not always a switch. (D) A timer interrupt preempts P only if its time slice has expired and another process is ready; otherwise P continues. Answer: (A), (B).

Concept: 'Always' is the key word: events that make P wait for I/O always remove it from the CPU; interrupts only sometimes lead to preemption.

A full scan must read every record. In sorted and heap files the records are packed into data pages that are read once each, about B I/Os for B pages. Scanning through an unclustered index fetches records in index order, jumping between data pages, which can cost one I/O per record plus the index pages; a hash index also leaves buckets partly empty. So only sorted and heap files are I/O efficient for a scan. Answer: (A), (B).

Concept: Scan cost depends on physical layout. Unclustered indexes help point or range lookups but make full scans expensive because of random page accesses.

(A) True: every 2PL schedule is conflict serializable (equivalent to the order of lock points). (B) False: releasing right after each operation and locking again later violates the growing/shrinking rule. (C) True: that is the definition of 2PL. (D) True: two transactions each holding one lock and waiting for the other's lock deadlock under basic 2PL. Answer: (A), (C), (D).

Concept: 2PL guarantees serializability but not freedom from deadlock or cascading aborts. Statement B describes short-duration locking, which breaks 2PL.

In IPv4 any router whose outgoing link MTU is smaller than the datagram fragments it (unless DF is set), so A is false and B is true. Fragments may travel different paths, so they are reassembled only at the final destination: C true, D false. Answer: (B), (C).

Concept: IPv4 allows fragmentation inside the network but reassembly only at the destination. Source-only fragmentation is IPv6 behaviour, a common mix-up.

(A) True - the textbook definition of an attribute grammar. (B) False - L-attributed definitions are exactly those that can always be evaluated in one depth-first, left-to-right traversal. (C) True - synthesized attributes are computed at each reduction. (D) False - L-attributed definitions on LL(1) grammars can be evaluated bottom-up (using marker non-terminals), but not every L-attributed definition on an LR(1) grammar can. The FALSE statements are B and D. Answer: (B), (D).

Concept: The question asks for FALSE statements. Key facts: L-attributed means depth-first evaluable; bottom-up evaluation of inherited attributes is guaranteed only for L-attributed SDDs on LL grammars.

(A) x · 1 = x is the identity law - true. (B) x + 1 = 1, not x - false. (C) x · x = x by idempotence, not 0 - false. (D) x + x̄ = 1 is the complement law - true. The FALSE statements are B and C. Answer: (B), (C).

Concept: Basic Boolean identities. Note the question asks for FALSE statements, and option C has x · x (idempotent), not x · x̄.

I1 writes R3 and I2 reads it: RAW on R3 (A true). I1 and I3 both write R3: that is WAW, not WAR (B false). I2 reads R3 and later I3 writes it: WAR, not RAW (C false). I3 writes R3 and I4 reads it: RAW, not WAW (D false). Answer: (A).

Concept: Classify by order of access: write-then-read is RAW, read-then-write is WAR, write-then-write is WAW. Each wrong option names a real dependency with the wrong type.

Every router decrements TTL. Since TTL is covered by the header checksum, the checksum must be recomputed as well. The source address changes only under NAT (not at any router), and the protocol field is never changed in forwarding. Answer: (C), (D).

Concept: The TTL decrement forces a checksum update at each hop. NAT rewriting addresses is neither 'always' nor done by 'any router'.

fX advances b to the terminating null character and returns the pointer difference, i.e. the string length; it is valid C and compiles (C false). A string literal, a char array initialised from a literal, and a char pointer to a literal are all null-terminated, so the loop always stops and fX returns 4 in each case. Answer: (A), (B), (D).

Concept: A strlen written with pointer subtraction. All three forms of "abcd" carry the terminating null, and the function only reads, so none of them misbehaves.

A total order containing P is a linear arrangement with 1 before 2, 3 before 2 and 3 before 4. The first element must be minimal: 1 or 3. If 1 is first, the rest {2,3,4} must have 3 first (it precedes both 2 and 4), then 2 and 4 in either order: 2 orders (1324, 1342). If 3 is first, the rest {1,2,4} only needs 1 before 2: 3!/2 = 3 orders (3124, 3142, 3412). Total = 5. Answer: 5.

Concept: Counting linear extensions of a small poset. Fix the first element among the minimal elements and recurse; forgetting that 3 must also precede 4 overcounts.

The elements kept unchanged must already form a non-decreasing subsequence, and any such subsequence can be kept (integers can fill the gaps since values may repeat). So distance = n − length of the longest non-decreasing subsequence. Here 2, 3, 4, 6 (positions 1, 3, 5, 7) has length 4, and no length-5 non-decreasing subsequence exists. Distance = 7 − 4 = 3 (e.g. 2, 3, 3, 3, 4, 4, 6). Answer: 3.

Concept: Reduces to the longest non-decreasing subsequence. The trap is counting inversions or out-of-place elements instead.

q = p + 1 points to the next double, and pointer subtraction counts elements, not bytes: q − p = 1. *q − *p = 25.0 − 20.0 = 5.0, cast to int gives 5. Both values are ints, so %d prints them correctly: 1,5. Answer: (B) 1,5.

Concept: Pointer arithmetic is scaled by element size: the difference of two double pointers is in elements. The trap is answering 8 (sizeof(double)).

SRTF: A 0-2; B arrives (6 < 8) B 2-4; C arrives (3 < 4) C 4-7; then B (4 left) 7-11; D 11-18; A 18-26. Waiting = completion − arrival − burst: A 26−0−10 = 16, B 11−2−6 = 3, C 7−4−3 = 0, D 18−6−7 = 5. Average 24/4 = 6. NP-SJF: A 0-10; at 10 pick C 10-13, B 13-19, D 19-26. Waiting: A 0, B 11, C 6, D 13. Average 30/4 = 7.5. Answer: (B) SRTF = 6, NP-SJF = 7.5.

Concept: Gantt charts for preemptive vs non-preemptive SJF. In SRTF, re-check at every arrival; in NP-SJF the long first job runs to completion.

The range covers 2 × 256 = 512 addresses = 2⁹, so the prefix length is 32 − 9 = 23. The block must start on a multiple of 512: third octet 2 = 00000010, and 2 is a multiple of 2, so 10.12.2.0/23 covers 10.12.2.0 - 10.12.3.255 exactly. /24 is too small, /22 covers 10.12.0.0 - 10.12.3.255 (too large). Answer: (A) 10.12.2.0/23.

Concept: CIDR block size must be a power of two and aligned to its size. 10.12.2.0/22 is not even a valid block start.

For any BST, the inorder traversal lists the keys in increasing order, so it is just V sorted - independent of insertion order. The shape of T, and hence the root, preorder and postorder, depend on the insertion order (the root is the first inserted element), which is unknown. Answer: (A).

Concept: Inorder of a BST is always the sorted order. Other traversals encode the tree shape, which varies with insertion order.

FIRST(A) = {c, ε}, FIRST(B) = {d, ε}. FIRST(AaAb) = {c, a}, FIRST(BbBa) = {d, b}. So M[S,c] = S → AaAb (1) and M[S,d] = S → BbBa (2). FOLLOW(A): A is followed by a and by b in AaAb, so FOLLOW(A) = {a, b} and A → ε goes in columns a and b: (3) = A → ε. FOLLOW(B) = {b, a} from BbBa, so (4) = B → ε. Answer: (A).

Concept: Filling an LL(1) table: productions go under FIRST of their right side, and ε-productions under FOLLOW of the left side. Forgetting the second occurrence of A (followed by b) leaves (3) blank wrongly.

Via 1 → 2: the 2-3 loop reads pairs, so ending at 2 accepts (00)*. Reaching 3 reads 0(00)*; then ε to 5, and the 5-4 loop on 1 returns to 5 after 11, giving 0(00)*(11)*. Via 1 → 4: reach 5 with 1, then (11)*: 1(11)*. So L = (00)* + 0(00)*(11)* + 1(11)* = (00)* + (1 + 0(00)*)(11)*. Option (B): 0* = (00)* + 0(00)*, and 0(00)* is already inside 0(00)*(11)*, so (B) equals L. (A) misses 0. (C) misses 0 and wrongly accepts 11. (D) misses 00011. Answer: (B).

Concept: Trace ε-closures: the path through state 3 contributes an odd block of 0s followed by pairs of 1s. Checking short strings such as 0, 011, 00011 separates the options.

first is the previous element and second the other value in the current two-value window. If X[i] equals second (not first), the window still has two values, so len2++; but the run of equal values ending at X[i] restarts, so len1 = 1 (P = 1). If X[i] is a new third value, the longest two-value subarray ending at X[i] is the run of the previous value (length len1) plus X[i]: len2 = len1 + 1 (Q). Answer: (B) (P) 1, (Q) len1+1.

Concept: Maintaining run-length invariants. When a new value appears, only the trailing run of the previous value can stay in the window - not the whole old window (len2+1 is the trap).

(1) must fetch s[i] for uminus: an indexed read, written =[] s i. (2) negates it. (3) multiplies (p + r) by −s[i]: * (0) (2). (4) and (5) add u/w. The assignment to x[i] is split into an indexed-store triple that computes the location, []= x i, and triple (7) = (6) (5) assigns the value (5) to it. Answer: (A).

Concept: In triples, an array store x[i] = y needs two triples: []= x i, then an assignment using it. The read s[i] uses =[]. Option C puts (5) inside (6), duplicating (7).

Since 0 ≤ y ≤ 1 and x ≥ 0, z = xy ≤ x always, so E[z] ≤ E[x], i.e. z̄ ≤ x̄ - (D) always holds. The others fail without independence: if x = y uniform on [0,1], z̄ = E[x²] = 1/3 > 1/4 = x̄ȳ, breaking (A) and (B); if y = 1 − x, z̄ = E[x − x²] = 1/6 < 1/4, breaking (C). Answer: (D).

Concept: E[xy] = E[x]E[y] needs independence (zero covariance). Only the pointwise bound xy ≤ x survives for dependent variables.

With no aggregation, 'at least 3 persons' needs three distinct tuples of Person in the same city. Rename three copies P1, P2, P3 and form P1 × P2 × P3 (2 cross products), select P1.city = P2.city = P3.city with P1.pid ≠ P2.pid, P2.pid ≠ P3.pid, P1.pid ≠ P3.pid, and project city. With one cross product only two persons can be compared at once, which cannot certify three. Answer: (B) 2.

Concept: Counting to k without aggregation needs k copies of the relation, i.e. k − 1 cross products, with pairwise inequality on the key.

If T1 enters first: it takes s1, prints 1, then blocks on wait(s2) (s2 = 0) while still holding s1. T2 blocks on wait(s1). Deadlock, T2 prints nothing: (C) possible, (A) impossible. If T2 enters first: it takes s1, prints 1, signals s2 (s2 = 1) and s1. T1 then enters, prints 2, wait(s2) succeeds, signals s1. So (B) possible and (D) impossible. Answer: (B), (C).

Concept: Holding a mutex while waiting on another semaphore that only the blocked thread can signal is a classic deadlock. Trace both entry orders.

(A) A row swap multiplies the determinant by −1 - true. (B) det B = −det A ≠ 0, so B is invertible - true. (C) False: A = [[1,2],[2,3]] is symmetric, but swapping its rows gives B = [[2,3],[1,2]], which is not. (D) False: A = [[0,1],[1,0]] has trace 0, swapping rows gives I with trace 2. Answer: (A), (B).

Concept: Elementary row operations: a swap flips the determinant's sign but keeps it non-zero. Symmetry and trace depend on positions of entries, so they are not preserved.

(A) Outputting 100 first needs 400, 300, 200 parked in S2, but S2 holds only 2 - impossible. (B) PushToS2 (400), PushToS2 (300), output 200, PushToS1, output 300, PushToS1, output 400, output 100 - possible. (C) Output 400, PushToS2 (300), output 200, output 100, PushToS1, output 300 - possible. (D) PushToS2 (400), output 300, output 200, PushToS1, output 400, output 100 - possible. Answer: (B), (C), (D).

Concept: Simulating stack permutations with a bounded auxiliary stack. The capacity of S2 is what rules out reaching the bottom element first.

224 in base 5 = 2·25 + 2·5 + 4 = 64. (A) 64 in base 10 = 64. (B) 100 in base 8 = 64. (C) 50 in base 16 = 5·16 = 80. (D) 121 in base 7 = 49 + 14 + 1 = 64. Answer: (A), (B), (D).

Concept: Convert everything to decimal with positional weights. Hex 50 is 80, not 50 - the usual slip is reading the digits as decimal.

Y = (f1 · f2) ⊕ (f3 + f4). f1 · f2 = common minterms = {3,5,7,11,13}. f3 + f4 = {0,1,2,4,6,11,13}. XOR keeps minterms in exactly one of them: 11 and 13 cancel, leaving {3,5,7} ∪ {0,1,2,4,6} = {0,1,2,3,4,5,6,7}. So Y = Σ(0,1,2,3,4,5,6,7) = Π(8,9,10,11,12,13,14,15). Answer: (C), (D).

Concept: AND is intersection, OR is union and XOR is symmetric difference of minterm sets. Options in Π form list the maxterms, i.e. the complement set.

Take any cycle C and two edges e, f on it. Extend the path C − f to a spanning tree T (it contains e, not f). T − e + f is also a spanning tree, and both have even weight, so w(f) − w(e) is even: e and f have the same parity. Hence every cycle is all-even or all-odd: (D) true. Counterexamples: a triangle with weights 1, 1, 1 (every spanning tree weighs 2) breaks (A) and (C); a path (a tree) with weights 1, 1, 2 has its only spanning tree of weight 4, breaking (B). Answer: (D).

Concept: Spanning-tree exchange: swapping one cycle edge for another keeps a spanning tree, so cycle edges must share parity. Edges not on a common cycle (bridges) can differ.

Track the number of S symbols in a sentential form. Start with 1. S → aS keeps it, S → aSbS adds one S and one b (and one a), S → c removes an S and adds a c. Every S ends as a c, so nc = 1 + nb: (C) true and (D) false (w = c gives 1 ≠ 0). Each b comes with an a, so na ≥ nb, but w = acbc has na = nb = 1, so (A) false. Since nc − 2 = nb − 1 ≤ na − 1 < na, (B) true. Answer: (B), (C).

Concept: Invariant counting over derivations. Check strict inequalities against the smallest strings (c, acbc) to catch equal cases.

6000 RPM = 100 rotations per second, so one rotation = 10 ms and average rotational latency = 5 ms. Transfer of one sector = 10 ms / 500 = 0.02 ms. Sectors are random, so each needs seek + latency + transfer = 5 + 5 + 0.02 = 10.02 ms. Total = 3000 × 10.02 ms = 30.06 s. The official key accepts 29.5 to 30.5 (ignoring the tiny transfer time gives 30.00). Answer: 30.06.

Concept: For randomly placed sectors every access pays the full seek and half-rotation latency. The trap is treating the file as contiguous and paying seek once.

On timeout, ssthresh = 12/2 = 6 MSS and cwnd resets to 1 MSS, entering slow start. RTT 1: cwnd = 1; all acknowledged, cwnd = 2. RTT 2: cwnd = 2; all acknowledged, cwnd = 4. Still below ssthresh 6, so during the third RTT cwnd = 4 MSS. Answer: 4.

Concept: Timeout means cwnd = 1 and slow start (doubling per RTT) up to ssthresh = half the old window. Fast-recovery halving applies to triple duplicate ACKs, not timeouts.

One-way propagation delay = 500 / (2 × 10⁸) = 2.5 µs. For CSMA/CD the transmission time must be at least the round-trip time 2 × 2.5 = 5 µs. Minimum frame = 10⁸ × 5 × 10⁻⁶ = 500 bits. Answer: 500.

Concept: CSMA/CD requires frame transmission time ≥ 2 × propagation delay so the sender is still transmitting when a collision returns. Using one-way delay gives 250, the trap.

Each attribute goes to X, to Y, or to neither: 3⁴ = 81 assignments with X and Y disjoint. Remove those with X empty (each attribute in Y or neither: 2⁴ = 16) and those with Y empty (16), adding back the one with both empty: 81 − 16 − 16 + 1 = 50. Answer: 50.

Concept: Counting ordered pairs of disjoint non-empty subsets via 3ⁿ and inclusion-exclusion. Forgetting to add back the both-empty case gives 49.

Register fields: 16 registers need 4 bits each, 2 × 4 = 8 bits. Addressing mode: 8 modes need 3 bits. Scalar: 16 bits. Opcode bits = 32 − 8 − 3 − 16 = 5, so 2⁵ = 32 opcodes for every addressing mode. Answer: 32.

Concept: Instruction field budgeting. The addressing-mode field is separate, so each mode gets the full opcode space.

Pipelined CPI = 1 + 0.2 × 2 + 0.2 × 3 = 1 + 0.4 + 0.6 = 2. Non-pipelined CPI = 6. The clock is the same 2 GHz, so speedup = 6 / 2 = 3.0. Answer: 3.0.

Concept: Effective CPI = ideal CPI + average stall cycles per instruction. Using 5 (stage count) instead of the given 6 cycles is the trap.

Take all weight-1 edges (no cycle): a-b, a-f, c-d, d-e. Components: {a,b,f}, {c,d,e}, {g}. Two more edges are needed. The cheapest connections are weight 2, all through g: g to {a,b,f} via a-g, b-g or f-g (3 choices) and g to {c,d,e} via c-g, d-g or e-g (3 choices). The direct links between {a,b,f} and {c,d,e} (b-c, f-e) weigh 3, so they never appear. MST weight 4 + 4 = 8 and the count is 3 × 3 = 9. Answer: 9.

Concept: Counting MSTs with ties: contract the forced lighter edges, then multiply the number of equal-weight choices for each required connection.

Colour odd-numbered vertices red and even-numbered vertices blue. Every edge joins vertices whose labels differ by an odd amount (sides differ by 1 or 7, chords by 3 or 5), so every edge joins an odd and an even vertex: the graph is bipartite and 2 colours suffice. It has edges, so 1 colour is not enough. Answer: 2.

Concept: A graph is 2-colourable exactly when it is bipartite (no odd cycle). The crossing chords make the picture look dense, which tempts answers of 3 or 4.

75 instructions of each type need ⌈log₂ 75⌉ = 7 operation bits, plus 1 type bit: Y = 8. 50 registers need 6 bits per register field. R-type: 8 + X + 3 × 6 = 32, so X = 6. I-type: 8 + 2 × 6 + Z = 32, so Z = 12. X + 2Y + Z = 6 + 16 + 12 = 34. Answer: 34.

Concept: Field budgeting with a type bit: the 7 operation bits encode 75 operations per type, not 150. Using 8 operation bits gives Y = 9 and a wrong total.

b*ab* contributes exactly one a, and each (ab*ab*) block adds two more, with b's anywhere: L1 = strings over {a,b} with an odd number of a's. Count those of length ≤ 4. Length 1: 1 (a). Length 2: C(2,1) = 2. Length 3: C(3,1) + C(3,3) = 4. Length 4: C(4,1) + C(4,3) = 8. Total = 1 + 2 + 4 + 8 = 15. Answer: 15.

Concept: Recognise the expression as 'odd number of a's'; half of the 2ⁿ strings of each length n ≥ 1 qualify, giving 2ⁿ⁻¹ each.

An element is its own inverse when g + g = 0, componentwise. In Z2 both 0 and 1 satisfy 2g = 0 (2 choices). In Z3 only 0 (2g ≡ 0 mod 3 forces g = 0). In Z4, 0 and 2 (2 choices). Total = 2 × 1 × 2 = 4. Answer: 4.

Concept: Self-inverse elements in a direct product are tuples of self-inverse components. Remember the identity counts as its own inverse.

A 4 KB page holds 4096/4 = 1024 entries, so each inner page-table page maps 1024 pages and the directory has 1024 entries (2²⁰ pages total). Minimum: 2000 pages packed contiguously need ⌈2000/1024⌉ = 2 inner pages, plus the directory: X = 3. Maximum: spread the pages so each inner page has as few valid entries as possible, but there are only 1024 inner pages possible: Y = 1024 + 1 = 1025. X + Y = 1028. Answer: 1028.

Concept: Two-level paging bounds: dense placement minimises inner tables; sparse placement is capped by the directory's 1024 entries, not by 2000.

I0 contains S′ → •S, S → •SS, S → •Aa, S → •bAc, S → •Bc, S → •bBa, A → •d#, B → •@. GOTO(I0, S) moves the dot over S in S′ → •S and S → •SS, giving the kernel S′ → S• and S → S•S. Closure of S → S•S adds all S-items S → •SS, S → •Aa, S → •bAc, S → •Bc, S → •bBa, and then A → •d# and B → •@. Total = 2 + 5 + 2 = 9. Answer: 9.

Concept: GOTO = advance the dot, then take the closure. Forgetting to close over A and B (reached via •Aa and •Bc) gives 7.