GATE 2023 CS (Computer Science) question paper with solutions

The blank must modify the verb "missed" and convey that the train was almost caught but not quite. "nearly" (an adverb meaning almost) fits: we arrived late and nearly missed the train. "near" is an adjective/preposition, "utterly" means completely and does not collocate with missed a train, and "mostly" makes no sense for a single event. Answer: (B) nearly.

Concept: Tests adverb choice in context. The trap is "near", which sounds similar but is not the adverb meaning "almost"; "nearly" is the correct modifier for a verb.

Run the recurrence backwards using Fₙ₋₁ = Fₙ₊₁ - Fₙ. F5 = F7 - F6 = 60 - 37 = 23. F4 = F6 - F5 = 37 - 23 = 14. F3 = F5 - F4 = 23 - 14 = 9. F2 = F4 - F3 = 14 - 9 = 5. F1 = F3 - F2 = 9 - 5 = 4. Check forwards: 4, 5, 9, 14, 23, 37, 60. Answer: (A) 4.

Concept: A Fibonacci-type recurrence solved in reverse. The usual slip is subtracting in the wrong order or stopping at F2 = 5, which is also an option.

90% of pregnant women received care at least once. Of these, 60% received care from doctors, i.e. 0.9 × 0.6 = 0.54 = 54% of all pregnant women received care at least once from a doctor. 54% is more than half, so (A) follows with certainty. Nothing is said about how many times care was received, so the "at most once" options cannot be inferred. Answer: (A).

Concept: Percent of a percent: 60% applies to the 90% subgroup, not to everyone. The trap is reading 60% as a share of all women, or being distracted by the "at most once" options, which the data do not address.

A smooth 3D object need not be convex (for example a bowl or a dumbbell shape) nor concave everywhere (a closed surface seen from outside cannot be concave everywhere). Smooth also rules out edges and corners, so (D) is wrong. The only statement that is always true is that the surface may be concave in some places and convex in others. Answer: (C).

Concept: Spatial reasoning about curvature. The trap is assuming every smooth object is convex like a sphere; smoothness only excludes edges and corners, not concave regions.

The government pays people to cycle to work as a measure against health problems caused by lack of physical exercise. That measure only makes sense if the government believes cycling is a form of physical exercise, so (D) is a necessary assumption and can be inferred. (A) and (B) predict outcomes that are not guaranteed, and (C) attributes a recommendation to the experts that the passage never mentions. Answer: (D).

Concept: Inference vs. speculation: the correct option is the belief implicit in the stated policy. Options that predict results or invent facts about what experts said are the usual traps.

f(t) - g(t) = 0.01t² - 4t = 0.01t(t - 400). For 0 < t < 400 this is negative, so g(t) > f(t) (e.g. t = 1: g = 4, f = 0.01), and (i) holds. For t > 400 it is positive, so taking T = 400 gives f(t) > g(t) for all t > T, and (ii) holds. Answer: (C) both (i) and (ii) are correct.

Concept: A quadratic eventually overtakes any linear function, but the linear one can be larger for small t. The trap is assuming one function dominates everywhere.

(iii) introduces Mina and her heavy bags - the natural opening. (ii) follows: she pants after climbing the stairs, explained by the heavy bags. (i) then has her reach the terrace and notice "the man", and (iv) describes what "he" was doing, which needs the man to have been introduced in (i). Order: (iii), (ii), (i), (iv). Answer: (D).

Concept: Narrative ordering using pronoun references and cause-effect. "He" in (iv) must follow the introduction of "the man", and the panting needs the heavy bags first.

Fix y = y0. Then f(x) = g(y0) for every x, so f is constant, say c. Similarly fixing x shows g(y) = f(x0) = c for every y. Hence f(x) = g(y) = c, a constant, but not necessarily zero (f = g = 5 works), so (A) is not necessary. (C) contradicts what we proved. (D) would force g(y) = 0, again not necessary. Answer: (B).

Concept: If a function of x equals a function of y for all independent x and y, both must equal the same constant. The trap is picking (A), which is one valid case but not forced.

The front end (lexical, syntax, semantic analysis, intermediate code generation) depends on the source language but not on the target machine, so S1 is true. The back end (target-specific optimisation, code generation, register allocation) depends on the target hardware, so S2 is true. The back end works on the intermediate representation and is independent of the source language, so S3 is false. Answer: (B) Only S1 and S2 are TRUE.

