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

Expedite, hasten and hurry all mean to make something happen faster. Accelerate means to increase speed, so it fits the group. Retard means to slow down (opposite), provide means to supply, and disable means to make unable. Answer: (A) Accelerate.

Concept: Synonym grouping. Identify the common meaning of the given words (speeding up) and pick the option sharing it. The trap is retard, which belongs to the same topic of speed but is the antonym.

This is a binomial count with n = 4, p = 0.5. P(exactly 3 cloudy) = C(4,3) x (0.5)^3 x (0.5)^1 = 4 x 1/16 = 1/4. Answer: (A) 1/4.

Concept: Binomial probability: choose which of the four days is sunny (4 ways), each specific pattern has probability 1/16. The trap is forgetting the C(4,3) factor and answering 1/16, or confusing with 3/8 which is the value for exactly 2 of 4.

Rs. 100 buys 100/50 = 2 shares of A; Rs. 80 buys 80/80 = 1 share of B. Total cost = 180. Next day: 2 x 55 + 1 x 70 = 110 + 70 = 180. Profit = 180 - 180 = 0. Answer: (A) 0.

Concept: Convert money invested into number of shares, then revalue. The gain of Rs. 10 on A exactly offsets the loss of Rs. 10 on B. The trap is applying the per-share change (+5, -10) directly without scaling by the number of shares.

The statement is: raining -> dance. The only statement logically equivalent to an implication is its contrapositive: not dance -> not raining, i.e. when peacocks are not dancing, it is not raining. (A) and (B) are the converse, (D) is the inverse; neither follows. Answer: (C).

Concept: Tests implication versus converse, inverse and contrapositive. Only the contrapositive is guaranteed. The usual trap is picking the converse or inverse, which sound natural but are not implied.

Water quenches thirst; food satisfies hunger. The relation is 'remedy : need', so P = Thirst and Q = Hunger. (B) mixes an action (drink) with a need; (C) mixes a need with a resulting state. Answer: (A).

Concept: Analogy questions require the same relation on both sides. Water relieves thirst as food relieves hunger. The trap is options where each pair is related to its word but via different relations.

The trip is a Hamiltonian cycle. (i): a 4 x 4 grid has one - go along the top row, snake down and back through columns 2 to 4, then return up column 1. So (i) works. (ii): Q, R and S each have degree 2, so both their edges must be in the cycle: Q-P, Q-T, R-P, R-T, S-P, S-T. That forces P to have 3 cycle edges, impossible (each vertex has exactly 2 in a cycle). So (ii) fails. Answer: (A).

Concept: Hamiltonian cycle reasoning: degree-2 vertices force their edges into the cycle, which quickly exposes contradictions. The trap is confusing this with an Euler circuit (every edge once) and checking degree parity instead.

Check row counts first: (i) has rows 3,2,1,2 - fails. (iii) has rows 3,2,1,2 - fails. (iv) has rows 3,1,1,3 - fails. (ii) has rows 3,1,2,2. Its columns: col1 rows 1,4 = 2; col2 rows 2,4 = 2; col3 rows 1,3 = 2; col4 rows 1,3 = 2. All constraints hold. Answer: (B) (ii).

Concept: Constraint checking (a nonogram): eliminate options by verifying row totals, then confirm column totals. The trap is checking only rows or only columns.

Possible prime sums are 2, 3, 5, 7, 11. Number of ordered outcomes: sum 2 -> 1, sum 3 -> 2, sum 5 -> 4, sum 7 -> 6, sum 11 -> 2. Total = 15 out of 36. Answer: (C) 15/36.

Concept: Counting ordered outcomes of two dice. The trap is forgetting 2 is prime or counting (1,2) and (2,1) as one outcome.

Let y be the special person: 'there exists y'. For every other person x (for all x with x ≠ y): x knows y, M(x, y), and y does not know x, ¬M(y, x). This is (∃y)(∀x)((x ≠ y) → (M(x, y) ∧ ¬M(y, x))). Answer: (A).