Concept: The front-end/back-end split exists so one front end can target many machines and one back end can serve many languages. The trap is S3: language specifics belong to the front end.

With 1-based indexing, the children of A[i] are A[2i] and A[2i+1]. (A): A[3] = 10 has child A[6] = 14 > 10, fails. (C): A[5] = 13 has child A[10] = 15, fails. (D): A[4] = 1 has children 12 and 7, fails. (B): 23 ≥ 17, 14; 17 ≥ 7, 13; 14 ≥ 10, 1; 7 ≥ 5, 6; 13 ≥ 12. Every parent is at least its children. Answer: (B).

Concept: Max-heap property: every node is at least as large as its children. Check each parent at index i against 2i and 2i+1; a sorted-looking prefix does not guarantee validity deep in the array.

To delete a node from a singly-linked list, its predecessor's next pointer must be changed, and the only way to find the predecessor is to walk from the head: O(n) in the worst case (the node may be last). In a doubly-linked list the node's prev pointer gives the predecessor directly, so unlinking takes a constant number of pointer updates: O(1). Answer: (D) SLLdel is O(n) and DLLdel is O(1).

Concept: The cost of deletion is the cost of finding the predecessor. The copy-next-node trick for singly-linked lists fails for the last node, so the worst case remains O(n).

From s the only useful move is 1 to p (0 goes to the dead state r). At p, reading 0 loops at p, and reading 1 goes to q, from where 1 must follow to return to p (0 goes to r). So from p, the strings that return to p are built from the pieces 0 and 11 in any order. Accepted language: 1(0 + 11)*. (A) forbids trailing 0s such as "10"; (D) forbids "10" too and allows 0s only after 11. Answer: (C).

Concept: Read loops at the final state as alternatives: a 0-self-loop and a 1-1 round trip give (0 + 11)*. The trap is (A) or (D), which force a fixed order of 0s and 11s.

The characteristic equation r² = r + 1 has roots φ = (1 + √5)/2 and ψ = (1 - √5)/2, so Lₙ = aφⁿ + bψⁿ; options with (1 - √5)/3 are not solutions of the recurrence. Test (A): n = 1: φ + ψ = 1 = L1. n = 2: φ² + ψ² = (φ + ψ)² - 2φψ = 1 - 2(-1) = 3 = L2. Test (D): n = 1 gives φ - ψ = √5 ≠ 1. Answer: (A).

Concept: Linear recurrences are solved by the roots of the characteristic equation, then fitted to initial values. The trap is (D), the Fibonacci form without the 1/√5 factor; Lucas numbers use the sum.

The degree (arity) of a relation is the number of attributes (columns) in its schema. The number of tuples (rows) is its cardinality. Answer: (A) Number of attributes of its relation schema.

Concept: Degree = number of attributes; cardinality = number of tuples. Swapping these two terms is the standard trap.

For Stop-and-Wait, utilization U = Tt / (Tt + 2Tp) = 1 / (1 + 2a), where a = Tp/Tt, Tt = L/R is transmission time and Tp is propagation delay (grows with link length). U is lowest when a is largest: Tp large (longer link) and Tt small (higher transmission rate). Answer: (B) Longer link length and higher transmission rate.

Concept: Stop-and-Wait wastes the round trip; the waste dominates when the frame is sent quickly but takes long to propagate. The trap is thinking a faster link always improves utilization.

B is obtained from A by swapping row 1 and row 3 (rows 2 and 4 are unchanged). A single row interchange multiplies the determinant by -1, so det(B) = -det(A). det(A) is not 0 (A is a circulant whose eigenvalues 10, -2 ± 2i, -2 are all non-zero; det(A) = -160), so (A) and (C) fail, and det(AB) = det(A)det(B) = -det(A)², not a sum. Answer: (B).

Concept: Row operations and determinants: swapping two rows flips the sign. Spot the swap rather than expanding a 4×4 determinant; also recall det(AB) is a product, not a sum.