Concept: Translating English to predicate logic: one specific person (∃) related in a fixed way to all others (∀), with the guard written as an implication. The trap is swapping the quantifier order, which changes the meaning, or using ∃x which makes the statement nearly vacuous.

Inorder visits left subtree, node, right subtree (L). Preorder visits node first, then left, then right (M). Postorder visits left, right, then node (N). Answer: (A) I → L, II → M, III → N.

Concept: Definitions of the three depth-first traversals: the prefix (pre/in/post) tells where the node is visited relative to its subtrees. Mixing up pre and post is the common slip.

M decides L means M halts on every input, accepting exactly the strings in L and rejecting every string not in L. (A) only says it halts (it could decide some other language). (B) alone allows looping on non-members (that is recognising). (C) alone says nothing about members. (D) states both halves, and accepting or rejecting implies halting. Answer: (D).

Concept: Deciding versus recognising: a decider must halt with the correct verdict on every input. The trap is (B), which describes a recogniser that may loop forever on strings outside L.

The normal density is (1/(σ√(2π))) exp(-(x - μ)²/(2σ²)). With μ = 0 and σ = 3: 2σ² = 18 and the constant is 1/(3√(2π)), matching exactly. So X ~ N(0, 9). Poisson is discrete, exponential is supported on x ≥ 0, uniform has a constant density. Answer: (B).

Concept: Recognise the Gaussian form exp(-x²/(2σ²)) with matching normalisation. The trap is being misled by 'exp' into choosing exponential, whose density is λe^(-λx) on x ≥ 0 only.

In the three-schema architecture: the logical (conceptual) schema describes the relations; the physical schema describes storage - file organization and indexes; the external schema describes the views presented to users. So I → N, II → M, III → L. Answer: (C).

Concept: Three levels of data abstraction (ANSI/SPARC). The trap is mapping the external schema to relations instead of views.

(A) and (D) are commutative laws. (C) is the complement law for OR. The complement law for AND is a . a' = 0, not 1, so (B) is false. Answer: (B).

Concept: Complement laws: a + a' = 1 and a . a' = 0. The trap is reading quickly and treating both complement laws as giving 1.

Static variables live in the data/BSS segment. A local array is on the stack in the function's activation record. The return address is also on the stack. Memory obtained with malloc() comes from the heap. Answer: (C).

Concept: Memory layout of a C program: text, data/BSS, stack, heap. The trap is (A): a static local has function scope but static storage duration, so it is in the data segment, not the stack or heap.

S1: In a non-vectored scheme the CPU jumps to a fixed location and software must identify the source, so starting the right ISR takes longer than with a vector supplied by the device. True. S2: In a daisy chain the interrupt-acknowledge signal propagates through devices in hardware and the first requesting device places its vector on the bus; the CPU does not poll each device. Polling is a different scheme. False. Answer: (C).

Concept: Distinguish vectored, non-vectored, polling and daisy-chain priority. The trap is treating daisy chaining as software polling; it is a hardware priority chain.

P1: the global a and the local a are in different scopes; the local one shadows the global. Legal. P2: a is defined twice in the same block - redefinition error. P3: a is declared as int and then as float in the same block - conflicting types error. Only P1 compiles. Answer: (A).

Concept: Scope and redeclaration rules in C: an inner scope may shadow an outer name, but the same block cannot define a name twice, whatever the type. The trap is thinking a different type makes P3 legal.

Two operations on the same item by different transactions conflict if at least one of them is a write. Read-write, write-read and write-write all conflict. Only read-read does not. Answer: (A).

Concept: Definition of conflicting operations used in conflict serializability. The trap is thinking only write-write conflicts.

File size = 4 x 10⁶ bytes = 32 x 10⁶ bits. With negligible delays and the data streamed along the path, end-to-end throughput equals the bottleneck link rate, min(2 Mbps, 500 kbps, 1 Mbps) = 500 kbps. Time = 32 x 10⁶ / 5 x 10⁵ = 64 s. Answer: (B) 64.

Concept: End-to-end throughput of a path is limited by its slowest link. Traps: forgetting bytes-to-bits (giving 8 or 16), or summing per-link transfer times as if the whole file were stored and forwarded at each hop.

A DHCP client has no IP address and does not know the server's address, so DHCPDISCOVER (and typically DHCPREQUEST) is sent to the broadcast address 255.255.255.255. SMTP, FTP and HTTP run over TCP connections to a known server and are unicast. Answer: (C) DHCP.

Concept: Broadcast is needed when the destination is unknown, as in address configuration. TCP-based application protocols are always unicast.

SRTF is the preemptive version of SJF. Round Robin preempts on quantum expiry. Priority scheduling can be preemptive or not. FCFS runs each process to completion (or until it blocks) in arrival order and never preempts. Answer: (B).

Concept: Know which schedulers are inherently preemptive, inherently non-preemptive, or either. The trap is priority scheduling, which has both variants.

2^(log₂ n) = n. log(n!) = Θ(n log n) by Stirling. Any polynomial beats a logarithm, so log n < n^(1/3) < n. Hence log n, n^(1/3), 2^(log n), log(n!). Answer: (A).

Concept: Simplify before comparing: 2^(log₂ n) is just n, and log(n!) is Θ(n log n). The trap is treating 2^(log n) as exponential and putting it last.

(A) unrolls to T(n) = n: Θ(n). (B) by the master theorem, a = 2, b = 2, n^(log_b a) = n dominates f(n) = 1, so Θ(n). (C) f(n) = n equals n^(log_b a), so Θ(n log n). (D) sums 1 + 2 + ... + n = Θ(n²). Answer: (A) and (B).

Concept: Solving recurrences by unrolling and the master theorem. The trap is (B): two half-size calls with constant work still total Θ(n), not Θ(log n).

Reflexive: x·x = x² is a square. Symmetric: xy = yx. Transitive: if xy = a² and yz = b², then xz·y² = (ab)², so xz = (ab/y)² is a rational square that is an integer, hence a perfect square. Antisymmetric fails: (1,4) and (4,1) are both in R but 1 ≠ 4. Answer: (A), (B) and (C).

Concept: R relates numbers with the same square-free part, so it is an equivalence relation. The trap is doubting transitivity, or assuming antisymmetry without testing a pair like (1,4).

∫₋₁¹ 3x² dx = [x³]₋₁¹ = 2. ∫₋₁¹ ax dx = 0 because x is odd over a symmetric interval. ∫₋₁¹ 1 dx = 2. So I(a) = 4 for every a. It is independent of a and always positive, never negative. Answer: (A) and (C).

Concept: Odd functions integrate to zero over symmetric limits, removing the a-dependence. The trap is assuming a parameter in the integrand must affect the value.

Values: N1 = -5, N2 = -3, N3 = -6, N4 = -7. Range is -8 to 7. N1 + N2 = -8: fits. N2 + N3 = -9: overflow. N3 - N4 = -6 + 7 = 1: fits. N1 + N4 = -12: overflow. Answer: (B) and (D).

Concept: Overflow occurs when the true result lies outside [-8, 7]; adding two negatives can overflow, subtracting a negative from a negative cannot here. The trap is forgetting -8 is representable, so N1 + N2 is fine.

(A) generates aⁿbⁿ with exactly one derivation per string. (B) id + id * id has two parse trees (+ at root or * at root): ambiguous. (C) 'a' can be derived as S → aS → a or S → Sa → a: two parse trees, ambiguous. (D) is right-linear with one derivation per aⁿ. Answer: (B) and (C).

Concept: Ambiguity means some string has two distinct parse trees. Grammars that can grow on both sides from the same nonterminal (like C) or lack precedence (B) are typical. The trap is thinking C is safe because its language a* is simple.

k mod 9: 5→5, 28→1, 19→1, 15→6, 26→8, 33→6, 12→3, 17→8, 10→1. Slot 1 holds 28, 19, 10 (3 keys); slots 6 and 8 hold 2 each; others at most 1. Longest chain = 3. Answer: 3.