(A) has an ϵ-move from the start straight to the final state, so it accepts the empty string and strings starting with a digit such as "9". (B) commits after the first letter to only letters or only digits, so "a1b" is rejected. (D) after the first letter accepts only repeated "letter digit" pairs, so "ab" is rejected. (C) is the Thompson construction: after one letter, the final state 1 can loop through either a letter branch or a digit branch and return via ϵ to 1, any number of times, giving letter(letter | digit)*. Answer: (C).

Concept: Tests turning a regular definition into an ϵ-NFA. Watch for ϵ-edges that skip the mandatory first letter and for loops that cannot mix letters and digits.

Any fixed hash function (division or multiplication method) is known to the adversary, who can then choose keys that all hash to the same slot, giving Θ(k) chains. Universal hashing picks the hash function at random from a universal family at run time, so for any fixed set of keys the expected number of collisions for a pair is at most 1/m, regardless of how the keys were chosen. Answer: (C) Universal hashing method.

Concept: Randomisation defeats a malicious input generator. The trap is believing a carefully chosen constant or a prime modulus helps; any deterministic function can be attacked.

Let the external input on line 1 be D. When S = 1 the mux passes input 1, so Q = D (transparent). When S = 0 it passes input 0, which is Q itself, so Q holds its previous value. Q = S·D + S'·Q: the output follows D while S is high and holds while S is low. That is level-triggered storage with S as enable, i.e. a D latch, not an edge-triggered flip-flop. Answer: (B) D Latch.

Concept: A mux with output fed back to one input is the classic gated D latch. The trap is choosing D flip-flop: there is no edge detection, so the output is transparent for the whole time S is high.

Threads of the same process share the address space, so the page table base register does not change and need not be saved. Each thread has its own execution context: its own stack (stack pointer), its own next instruction (program counter) and its own register values (general purpose registers). These must be saved for T1 and restored for T2. Answer: (B), (C), (D).

Concept: Thread context = PC, SP, registers; process context additionally includes the address space. The trap is including the page table base register, which only changes on a process switch.

A function call is an ordinary jump within user mode. malloc is a library routine that usually serves requests from memory already obtained by the process and only sometimes calls brk/mmap, so it does not guarantee a mode switch. A page fault is an exception that always traps into the kernel's fault handler. A system call executes a trap instruction that always switches to kernel mode. Answer: (C) and (D).

Concept: Only traps, exceptions and interrupts guarantee entry to kernel mode. The trap is malloc: it may make a system call, but not on every invocation.

Regular languages are closed under intersection (product automaton), so (A) is correct. CFLs are not: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}, which is not context-free, so (B) is incorrect. Recursive languages are closed under intersection (run both deciders, accept if both accept), so (C) is correct. Recursively enumerable languages are closed under intersection (run both recognisers; accept if both accept; if either loops the string is not in the intersection anyway), so (D) is correct. Answer: (A), (C), (D).

Concept: Closure under intersection holds for regular, recursive and RE languages but fails for CFLs. The standard counterexample is the intersection giving aⁿbⁿcⁿ.

OSPF is a link-state protocol: each router floods link-state advertisements and computes least-cost paths with Dijkstra's algorithm, so (B) is correct and (A), which describes distance-vector protocols like RIP, is incorrect. OSPF is an interior gateway protocol used within one autonomous system (intra-domain); inter-domain routing uses BGP, so (C) is incorrect. OSPF supports hierarchical routing through areas and a backbone area, so (D) is correct. The INCORRECT statements are (A) and (C).

Concept: Link-state = Dijkstra (OSPF); distance-vector = Bellman-Ford (RIP); inter-domain = BGP. Note the question asks for INCORRECT statements.

(B): if Q(x, y) holds for all x, y, then for every x, ∃y Q(x, y) is true, so P(x) ⇒ ∃y Q(x, y) holds for all x. (C): take the witness y0; for every x, P(x) ⇒ Q(x, y0), hence P(x) ⇒ ∃y Q(x, y). So ∃y∀x implies ∀x∃y. (A) and (D) speak about only one particular x; another x with P(x) true and no suitable y would still falsify the conjecture. Answer: (B) and (C).

Concept: Quantifier strength: ∃y∀x implies ∀x∃y, and a universal statement implies its weaker forms. Statements about a single x (existentials) never imply a universal claim.