Concept: Separate chaining: just compute each bucket and count. The usual slip is an arithmetic error in a mod computation.

Infinitely many solutions require the two equations to be proportional: a/16 = 1/a = b/24. From a/16 = 1/a, a² = 16, a = ±4. Then b = 24/a: a = 4 gives b = 6, a = -4 gives b = -6. Either way ab = 24. Answer: 24.

Concept: Two lines coincide when coefficient ratios and constant ratio are all equal. The trap is setting only the determinant to zero (that also allows no solution) and forgetting the constant ratio.

Level 1: [10]+[7] not void; [8]+[19] void; [41]+[35] not void; [25]+[31] void. Level 2: [7,10]+[8,19] not void (8 < 10); [35,41]+[25,31] not void. Level 3: [7,8,10,19]+[25,31,35,41] void (19 < 25). A merge is void exactly when max(L) < min(R). Total = 3. Answer: 3.

Concept: Trace top-down merge sort level by level; a merge is void when the largest element of L is below the smallest of R. The trap is checking the original unsorted halves instead of the sorted subarrays.

255.255.240.0 = 11111111.11111111.11110000.00000000, a /20 mask, leaving 32 - 20 = 12 host bits. That gives 2¹² = 4096 addresses; excluding the network address (all host bits 0) and the broadcast address (all 1) leaves 4094 assignable. Answer: 4094.

Concept: Usable hosts = 2^(host bits) - 2. The trap is answering 4096 by forgetting the network and broadcast addresses, or miscounting the bits in 240 (four 1s).

0xC2710000 = 1 10000100 11100010000000000000000. Sign = 1 (negative). Exponent = 10000100₂ = 132, unbiased 132 - 127 = 5. Significand = 1.1110001₂. Value = -1.1110001₂ x 2⁵ = -111100.01₂ = -(32 + 16 + 8 + 4 + 0.25) = -60.25. Answer: -60.25.

Concept: IEEE 754 decoding: 1 sign bit, 8-bit exponent with bias 127, implicit leading 1. Traps: forgetting the hidden 1, using bias 128, or misaligning the hex nibbles across the sign/exponent boundary.

Use longest match. x1 → id (1). 23mm → number 23, id mm (2). 78 → number (1). y → id (1). 7z → number 7, id z (2). zz5 → id (1). 14A → number 14, id A (2). 8H → number 8, id H (2). AaYcD → id (1). Total = 1+2+1+1+2+1+2+2+1 = 13. Answer: 13.

Concept: An id must start with a letter, so a word beginning with digits splits into a number followed by an id. The trap is counting each blank-separated word as one token (giving 9).

The coefficient is 0 exactly when two spanning trees share no edge. Kₙ has n(n-1)/2 edges, and for n ≥ 4 it contains two edge-disjoint spanning trees (Nash-Williams; indeed Kₙ decomposes into floor(n/2) of them). Example for n = 5: T1 = path 1-2-3-4-5 = {12, 23, 34, 45} and T2 = path 1-3-5-2-4 = {13, 35, 25, 24}, which share no edge. So the minimum is 0. Answer: (C) 0.

Concept: Edge-disjoint spanning trees exist in dense graphs; Kₙ has enough edges (at least 2(n-1) for n ≥ 4). The trap is assuming all spanning trees must share some edge and computing 1/(2n-3), which is the value for exactly one shared edge.

Topologically sort the DAG in Θ(m + n), then relax the outgoing edges of each vertex in topological order. Every edge is relaxed once, and when a vertex is processed its distance is final. Total Θ(m + n), and every edge may need to be examined, so this is optimal. It also handles negative weights. Answer: (A).

Concept: DAG shortest paths need no priority queue. The trap is reaching for Dijkstra (B) or Bellman-Ford (C) without exploiting acyclicity.

Let dᵢ = A[i+1] - A[i] for i = 1..n-1. The condition says dᵢ > dⱼ whenever i > j, i.e. the difference sequence is strictly increasing. By transitivity it suffices to check dᵢ₊₁ > dᵢ for consecutive i: one pass, Θ(n). A lower bound of Ω(n) holds because any unread element could break the condition. Answer: (A) Θ(n).

Concept: A condition over all pairs often reduces to adjacent pairs via transitivity. The trap is checking all pairs in Θ(n²) or thinking binary search applies.

T[i][j] depends on T[i-1][j] (row above) and T[i][j-1] (left). Boundary entries are already 1. B1 fills row by row, left to right, so both dependencies are final when used: correct. B2 fills anti-diagonals i + j = s in increasing s; both dependencies lie on diagonal s - 1 (or on the boundary), already computed: correct. B2 is just slower (Θ(n³)). Answer: (A).

Concept: A DP evaluation order is valid if every entry's dependencies are computed before it. Both row-major and anti-diagonal orders satisfy this. The trap is judging B2 wrong because of its wasted iterations.

Minterms 0-3 are 00xx (A'B') and minterms 8-11 are 10xx (AB'). Together they are all minterms with B = 0 regardless of A, C, D: F = A'B' + AB' = B'. Answer: (B) B'.

Concept: Group the eight 1-cells in a K-map; an octet eliminates three variables. The trap is (C), which replaces AB' with AB.

Augment with S' → S. I0 = {S' → .S, S → .ACB, A → .aA, A → .}: shift on a and reduce A → ε (LR(0) reduces in every column) - conflict 1. I(a) = {A → a.A, A → .aA, A → .}: shift a vs reduce - conflict 2. I(A) = {S → A.CB, C → .cC, C → .}: shift c vs reduce - conflict 3. I(c) = {C → c.C, C → .cC, C → .}: conflict 4. I(AC) = {S → AC.B, B → .bB, B → .b}: shifts only. I(b) = {B → b.B, B → b., B → .bB, B → .b}: shift b vs reduce B → b - conflict 5. Other states have no conflict. Total = 5. Answer: (D) 5.

Concept: In LR(0), a state with a completed item reduces on every terminal, so any shift in that state conflicts. ε-productions create a completed item in every state that predicts them. The trap is missing the B → b. state or forgetting I0.

Augment X → Y with X: X → XY (since XX = X). Augment X → Z with Y: XY → YZ. Transitivity on X → XY and XY → YZ gives X → YZ. Only augmentation and transitivity are used, and neither alone suffices (transitivity cannot combine right-hand sides; augmentation cannot chain). Answer: (D).

Concept: The standard derivation of the union rule. The trap is (A): all three axioms are sufficient but reflexivity is not necessary.

Generator 1001 has degree 3, so append three 0s: 110001011000. Modulo-2 division by 1001: 1100 xor 1001 = 0101; continue bringing down bits and XORing whenever the leading bit is 1. Working through the 12 bits leaves remainder 100. The transmitted frame is 110001011100. Answer: (D) 100.

Concept: CRC: append (degree of generator) zeros, divide with XOR (no borrows), the remainder is the checksum. Traps: appending 4 zeros instead of 3, or doing ordinary subtraction.

Instruction = 16 bits, register field = 4 bits. M-type: 4+4+6 = 14 operand bits, 2-bit opcode. R-type: 12 operand bits, 4-bit opcode. C-type: 4+6 = 10 operand bits, 6-bit opcode. Expanding opcodes: 2² = 4 codes, M uses 2, leaving 2. Each extends by 2 bits: 2 x 4 = 8 R-level codes; R uses 7, leaving 1. That extends by 2 more bits: 1 x 4 = 4 C-type opcodes. Answer: (B) 4.

Concept: Expanding-opcode technique: unused shorter opcodes become prefixes for longer ones. The trap is answering 64 by giving C-type the full 6-bit opcode space.