f'(x) = 3x² + 30x - 33 = 3(x² + 10x - 11) = 3(x + 11)(x - 1), so critical points are x = -11 and x = 1. f''(x) = 6x + 30: f''(-11) = -36 < 0, a local maximum; f''(1) = 36 > 0, a local minimum. Answer: (B) f(x) has a local maximum and (D) f(x) has a local minimum.

Concept: A cubic with two distinct real critical points has one local maximum and one local minimum (but no global extrema). The trap is confusing "no global maximum" with "no local maximum".

n ≤ n² for all n ≥ 1, so f ∈ O(g). Moreover f(n)/g(n) = 1/n → 0, so f ∈ o(g) (strictly slower growth). Since the ratio tends to 0, there is no constant c > 0 with n ≥ c·n² for all large n, so f ∉ Ω(g) and therefore f ∉ Θ(g). Answer: (A) and (C).

Concept: Little-o means the ratio tends to 0, which implies big-O but rules out Ω and Θ. The trap is marking only O and forgetting that o also holds.

Split the integrand. ∫∫∫ 4x²y: the y-integral ∫ from -2 to 2 of y dy = 0 (odd function over a symmetric interval), so this term is 0. ∫∫∫ z³: the z-integral ∫ from -1 to 1 of z³ dz = 0, also odd. Hence the whole integral is 0. Answer: 0.

Concept: Odd-function symmetry: integrating an odd power of a variable over a symmetric interval gives zero. Spotting it avoids a long computation.

132 in radix 4 = 1×16 + 3×4 + 2 = 30 in decimal. Convert 30 to radix 5: 30 = 1×25 + 1×5 + 0, so the digits are 1, 1, 0. Answer: 110.

Concept: Base conversion via decimal. A common slip is reading 132 as decimal or reversing the digits when dividing repeatedly by 5.

The clock cycle must accommodate the slowest stage: max(10, 20, 14) = 20 ns. For k = 3 stages and n = 100 instructions with no hazards, total cycles = k + n - 1 = 3 + 99 = 102. Time = 102 × 20 = 2040 ns. Answer: 2040.

Concept: Pipeline time = (k + n - 1) × cycle time, with the cycle set by the slowest stage. Traps: using the sum of stage delays (44 ns) as the cycle, or using n × k.

Polling: 1 s / 10 ms = 100 polls per second, each 100 μs, giving 10,000 μs = 10 ms. Plus one keystroke processed: 200 μs. T1 = 10.2 ms per second. Interrupts: one keystroke per second, 1 ms each, so T2 = 1 ms per second. T1/T2 = 10.2 / 1 = 10.2. Answer: 10.2.

Concept: Polling costs time even when nothing happens; interrupts cost only per event. Remember to add the 200 μs processing for the one actual keystroke.

The static x in funcp is initialised once to 1 and keeps its value between calls. First call: x becomes 2 and returns 2, so main's x = 2. Second call: static x becomes 3 and returns 3, so y = 3 + 2 = 5. Printed value: x + y = 2 + 5 = 7. Answer: 7.

Concept: A static local variable is initialised once and persists across calls. The trap is re-initialising it to 1 on every call, which would give 2 + 4 = 6.

main calls f1(), f2(2), f3() in that order, so its children are f1, f2, f3. f2(2) first calls f3(); since X = 2 ≠ 1 it then calls f2(1). So f2(2) has children f3, f2. f2(1) calls f3(), then, since X == 1, calls f1(). So f2(1) has children f3, f1. f1 and f3 make no calls. Answer: (A).

Concept: An activation tree has one node per call, with children in call order. The trap is (D), which flattens the recursive call f2(1) and its callees into one level.

Use IN(B) = USE(B) ∪ (OUT(B) - DEF(B)). B2: USE {i, j}, DEF {i, j}. B3: DEF {a}. B4: USE {a}, DEF {i}. OUT(B4) = IN(B2) ∪ IN(EXIT) = IN(B2). Iterate to a fixed point: IN(B2) = {i, j} ∪ (OUT(B2) - {i, j}); OUT(B2) = IN(B3) ∪ IN(B4); IN(B4) = {a} ∪ (OUT(B4) - {i}); IN(B3) = OUT(B3) - {a} = IN(B4) - {a}. Fixed point: IN(B2) = {a, i, j}, so OUT(B4) = {a, i, j}, IN(B4) = {a, j}, OUT(B3) = {a, j}, IN(B3) = {j}, OUT(B2) = {a, j}, OUT(B1) = {a, i, j}. Answer: (D) B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}.

Concept: Backward data-flow analysis with the loop B4 -> B2 carrying i and j back. The trap is ignoring the back edge, which makes i and j look dead at the end of B4.

I-1: a binary semaphore gives mutual exclusion, so every update takes effect: V1 = 10 + 5 - 3 = 12. I-2: two threads can be inside together, so X = X ± 1 (read, modify, write) can race. Minimum: decr1 reads X = 10 and pauses. Through the other slot all 5 incr run one after another, X = 15. decr1 now writes 10 - 1 = 9, wiping out all increments. The remaining two decr run serially: 8, 7. Nothing lower is possible, since only 3 decrements exist and every write is some read value ± 1. V2 = 7. Answer: (C) 12, 7.

Concept: A counting semaphore initialised to 2 is not a mutex, so lost updates are possible. To minimise, let one stale decrement overwrite all the increments.

X generates any number of a's on the left and b's on the right around one base symbol a or b: L(X) = a*(a + b)b*. S → aSb wraps X in equal numbers of a's and b's: L(S) = {aⁿ w bⁿ : w ∈ a*(a + b)b*, n ≥ 0}. Since aⁿa* = a* and b*bⁿ = b*, this is just a*(a + b)b*, which is regular. Strings like "ba" are not generated, ruling out (A), and (C) wrongly puts the single symbol at the end. Answer: (B).

Concept: The aSb rule looks like it forces equal counts, but X already absorbs arbitrary a's and b's, so the language stays regular. The trap is option (D).

The stack can only be emptied in q (the only move that pops ⊥), and q can be entered only by popping an A. In s, each a pushes one A. Reading b's (s to p, then p) pops one A per b. To reach q from s or p we need an A still on top, so after m a's and n b's we need m - n ≥ 1. In q the remaining A's and ⊥ are popped. The empty string fails (no A to enter q), and m ≥ 1 with n < m works. Language: {aᵐbⁿ | m ≥ 1, n < m}. Answer: (A).

Concept: With empty-stack acceptance, find the only route that pops the bottom marker. Here entering q costs one A, so b's must be strictly fewer than a's; the trap is (B), which allows n = m.

Multiplying by 8 = 2³ is a left shift by 3, so U1 = 3. int is 32 bits = 4 bytes and memory is byte-addressable, so the pointers to a[i] and b[i] advance by 4 each iteration: U2 = 4, U3 = 4. The loop must re-test the condition r1 == r2 every iteration, so it jumps back to L01: U4 = L01 (jumping to L02 would never exit). Answer: (B) (3, 4, 4, L01).

Concept: Tests strength reduction (×8 = <<3) and byte addressing (stride = sizeof(int) = 4). The traps are shifting by 8 and stepping pointers by 1.

Addr = 0 inside a block means all ten address-port lines (IA11-IA5, IA2-IA0) are 0. Only IA4 and IA3 vary, selecting the block. X1: IA4 IA3 = 00, address 0. X2: 01, IA3 = 1, address 2³ = 8. X3: 10, IA4 = 1, address 2⁴ = 16. X4: 11, address 16 + 8 = 24. Answer: (C) (0, 8, 16, 24).

Concept: Chip-select lines taken from the middle of the address bus interleave blocks. The trap is (B), which assumes the top two bits (IA11, IA10) select the block.

Next state: Q1+ = Q1 XOR Q3', Q2+ = Q1, Q3+ = Q3 XOR Q2. From (0,1,1): T1 = 0, so (0,0,0). Then (1,0,0), (0,1,0), (1,0,1), (1,1,1), (1,1,0), and back to (0,1,1). The cycle visits 011, 000, 100, 010, 101, 111, 110 - seven states. The only missing state is (0,0,1). Answer: (A) (0, 0, 1).

Concept: Write the next-state equations and trace from the given initial state. T flip-flops toggle when T = 1; the D flip-flop copies Q1. Options (B), (C), (D) all appear in the cycle.