in(B) = use(B) ∪ (out(B) - def(B)), out(B) = union of in(successors). B4: out = ∅, in = {d, e}. B2: out = {d, e}, in = {a, e}. B3: in = {a, f} ∪ (out(B3) - {e}), out(B3) = in(B1). B1: in = {b, c} ∪ (out(B1) - {a}), out(B1) = in(B2) ∪ in(B3). Iterate to a fixed point: out(B1) = {a, e} ∪ {a, f, b, c} = {a, b, c, e, f}; in(B1) = {b, c, e, f}; out(B3) = {b, c, e, f}. Answer: (A).

Concept: Backward dataflow analysis with a loop (B3 → B1) needs iteration until nothing changes. The trap is stopping after one pass and missing that e and f flow around the loop, or that e is killed in B3 but live again from B1.

S1: A hash index locates a record by hashing its exact key value; there is no ordering to let one entry cover a range of keys, so every search-key value must have an entry - it is a secondary-style dense index. True. S2: On a file sorted by the search key, a B+ tree can store one entry per data block (leaf entries point to blocks), which is a sparse index. True. Answer: (A).

Concept: Sparse indexing works only when the file is ordered on the key, so the index can point to the block where a key would lie. Hashing has no such order. The trap is assuming B+ trees must always be dense.

(A) i - j + k - l = 0: a PDA keeps a signed counter on the stack (+1 for a, c; -1 for b, d), using a marker for sign; accept when it returns to zero. Context-free. (B) i = k and j = l are crossing dependencies (like aⁱbʲcⁱdʲ), not context-free by the pumping lemma. (C) i = l, j = k is nested: S → aSd | T, T → bTc | ε. Context-free. (D) i + j = k + l: push for a and b, pop for c and d. Context-free. Answer: (A), (C) and (D).

Concept: A single stack handles nested or counter-style constraints but not two interleaved (crossing) equalities. The trap is (A), which looks crossing but is really one balanced counter.

(A) Each interval (Val(Lᵢ), Val(Suc(Lᵢ))) lies between consecutive keys in sorted order, so different leaves give disjoint open intervals: no duplicates. True. (B) If the only leaf holds the maximum key (e.g. a single-node tree or a right-skewed chain), it has no successor and K is empty. False. (C) A leaf has no right child, and kᵢ lies just after Val(Lᵢ) in order, so kᵢ is inserted as the right child of Lᵢ. Each new node hangs one level below an old leaf, so height grows by at most one. True. (D) Only leaves get new keys, so nodes do not double in general. False. Answer: (A) and (C).

Concept: A key between a node and its inorder successor is inserted as that node's right child if it has none. The trap is (B): the single-leaf case can have no successor.

Stack output is its elements in decreasing arrival order, then the queue in increasing order. (A) S = {1,3,4} → 4 3 1, Q = {2,5} → 2 5: output 4 3 1 2 5. Valid. (B) S = {3,4} → 4 3, Q = {1,2,5} → 1 2 5: 4 3 1 2 5. Valid. (C) S = {4,5} → 5 4 first. Invalid. (D) S = {1,2,3} → 3 2 1 first. Invalid. Answer: (A) and (B).

Concept: Simulate each assignment. The output can be split as a decreasing prefix (stack) and an increasing suffix (queue); element 1 can sit on either side of the split, giving two valid answers.

The block from Wait(A) to Signal(A) is a critical section. The second process to enter prints * then $ and signals B before releasing A. So $ immediately follows the second *, and the third * can only come after $ - (D) is impossible. After $, B = 1 and each # is followed by Signal(B), so #s chain. (A): third process enters before any #: **$*###. (B): first waiter prints #, then third enters: **$#*##. (C): two #s, then third enters, then its #: **$##*#. All feasible. Answer: (A), (B) and (C).

Concept: Mutual exclusion on A forces * $ of the second process to be adjacent; B acts as a turnstile once opened. The trap is (D), which needs a third * inside another process's critical section.