Simplify: A' + A'C' = A', so F = A' + AB'C. B = 0 selects M1: F = A' + AC; inputs indexed by (A, C): 00 gives 1, 01 gives 1, 10 gives 0, 11 gives 1, so X0..X3 = 1, 1, 0, 1. B = 1 selects M2: F = A'; (A, C) = 00, 01 give 1, 10, 11 give 0, so X4..X7 = 1, 1, 0, 0. Answer: (C) (1, 1, 0, 1, 1, 1, 0, 0).

Concept: Split the function on the M3 select variable (B), then fill each 4-input mux with the truth table in its own select order (A as S1, C as S0). Using the wrong select order swaps X1 and X2.

P = 0xC1800000: sign 1, exponent 1000 0011 = 131, so 2^(131-127) = 2⁴, mantissa 0: P = -16. Q = 0x3F5C2EF4: sign 0, exponent 0111 1110 = 126, fraction 0x5C2EF4, Q = 1.f × 2⁻¹. P × Q = -(1.f) × 2³: same fraction, exponent 126 + 4 = 130 = 1000 0010, sign 1. Bits: 1 10000010 then fraction 0x5C2EF4, i.e. 0xC1000000 + 0x5C2EF4 = 0xC15C2EF4. Answer: (C).

Concept: Multiplying by a power of two only changes the exponent (and here the sign); the fraction bits are copied. The trap is forgetting the sign or adding 4 to the wrong field.

Extract-Max removes the root, moves the last element to the root and sifts it down, at most the tree height: O(log n). Insert places the key at the end and sifts it up, again at most the height: O(log n). Neither can be O(1) in the worst case because restoring the heap may need a full root-to-leaf path. Answer: (B) Both run in O(log(n)).

Concept: Finding the max is O(1), but extracting it is O(log n) because of the heapify step. The trap is (D), which confuses Find-Max with Extract-Max.

foo prints after both recursive calls, i.e. in postorder, and each printed value is the sum of the subtree. Postorder: 3, 8, 5, 13, 11, 10. Sums: subtree 3 = 3; subtree 8 = 8; subtree 5 = 5 + 3 + 8 = 16; subtree 13 = 13; subtree 11 = 11 + 0 + 13 = 24; subtree 10 = 10 + 16 + 24 = 50. Output: 3 8 16 13 24 50. Answer: (C).

Concept: Postorder traversal returning subtree sums. The trap is (A), which prints node values in postorder rather than the accumulated sums.

Choose the 2k positions occupied by A ∪ B: C(n, 2k). Fill the other n - 2k positions with the remaining elements: (n - 2k)!. Within the chosen positions, either A takes the first k or B does: 2 ways; then arrange A among its k positions (k!) and B among its k (k!). Total = 2 C(n, 2k) (n - 2k)! (k!)². The two cases are disjoint since k ≥ 1. Answer: (D).

Concept: Positions-first counting. The trap is (C), which forgets that either A or B may come first.

Well-defined: if [x] = [y] then x ∼ y, i.e. f(x) = f(y), so F([x]) does not depend on the representative; (A) is false. Onto: for b ∈ B, f onto gives x with f(x) = b, so F([x]) = b. One-to-one: F([x]) = F([y]) means f(x) = f(y), i.e. x ∼ y, so [x] = [y]. Being injective and surjective, F is bijective. Answer: (B), (C), (D).

Concept: The quotient of a function by its kernel relation is always injective; surjectivity is inherited from f. This is the set-level first isomorphism theorem.

Sequence numbers count bytes and must not wrap around within the maximum segment lifetime. Bytes sent in 2 minutes at 100 Mbps: 100 × 10⁶ / 8 × 120 = 1.5 × 10⁹ bytes. Need 2^b ≥ 1.5 × 10⁹. 2³⁰ ≈ 1.07 × 10⁹ is too small; 2³¹ ≈ 2.15 × 10⁹ suffices. So any length ≥ 31 bits is valid: 32, 34, 36 bits. (The window needed for the 150 ms RTT, about 1.9 MB, is much smaller.) Answer: (B), (C), (D).

Concept: Sequence space must exceed the bytes that can be in flight during one MSL so old segments cannot be confused with new ones. The trap is sizing by RTT instead of MSL.

Symmetric difference is closed on subsets of X and associative (it is XOR of characteristic functions). Identity: AΔ∅ = A. Inverse: AΔA = ∅, so each A is its own inverse. Hence H is a group (an abelian one), (A) true, (B) false. The complement is not the inverse: AΔA' = X ≠ ∅ unless X is empty. Answer: (A) and (D).

Concept: The power set under symmetric difference is a group with identity ∅ in which every element is self-inverse. The trap is guessing the complement as inverse, which gives X, not the identity.

DNS: iterative lookup through root, TLD and authoritative servers costs 3 RTT. Non-persistent HTTP, 5 parallel connections: base HTML needs TCP setup + request = 2 RTT; the 10 objects go in two rounds of 5, each round 2 RTT (new TCP connection + request) = 4 RTT. Total 3 + 2 + 4 = 9 RTT. Persistent HTTP with pipelining: TCP setup 1 RTT, HTML 1 RTT, all 10 objects pipelined in 1 RTT, total 3 + 3 = 6 RTT. Answer: (C) and (D).

Concept: Count RTTs per phase: DNS levels, TCP handshake, each request round. Non-persistent pays a handshake per object; pipelining collapses all object requests into one RTT.

P(A) = 1/4, P(B) = P(C) = 1/2. A ⊆ B, so P(A ∩ B) = 1/4 ≠ P(A)P(B) = 1/8: not independent. Likewise A and C. B ∩ C = A, P = 1/4 = (1/2)(1/2): B and C are independent, which is the same as P(B|C) = P(B ∩ C)/P(C) = (1/4)/(1/2) = 1/2 = P(B). Answer: (C) and (D).

Concept: Independence means P(X ∩ Y) = P(X)P(Y). An event contained in another (A ⊆ B) with probabilities strictly between 0 and 1 is never independent of it.

f1(n) = n + floor(n/2) + floor(n/4) + ... (while the value exceeds 1), which lies between n and 2n, so f1(n) = Θ(n). f2(n) = 100n = Θ(n). Hence f1 ∈ Θ(f2) and f1 ∈ O(n). Since the ratio f1/f2 stays between 1/100 and 1/50 (roughly), it neither tends to 0 nor to infinity, so o and ω are false. Answer: (A) and (D).

Concept: A geometric series n + n/2 + n/4 + ... sums to under 2n, so the halving loop is linear, not n log n. Constant factors like 100 do not affect Θ.

Each vertex receives a color not used by any already-colored neighbour, and later neighbours avoid it in turn, so the coloring is proper: (A). A vertex has at most Δ(G) neighbours, so among the colors 1..Δ(G)+1 at least one is free: (B). (C) fails for a complete graph K_n, where Δ = n - 1 but n colors are needed. (D) fails because greedy depends on the order; e.g. a path a-b-c-d ordered a, d, b, c uses 3 colors though it is 2-colorable. Answer: (A) and (B).

Concept: Greedy coloring is always proper and uses at most Δ + 1 colors, but it is not optimal in general. Complete graphs and odd cycles show Δ colors can be insufficient.

G has 8 vertices. ∅ is a proper subset of every other subset, so ∅ is adjacent to all 7 other vertices. BFS from ∅ visits ∅ first and then discovers all 7 neighbours at level 1; they may be enqueued in any order, and once they are all discovered nothing else remains. So every ordering of the 7 non-empty subsets is a valid BFS order: 7! = 5040. Answer: 5040.

Concept: BFS order freedom comes from the order in which neighbours are enqueued. Because the start vertex is adjacent to everything, the count is simply 7!.

A row has 128 elements, so one page holds 4 rows; the array spans 128/4 = 32 pages. The inner loop walks down column i, touching rows 0..127, i.e. pages 0..31 in order (4 consecutive accesses per page). With only 30 frames under LRU, a cyclic reference to 32 pages faults on every new page: when page p is needed again it was the least recently used one evicted. So each outer iteration causes 32 faults: 128 × 32 = 4096. Answer: 4096.

Concept: Column-wise access to a row-major array crosses pages constantly. LRU with fewer frames than the cyclic working set degenerates to a fault on every page change.