24-bit address; 256 lines, so offset 4 bits, index 8 bits, tag 12 bits. P: tag 845, index B3. Q: tag 845, index B2. R: tag 845, index B3 (same block as P). S: tag 846, index B3. Each round: P misses (S evicted it, or cold), Q hits after the first round (own line B2), R hits (block just loaded by P), S misses and evicts P's block. So P always misses, R always hits, Q misses only once, S always misses. Answer: (A) and (B).

Concept: Split addresses into tag/index/offset; words in the same block share a line, and different tags on the same index thrash. The trap is thinking R misses because it differs from P - it is in the same 16-byte block.

Number of disk blocks = 16 GB / 2 KB = 2³⁴ / 2¹¹ = 2²³ = 8,388,608. Each list block holds (2048 - 4)/4 = 511 block numbers (4 bytes reserved for the next pointer). In the worst case (all blocks free) the list needs ceil(8,388,608 / 511) = ceil(16416.06) = 16417 blocks. Answer: 16417.

Concept: Grouped free-list sizing: subtract the next-pointer from each block's capacity and take the ceiling. Traps: using 512 entries per block (giving 16384) or forgetting to round up.

Entries = reach / page size = 2²⁰ / 2¹² = 256. Page number bits = log₂(64 GB / 4 KB) = 36 - 12 = 24. Frame number bits = log₂(1 GB / 4 KB) = 30 - 12 = 18. Entry = 4 + 24 + 18 + 2 = 48 bits = 6 bytes. TLB size = 256 x 6 = 1536 bytes. Answer: 1536.

Concept: TLB reach = entries x page size, giving the entry count; each entry stores the full virtual page number (fully associative) plus frame number and extras. The trap is using the address widths (36, 30) instead of page/frame number widths.

Best fit for P1 (16 KB): smallest hole ≥ 16 is 18 KB, leaving a 2 KB hole. Best fit for P2 (9 KB): the 9 KB hole fits exactly, leaving no hole. Holes now: 20, 4, 25, 2, 7, 15, 12. Those below 8 KB: 4, 2, 7 = 3. Answer: 3.

Concept: Best fit picks the smallest adequate hole and tends to leave tiny fragments. The trap is counting a 0 KB leftover as a hole.

Address is 20 bits: 0xA2C28 = 1010 0010 1100 0010 1000. The index field is a contiguous bit range just above the offset whose value must be 176 = 10110000₂. The pattern 10110000 occurs at bits 13..6 (counting bit 0 as LSB), so the offset is bits 5..0 (block size 64 bytes). Leading zeros extend the index upward: bits 16, 15, 14 are 0, bit 17 is 1. So the index can be bits 16..6 = 11 bits, value 00010110000₂ = 176. Cache size = 2¹¹ blocks x 64 B = 128 KB. Answer: 128.

Concept: Index bits of the address must equal the block number; the cache is largest when the index is widened with leading zeros as far as possible. The trap is assuming a fixed block size or ignoring that leading zeros may join the index.

Non-pipelined time per instruction = 5 / 1.6 GHz = 3.125 ns. Pipelined CPI = 1 + 0.3 x 2 = 1.6, time = 1.6 / 1.2 GHz = 1.333 ns. Speed-up = 3.125 / 1.333 = 2.34. Answer: 2.34 (accepted range 2.3 to 2.4).

Concept: Speed-up compares execution time per instruction (CPI x cycle time), so the slower pipelined clock must be included. Traps: using 5/1.6 cycles ratio alone (3.125) or ignoring stalls (3.75).

Slow start begins at cwnd = 1 MSS = 2 KB and doubles each round: round 1: 2 KB, round 2: 4 KB, round 3: 8 KB, round 4: 16 KB. In round 4 cwnd reaches ssthresh = 16 KB (8 MSS), so the connection is now in congestion avoidance and grows linearly afterwards. The 48 KB receiver window never limits this. Answer: 4.

Concept: Slow start doubles cwnd per RTT until it reaches ssthresh, then switches to additive increase. The trap is starting cwnd at 0 or counting the number of doublings (3) rather than transmission rounds.