Page size 4 KB = 2¹² bytes, so the offset uses 12 bits and the virtual page number has 57 - 12 = 45 bits. Each page-table page fits in one page: 4096 / 8 = 512 = 2⁹ entries, so each level resolves 9 bits. Levels L = 45 / 9 = 5. Answer: 5.

Concept: Multi-level paging: bits per level = log2(page size / PTE size). This 57-bit, 5-level layout is exactly x86-64 five-level paging.

I: S (bottom to top) = 1 5 7 8 9 2. II: Q (front to back) = 1 5 7 8 9 2. III: pop 2, S = 1 5 7 8 9. IV: dequeue 1. V: pop 9, S = 1 5 7 8. VI: dequeue 5, Q = 7 8 9 2. VII: dequeue 7, push: S = 1 5 7 8 7. VIII: three more times: push 8, 9, 2, S = 1 5 7 8 7 8 9 2. IX: pop 2. X: pop 9. Top of S = 8. Answer: 8.

Concept: Careful simulation of LIFO vs FIFO. The usual error is miscounting "repeat VII three times" as three in total rather than three more after VII.

Integer part "10": I(1) = 1, then I(10) = 2 × 1 + 0 = 2. Fraction part "011" is right-recursive: F(1) = 1/2 × 1 = 0.5; F(11) = 1/2 × (1 + 0.5) = 0.75; F(011) = 1/2 × (0 + 0.75) = 0.375. N.val = 2 + 0.375 = 2.375 (binary 10.011). Answer: 2.375 (key range 2.374 to 2.376).

Concept: The scheme converts a binary fixed-point string to decimal: left recursion doubles for integer digits, right recursion halves for fractional digits. Evaluate F from the rightmost digit.

Female students: rollNum 2 (70), 3 (80), 5 (65). marks > 65 is strict, so Swati with 65 is excluded. Rows returned: rollNum 2 and 3. Duplicated names do not matter since SELECT * returns whole rows. Answer: 2.

Concept: Straightforward WHERE filtering; the traps are the strict inequality at 65 and wondering whether the duplicate name "Aliya" collapses rows (it does not without DISTINCT, and rows differ anyway).

Records per data block = floor(1024/100) = 10, so data blocks = 25000/10 = 2500. The primary (sparse) index has one entry per data block: 2500 entries of 15 + 5 = 20 bytes. Entries per index block = floor(1024/20) = 51, so index blocks = ceil(2500/51) = 50. Binary search on the index: ⌈log2 50⌉ = 6 block accesses, which identifies the data block. Answer: 6.

Concept: A primary index is sparse: one entry per data block, not per record. The question stops at identifying the block, so the extra data-block access (7) is not counted.

Track the number of consecutive trailing 1s: state 0 (none), state 1 (one 1), state 2 (two 1s); all three are accepting. A 0 returns to state 0; a 1 moves 0 to 1 to 2, and from 2 to a dead state D (three 1s seen), which loops on both symbols. The four states are pairwise distinguishable: from 0, 1, 2 the strings 111, 11, 1 respectively are the shortest that lead to rejection, and D rejects everything. Minimum states: 4. Answer: 4.

Concept: Count states by what must be remembered: the current run of 1s (0, 1, 2) plus a dead state. Forgetting the dead state gives 3, which is the usual mistake for a complete DFA.

Let the block size be 2^b bytes. Number of sets = cache size / (ways × block size) = 2¹⁶ / (2³ × 2^b) = 2^(13 - b), so INDEX = 13 - b bits and OFFSET = b bits. INDEX + OFFSET = 13 regardless of block size. TAG = 32 - 13 = 19. Answer: 19.

Concept: Index + offset bits equal log2(cache size / associativity), so the block size, which is not given, cancels out. Students often stall looking for the missing block size.

AND the destination with each mask. /16: 200.150.0.0, matches (interface 1). /19 (255.255.224.0): 68 AND 224 = 64, giving 200.150.64.0, matches (interface 2). /24: 200.150.68.0, matches (interface 3). /27 (255.255.255.224): 118 AND 224 = 96, giving 200.150.68.96 ≠ 200.150.68.64, no match. Longest prefix match is the /24 entry. Answer: 3.

Concept: Longest prefix matching: among all matching entries choose the longest mask. The trap is assuming 200.150.68.64/27 covers .118; that subnet is .64 to .95.