D0 = A'B', D3 = AB. S1S0 = 00: Y = D0, true for AB = 00 only: 1 combination. S1S0 = 01: Y = 0: 0. S1S0 = 10: Y = 1 for all four AB: 4. S1S0 = 11: Y = D3, true for AB = 11: 1. Total = 1 + 0 + 4 + 1 = 6. Answer: 6.

Concept: Enumerate by select-line value: each mux input contributes the number of AB values that make it 1. The trap is counting only distinct select values, or treating the decoder outputs as active low.

a=5, b=11, c=20. ptr=&a; *ptr=c sets a=20. ptr=&c. a=*(&b) sets a=11. c=*ptr-a = c - a = 20 - 11 = 9. Output: 9.

Concept: Track which variable ptr points to after each assignment; *(&b) is simply b. The trap is using the stale value of a or thinking *ptr still refers to a.

Only the length%3==1 branch adds 1, and each call reduces length. Track length L mod 3: L ≡ 1 → add 1, L-1 (≡ 0). L ≡ 0 → L-1 (≡ 2). L ≡ 2 → L-2 (≡ 0). From ≡ 0 the chain alternates 0 → 2 → 0 → 2 ... and never returns to ≡ 1, ending at length 0 or -1 which returns 0. So at most one +1 can occur, when the initial length is ≡ 1 mod 3 (e.g. func(0,0) = 1). Maximum = 1. Answer: 1.

Concept: Analyse the recursion as a state machine on length mod 3. The trap is assuming each cycle adds 1 and getting a value growing with n.

Scaling an n x n matrix by k scales the determinant by kⁿ, since each of the n rows is multiplied by k. det(2A) = 2⁴ x 3 = 16 x 3 = 48. Answer: 48.

Concept: det(kA) = kⁿ det(A). The trap is answering 6 (multiplying once) or 24 (2³).

E2: exactly 2 heads among tosses 1, 2, 3, 5 (6 equally likely patterns). Toss 2 is the only overlap with E1; given E2, toss 2 is H in 3 of 6 patterns, so P(toss2 = H | E2) = 1/2. Tosses 4 and 6 are independent of E2. If toss 2 = H, E1 needs at least one H in tosses 4, 6: 3/4. If toss 2 = T, E1 needs both: 1/4. P(E1 | E2) = 1/2 x 3/4 + 1/2 x 1/4 = 1/2. Answer: 0.5.

Concept: Condition on the single shared toss and use independence for the rest. The trap is treating E1 and E2 as independent without checking, or miscounting the 6 patterns of E2.

f is constant on each interval [0.d₁d₂, 0.d₁d₂ + 0.01). Within each tenth, second digits 0-9 give values 0,0,1,1,0,0,1,1,0,0. The value changes at second digits 2 (0→1), 4 (1→0), 6 (0→1) and 8 (1→0): 4 jumps per tenth. Between tenths (second digit 9 to 0) the value stays 0, so no jump. Ten tenths give 4 x 10 = 40 discontinuities, all inside (0,1) (0.02 up to 0.98). Answer: 40.

Concept: A step function is discontinuous only where its value actually changes. The trap is counting every 0.01 boundary (99) or every boundary of an in-set digit block without noticing that 9→0 is not a jump.

(i) In 60 s the link carries 10⁸ x 60 = 6 x 10⁹ bits = 7.5 x 10⁸ bytes, each needing a distinct number: 2ⁿ ≥ 7.5 x 10⁸ gives n = 30 (2²⁹ ≈ 5.4 x 10⁸ is too small, 2³⁰ ≈ 1.07 x 10⁹). (ii) One-way delay = 3 x 10⁶ m x 5 ns = 15 ms, RTT = 30 ms; bytes in flight for full utilisation = 10⁸ x 0.03 / 8 = 375,000, needing about 19-20 bits. The binding requirement is (i). n = 30. Answer: 30.

Concept: Sequence space must cover both the wrap-around time and the bandwidth-delay product; take the larger requirement. The trap is computing only the window for utilisation and answering about 19 or 20.