GATE 2016 CS (Computer Science) Set 1 question paper with solutions

'Until' already carries the negative sense of 'up to the time when', so adding 'does not' after it creates a double negative and changes the meaning (options A and B are wrong). The subject 'the minister' is third person singular, so the present-tense verb must be 'meets', not 'meet' (option C is wrong). 'I will not leave the place until the minister meets me' is correct. Answer: (D).

Concept: Tests subject-verb agreement and the use of 'until'. The trap is the double negative 'until ... does not', which sounds natural in some spoken Indian English but is ungrammatical.

A paraphrase restates a text or speech in other words. A paradox is a self-contradictory statement, a paradigm is a model or pattern, and paraffin is a wax or fuel. Answer: (A) paraphrase.

Concept: Vocabulary question built on look-alike words sharing the prefix 'para-'. Only the meaning matters; do not be distracted by the similar spelling.

Archimedes is not literally proposing to move the Earth; he uses an exaggerated image to express the power of the lever. A statement that uses words in a non-literal, imaginative sense is figurative. 'Literal' is the opposite, 'collateral' means secondary or accompanying, and a 'figurine' is a small statue. Answer: (A) figurative.

Concept: Distinguishes figurative from literal language. The distractor 'figurine' looks like 'figurative' but is a noun meaning a statuette.

All three words share 'taga', which must mean 'care'. In each, 'care' comes first in English but 'taga' comes last in the coded word: relf = free, o = ful, fer = less, so the coded word reverses the English order (modifier + taga). In 'aftercare', 'care' is the last English part, so 'taga' must come first, followed by a new code for 'after'. Only 'tagazen' has that form ('zen' = after). Answer: (C) tagazen.

Concept: Coded-language reasoning: identify the common root and, crucially, the word order. The trap is 'zentaga', which keeps 'taga' at the end as in the examples but ignores that the English order is reversed.

64 unit blocks form a 4 x 4 x 4 cube with surface area 6 x 16 = 96. Removing a corner block takes away its 3 exposed unit faces, but exposes 3 new unit faces of the neighbouring blocks (the inner faces of the notch). The net change per corner is 0, so the surface area stays 96. Answer: (D) 96.

Concept: Visualising surface area after removing corner blocks. The trap is subtracting 3 faces per corner (giving 72) and forgetting the 3 newly exposed faces.

Annual units: Elegance 27300+25222+28976+21012 = 102510; Smooth 20009+19392+22429+18229 = 80059; Soft 17602+18445+19544+16595 = 72186; Executive 9999+8942+10234+10109 = 39284. Revenue: Elegance 102510 x 48 = 4,920,480; Smooth 80059 x 63 = 5,043,717; Soft 72186 x 78 = 5,630,508; Executive 39284 x 173 = 6,796,132. Executive has the largest revenue, hence the greatest fraction. Answer: (B) Executive.

Concept: Revenue = price x quantity. The trap is picking Elegance because it sells the most units; the much higher price of Executive outweighs its lower volume.

The passage says 'at least seventeen', so 'exactly seventeen' (A) is wrong. 'If this is not an indication ..., nothing else is' is a rhetorical way of saying the multilingual notes are a very strong indicator, not the only possible one, so (B) overstates it. Nothing is said about space on notes (C). The claim is simply that linguistic plurality strongly evidences India's diversity. Answer: (D).

Concept: Inference questions reward the option that follows without adding information. The traps are absolute words ('exactly', 'only') that go beyond the passage.

(ii): Statement III says S loses to P only sometimes, so S sometimes beats P. S cannot be the absolute worst player, so (ii) fails. (i): The chain P > Q > R > S suggests P is strong, but no statement relates P directly to R, and S beats P part of the time. Winning in poker is not transitive, so 'P is likely to beat all three' cannot be logically inferred from the given statements. Neither inference follows. Answer: (D) neither (i) nor (ii).

Concept: Tests whether you assume transitivity where none is given. The trap is chaining P > Q > R > S into conclusions about pairs the statements never compare, and ignoring that S beats P sometimes.

By the factor theorem, (x - c) is a factor iff f(c) = 0. f(1) = 2 + 3 - 5 = 0, so (x - 1) is a factor. Check the others: f(-1) = -2 - 3 - 5 = -10 ≠ 0; f(5/2) is clearly positive and large; x³ + 8 has root x = -2 and f(-2) = -256 - 6 - 5 ≠ 0. Answer: (B) (x - 1).

Concept: Factor theorem: substitute the root of each candidate factor. A quick check of x = 1 (sum of coefficients equals zero) settles it immediately.

Let N = A·e^(-kL). From N(80) = 100 and N(40) = 10000: N(40)/N(80) = e^(40k) = 100, so k = ln 100 / 40. For N = 5000: N(40)/N(L) = 10000/5000 = 2 = e^(k(L - 40)), so L - 40 = ln 2 / k = 40 · ln 2 / ln 100 = 40 × 0.30103 / 2 = 6.02. L = 46.02. Answer: (B) 46.02.

Concept: Exponential decay model fitted from two points, solved with logarithms. The trap is assuming linear interpolation between 40 and 80, which gives a very different load.

¬((p → q) ∧ (¬r ∨ ¬s)) = ¬(p → q) ∨ ¬(¬r ∨ ¬s) = (p ∧ ¬q) ∨ (r ∧ s). r ∧ s needs x to be both a perfect square and a prime, which is impossible. So we need p ∧ ¬q: x ∈ {8, 9, 10, 11, 12} and x not composite. Since x ≥ 2, not composite means prime; the only prime in the set is 11. Answer: 11.

Concept: Applying De Morgan's law and ¬(p → q) ≡ p ∧ ¬q. The trap is mis-negating the implication as ¬p → ¬q or forgetting that r ∧ s is unsatisfiable.

Classify valid n-bit strings by their last bit. If it ends in 0, the first n-1 bits form any valid string: aₙ₋₁ ways. If it ends in 1, the bit before must be 0, and the first n-2 bits form any valid string: aₙ₋₂ ways. So aₙ = aₙ₋₁ + aₙ₋₂ (with a₁ = 2, a₂ = 3). Answer: (B).

Concept: Standard Fibonacci-type recurrence from case analysis on the last bit. The trap is counting the '1' ending as aₙ₋₁ without forcing the preceding 0.

Substitute t = x - 4; as x → 4, t → 0. The limit becomes lim (t→0) sin t / t = 1. Answer: 1.

Concept: The standard limit sin t / t → 1 after a shift of variable. The trap is substituting x = 4 directly and stopping at the indeterminate form 0/0.

A pdf must integrate to 1: ∫ from a to 1 of x⁻² dx = [-1/x] from a to 1 = -1 + 1/a = 1. So 1/a = 2 and a = 0.5. Answer: 0.5.

Concept: Normalisation condition of a probability density function. The trap is a sign slip in the antiderivative -1/x.

For a real matrix, complex eigenvalues occur in conjugate pairs, so the third eigenvalue is 2 - i. The determinant is the product of eigenvalues: (2 + i)(2 - i) × 3 = (4 + 1) × 3 = 15. Answer: 15.

Concept: Real matrices have conjugate-paired complex eigenvalues, and det = product of eigenvalues. The trap is treating the given two as all the information and multiplying (2 + i) × 3.

The properties give the truth table: y = 0 gives x, y = 1 gives x̄. So x # y = 1 exactly when x ≠ y, which is XOR: x # y = xȳ + x̄y. Check: x # x = 0 and x # x̄ = 1 hold. Answer: (A).

Concept: Recognising XOR from its identities. The trap is option (D), XNOR, which gives x # x = 1.

The MSB is 1, so the number is negative. Its magnitude is the 2's complement: invert 1111 1111 1111 0101 to get 0000 0000 0000 1010, add 1 to get 0000 0000 0000 1011 = 11. So the value is -11. Answer: -11.

Concept: Reading a negative 2's complement number. The trap is reading it as unsigned (65525) or forgetting to add 1 after inverting (giving -10).

The sequence has 6 distinct steps (the three 0s are different states because each is followed by a different value). Distinguishing 6 states needs ⌈log₂ 6⌉ = 3 flip-flops, with combinational logic decoding the output; this gives 3. If instead the counter's output must come directly from flip-flops, the 2 value bits are not enough to tell the three 0 states apart and an extra state bit is needed, giving 4. The official key accepts 3 to 4. Answer: 3 (or 4).

Concept: A counter with repeated output values needs extra state to remember its position. The trap is answering 2 because the largest output value is 3.

4 GB = 2³² bytes. Each address refers to one word of 2 bytes, so the number of addressable units is 2³² / 2 = 2³¹. The address bus needs log₂(2³¹) = 31 bits. Answer: 31.

Concept: Address width depends on the number of addressable units, not bytes. The trap is answering 32 by ignoring word addressing.

Use a circular array with front and rear indices. ENQUEUE writes at rear and advances rear modulo the array size; DEQUEUE reads at front and advances front modulo the size. Neither shifts elements, so both run in O(1). Answer: (A).

Concept: Circular buffer implementation of a queue. The trap is imagining a linear array that shifts elements on every dequeue, which costs Ω(n).

a is the only source, so it comes first; f is the only sink, so it comes last. In between, b must precede c and d must precede e, with no constraint between the two chains. The number of interleavings of two chains of length 2 is C(4, 2) = 6. Answer: 6.

Concept: Counting topological orders as interleavings of independent chains. The trap is listing orders by hand and missing some, or treating b, c, d, e as freely permutable (24).

s is a short, not a pointer, so *s is invalid; this rules out (A) and (C). f returns void, so assigning its result to i is a type error; this rules out (B). In (D), i is int and *p dereferences a short pointer to give a short, matching f(int, short). Answer: (D) f(i,*p).

Concept: Type checking of function calls: argument types, dereferencing only pointers, and void return values. The trap is (B), which looks harmless but uses a void result as a value.

Insertion sort: a reverse-sorted input forces i shifts for the i-th element, Θ(n²). Merge sort always splits in half and merges in linear time, Θ(n log n) in every case. Quick sort: with consistently bad pivots (e.g. sorted input with first-element pivot) partitions are of size n-1 and 0, Θ(n²). Answer: (D).

Concept: Worst-case complexities of the standard sorts. The trap is quoting quick sort's average Θ(n log n) as its worst case.

P: Every spanning tree has exactly V - 1 edges, so adding c to each edge adds (V - 1)c to every tree; the relative order of edge weights (which Kruskal uses) is unchanged. The MST stays the same. P is true. Q: Paths have different numbers of edges, so a path with k edges increases by kc. Example: A-B weight 3 directly vs A-C-B with weights 1 + 1 = 2. Adding 2 to each edge gives 5 vs 6, so the shortest path changes. Q is false. Answer: (A) P only.

Concept: MSTs depend only on the order of weights; shortest paths depend on sums over paths of different lengths. The trap is assuming both are invariant.

mystery swaps its local copies of the pointers, never the values they point to (it never writes through *ptra or *ptrb). So no call changes a, b, c or d. a stays 2016; a < c is false so the second call is skipped anyway; the third call also changes nothing. Output: 2016.

Concept: C passes pointers by value: swapping the pointer variables inside a function has no effect on the caller. The trap is assuming a swap of the integers happened.

Each step prepends either a or b, in any order, and ε ends the derivation. So any string over {a, b} of any length, including ε, can be generated, e.g. ba via S ⇒ bS ⇒ baS ⇒ ba. The language is {a, b}*. Answer: (D).

Concept: Reading a right-linear grammar. The trap is (A), which forbids b before a, though the grammar allows a and b in any order.

I: Build the product automaton for the intersection and test reachability of a final state; decidable. II: CFG membership is decidable (convert to CNF and use CYK). III: Equivalence of two CFGs is undecidable. IV: Emptiness of a TM's language is a non-trivial property of RE languages, undecidable by Rice's theorem. Undecidable: III and IV. Answer: (C).

Concept: Know the decidability table: regular languages are closed and decidable for everything; CFLs have decidable membership and emptiness but undecidable equivalence; TM language properties are undecidable.

A string must contain 00 somewhere and 11 somewhere, in either order, possibly far apart. (B) says: anything, then either 00 ... 11 or 11 ... 00, then anything; this captures exactly that. (A) forces 00 and 11 to be adjacent (it misses strings like 001011, where 00 and 11 are separated). (C) is 'contains 00 OR 11'. (D) forces the string to start with 00 or 11 and end with the other. Answer: (B).

Concept: Expressing an AND of two substring conditions with a regex requires both orderings. The trap is (C), which is a union (OR) rather than an intersection.

In SSA each variable is assigned exactly once, so every assignment gets a fresh name: x1 = u - t y1 = x1 * v x2 = y1 + w y2 = t - z y3 = x2 * y2 Variables used: the inputs u, t, v, w, z (5) plus x1, y1, x2, y2, y3 (5). Total = 10. Answer: 10.

Concept: SSA renames every definition. The trap is forgetting to count the original input variables (giving 5) or trying to reuse a temporary name.

When all processes arrive together, running them in increasing order of burst length (SJF) minimises the average waiting time, by an exchange argument. With simultaneous arrival, SRTF behaves exactly as SJF. Round-robin interleaves jobs and delays all of them; random order is not optimal; priority proportional to burst length runs the longest first, the worst order. Answer: (A).

Concept: SJF/SRTF is optimal for average waiting time. The trap is option (D), whose wording sounds like SJF but actually favours long bursts.

A superkey is any attribute set containing a key. With no other information, a set is guaranteed to be a superkey if it contains both V and Y. VXYZ, VWXY and VWXYZ all contain V and Y. VWXZ lacks Y. Answer: (B) VWXZ.

Concept: Superkey = superset of a candidate key. The trap is over-thinking about other dependencies; only containment of VY is guaranteed.

ACID stands for Atomicity, Consistency, Isolation and Durability. Deadlock-freedom is a property of some concurrency-control protocols, not one of the ACID properties. Answer: (D).

Concept: Recall of the ACID acronym; the missing D is Durability, which the distractor tries to replace with Deadlock-freedom.

Old schema: (VOLUME, NUMBER) → YEAR has a proper subset of the key determining a non-prime attribute, a partial dependency. So the old schema is in 1NF but not 2NF. New schemas: in the first, the full key determines TITLE and PRICE; in the second, (VOLUME, NUMBER) is the key and determines YEAR. Every determinant is a key, so both are in BCNF, hence also in 2NF. The weakest normal form satisfied by the new design but not by the old is 2NF. Answer: (B).

Concept: Partial dependencies violate 2NF. The trap is answering BCNF because the new design is in BCNF; the question asks for the weakest form that separates the two.

DNS maps host names to IP addresses; ARP maps IP addresses to MAC addresses; RARP maps MAC addresses to IP addresses. DHCP dynamically assigns IP addresses and configuration to hosts; it does not translate one existing address form into another. Answer: (C) DHCP.

Concept: Distinguishing address resolution from address allocation. The trap is thinking of DHCP as a MAC-to-IP lookup like RARP; it is an allocation protocol.

HTTP is stateless: each request is independent (state is added via cookies, outside the protocol). TCP is stateful but is a transport-layer protocol, not application layer. FTP keeps session state (login, current directory, transfer mode) across commands, and POP3 keeps session state (authorization, transaction, update states). Stateful application-layer protocols: FTP and POP3. Answer: (C).

Concept: Know which protocols maintain server-side session state and at which layer each operates. The traps are HTTP (stateless) and TCP (stateful but transport layer).

(x³ + x⁴ + ···)³ = x⁹ (1 + x + x² + ···)³ = x⁹ (1 - x)⁻³. We need the coefficient of x³ in (1 - x)⁻³, which is C(3 + 2, 2) = C(5, 2) = 10. Check by counting: solutions of a + b + c = 12 with each ≥ 3 equal solutions of a' + b' + c' = 3 with each ≥ 0, which is C(5, 2) = 10. Answer: 10.

Concept: Generating functions / stars and bars with lower bounds. The trap is forgetting to factor out x⁹ or using C(n + k, k) with the wrong n.

Note that 6(1)² + 2(1) = 8 = a₁, so aₙ = Σ (k = 1 to n) (6k² + 2k). Σ 6k² = 6 · n(n + 1)(2n + 1)/6 = n(n + 1)(2n + 1); Σ 2k = n(n + 1). aₙ = n(n + 1)(2n + 1 + 1) = 2n(n + 1)². a₉₉ = 2 × 99 × 100² = 1,980,000 = 198 × 10⁴. K = 198 (key range 197.9 to 198.1). Answer: 198.

Concept: Unrolling a recurrence into standard power sums. The trick is noticing a₁ fits the same formula, so the sum can start at k = 1; otherwise an off-by-8 slip is easy.

Both rules preserve divisibility by 5 (halving an even multiple of 5 keeps it a multiple of 5; adding 5 too), so multiples and non-multiples of 5 never mix. Non-multiples: 1 → 6 → 3 → 8 → 4 → 2 → 1, so f(1) = f(2) = f(3) = f(4) = f(6) = f(8). Any other non-multiple n descends into this cycle: an odd n > 5 gives (n + 5)/2 < n after halving, and an even n halves, so the value strictly decreases until it lands in {1, 2, 3, 4, 6, 8}. All non-multiples share one value. Multiples of 5: 5 → 10 → 5, and every 5m reduces the same way to 5. All share one value. So f takes at most 2 distinct values. Answer: 2.

Concept: Find the invariant (residue class mod 5) and show each class collapses to one cycle. The trap is assuming one value per residue mod 5, giving 5.

Each round: P(Y) = 1/4, P(N) = 2/4, P(repeat) = 1/4. Let p = P(output Y). Then p = 1/4 + (1/4)p, so (3/4)p = 1/4 and p = 1/3 ≈ 0.33. Equivalently, conditioned on stopping, Y has 1 of the 3 stopping outcomes. Answer: 0.33 (key 0.33 to 0.34).

Concept: Repeated trials with a restart: condition on the process stopping. The trap is answering 0.25 by ignoring the restarts.

First MUX: output = P̄·0 + P·R = PR. Second MUX: X = Q̄·R̄ + Q·(PR) = Q̄R̄ + PQR. The two terms share no adjacent minterms that would allow further merging (Q̄R̄ covers minterms with Q = 0, R = 0; PQR has Q = 1, R = 1), so this is minimal. Answer: (D).

Concept: A 2-to-1 MUX computes s̄·I0 + s·I1; cascade by substitution. The trap is mixing up which input is selected by 0 versus 1.

A 16-bit count register allows at most 2¹⁶ bytes = 64 KB per DMA transfer (one bus grant in burst mode). Number of grants = ⌈29154 KB / 64 KB⌉ = ⌈455.53⌉ = 456. Answer: 456.

Concept: The count register limits the block size per DMA operation. The trap is rounding down to 455 and leaving the last partial block untransferred.

Pipeline clock period = slowest stage. Old: max(800, 500, 400, 300) = 800 ps. New stages 600, 350, 500, 400, 300: max = 600 ps. Throughput is 1/period, so the ratio is 800/600 = 1.333, an increase of 33.33%. Answer: 33.33 (key 33 to 34).

Concept: Throughput is set by the bottleneck stage. The trap is computing the change in period (25%) instead of the change in throughput.

A carry lookahead adder computes each carry as cᵢ = Gᵢ + PᵢGᵢ₋₁ + ... + PᵢPᵢ₋₁...P₀c₀, which involves AND/OR terms of up to about n inputs. With gates of fan-in at most 2, an n-input AND or OR must be built as a binary tree of depth Θ(log n). So the addition takes Θ(log n) time. Answer: (B).

Concept: With unlimited fan-in the CLA would be Θ(1) depth; the fan-in-2 restriction forces logarithmic trees. The trap is answering Θ(1) from the textbook 'constant time' claim.

Each iteration discards the smaller of p[a] and p[b] (moving a right or b left), so the maximum always stays within [a, b]. When a == b only one candidate remains, and it is the maximum, so the loop must run while b != a. (A) and (B) let a or b run past each other. (C) stops with two candidates left and returns p[a] even if p[b] is larger, e.g. p = {1, 2}. Answer: (D) b != a.

Concept: Loop invariant reasoning: the maximum lies in p[a..b]. The trap is (C), which stops one step early.

d is static, so all calls share one d, initialised once. count(3): prints 3 1; d = 2; calls count(2). count(2): prints 2 2; d = 3; calls count(1). count(1): prints 1 3; d = 4; no call; prints 4. Back in count(2): prints 4. Back in count(3): prints 4. Output: 3 1 2 2 1 3 4 4 4. Answer: (A).

Concept: Static locals persist across recursive calls; the final printf runs on the way back up, once per call. The traps are treating d as fresh per call or forgetting the unwinding prints.

Move the last element of the array into position i and shrink the heap. The moved element may violate the heap property with its parent or its children, so sift it up or down as needed. Either direction moves along a single root-to-leaf path, at most d swaps, so O(d). It is not O(1) in general, since the element may need to travel the full height. Answer: (B).

Concept: Arbitrary deletion in a heap = replace with last element, then heapify up or down along one path. The trap is thinking the whole heap must be rebuilt (O(2ᵈ), i.e. O(n)).

Edges: {1,2} = 2, {1,3} = 8, {1,4} = 5, {2,3} = 5, {2,4} = 8, {3,4} = x. The edge {3,4} is most useful for the pair (3, 4). Without it, the shortest 3-4 route is 3-2-1-4 = 5 + 2 + 5 = 12 (3-1-4 and 3-2-4 cost 13). So the direct edge lies on a shortest path whenever x ≤ 12 (at x = 12 it ties, and 'at least one shortest path' still includes it). For other pairs the edge would need a much smaller x (e.g. for (1,3), 5 + x ≤ 7 needs x ≤ 2). Largest integer x = 12. Answer: 12.

Concept: An edge lies on some shortest path iff its weight does not exceed the best alternative between its endpoints. The trap is using strict inequality and answering 11.

Kruskal always takes edges 1 and 2 (two edges cannot form a cycle). To make the MST heavy, edge 3 should close a cycle: place edges 1, 2, 3 as a triangle on three vertices, so edge 3 is rejected. The fourth vertex is joined by edges 4, 5, 6, and Kruskal takes 4. MST weight = 1 + 2 + 4 = 7. If edges 1 and 2 do not form a path with 3 completing a triangle, edge 3 is accepted and the weight is only 1 + 2 + 3 = 6. Maximum = 7. Answer: 7.

Concept: Adversarial edge placement against Kruskal's algorithm. The trap is answering 6 + 5 + 4 or ignoring that edges 1 and 2 are always chosen.

II is the cycle property: if e is the unique heaviest edge on a cycle and some spanning tree contains e, removing e and adding another edge of that cycle reconnecting the tree gives a lighter spanning tree. So no MST contains e. II is true. I is false: an edge can be the lightest on one cycle and the heaviest on another. Take vertices X, Y, Z, W with XY = 1, YZ = 2, XZ = 3, ZW = 4, WX = 5. XZ = 3 is the lightest edge of cycle X-Z-W, yet it is the heaviest edge of triangle X-Y-Z, so by the cycle property no MST contains it (the MST is XY, YZ, ZW). Answer: (B) II only.

Concept: Cycle property: the unique heaviest edge of any cycle is in no MST. The trap is believing the converse for the lightest edge; an edge can be lightest on one cycle and heaviest on another.

The loop builds a non-decreasing stack: an element is pushed only if it is not smaller than the top; otherwise the top is popped and sent to the back of the queue. The worst case is when the smallest element is last, e.g. 1, 2, ..., 15, 0 (with n = 16). The first 15 elements are pushed (15 iterations), then 0 forces all 15 to be popped back to the queue (15 iterations), then 0 is pushed, and the 15 elements cycle again; each 'round' fixes one more element. Counting all rounds gives n² iterations; a brute-force check over all permutations for n = 1..7 confirms the maximum is exactly n². For n = 16: 16² = 256. Answer: 256.

Concept: Analysing a stack-queue sorting loop for its worst-case input. The trap is answering 2n or n(n+1)/2 by counting only pushes, not the pops that send elements back to the queue.

G1: S generates a* followed by B, and B generates b⁺. So L(G1) = a*b⁺ = {aᵐbⁿ | m ≥ 0 and n > 0}. G2: B generates b*. A generates a* b*. S → aA gives a⁺b*; S → bB gives b⁺. So L(G2) = a⁺b* ∪ b⁺ = all non-empty aᵐbⁿ = {aᵐbⁿ | m > 0 or n > 0}. Answer: (D).

Concept: Translate each nonterminal into a regular expression bottom-up. The trap is missing that G2 cannot generate ε (S has no ε-production) while it can generate strings with only b's.

Acceptance is by final state. Staying in q0, the PDA reads a's and pushes an X for each; since q0 is final, every aⁿ (n ≥ 0) is accepted. On b it pops an X and moves to q1, popping one X per b; when Z is exposed it moves by ε to final q2. So aⁿbⁿ (n ≥ 1) is accepted, and more b's than a's or fewer get stuck or end in non-final q1. L = {aⁿ | n ≥ 0} ∪ {aⁿbⁿ | n ≥ 0}. The machine is deterministic: in each state, for each input/stack-top pair at most one move exists, and the ε-move in q1 is only on Z, where no b-move exists. So L is deterministic context-free. Answer: (D).

Concept: Read acceptance by final state carefully: the accepting start state adds all aⁿ. The trap is (A), forgetting q0 is final, or (B), assuming a union forces nondeterminism.

Y is RE but not recursive, so its complement Ȳ is not RE (if both Y and Ȳ were RE, Y would be recursive). If A ≤m B and B is RE then A is RE; contrapositively, Ȳ ≤m W with Ȳ not RE means W is not RE. X is recursive, so X̄ is recursive. If Z ≤m X̄ and X̄ is recursive, then Z is recursive. So W is not RE and Z is recursive. Answer: (C).

Concept: Reductions transfer decidability downward and undecidability upward; plus the fact that the complement of an RE-but-not-recursive language is not RE. The trap is missing the complement bars on Y and X.

* has the lowest precedence, so it is applied last: (2 - 5 + 1 - 7) * 3. + has the highest precedence: 5 + 1 = 6, giving 2 - 6 - 7. - is right-associative: 2 - (6 - 7) = 2 - (-1) = 3. Then 3 * 3 = 9. Answer: 9.

Concept: Parsing with non-standard precedence and associativity. The trap is applying the usual rules (giving -30) or treating - as left-associative (giving -33 after multiplying).

The derivation of aab is S ⇒ aA ⇒ aSb ⇒ aab. A bottom-up parser performs the reductions in reverse of this rightmost derivation: 1. Reduce the second a to S by S → a: print 2. 2. Reduce Sb to A by A → Sb: print 3. 3. Reduce aA to S by S → aA: print 1. Output: 2 3 1. Answer: (C).

Concept: Bottom-up parsing executes actions at reductions, i.e. the reverse rightmost derivation. The trap is printing in top-down (derivation) order, giving 1 3 2.

Page size = 16 KB = 2¹⁴ bytes. Number of pages = 2⁴⁰ / 2¹⁴ = 2²⁶ entries. Each entry is 48 bits = 6 bytes. Table size = 2²⁶ × 6 bytes = 6 × 64 MB = 384 MB. Answer: 384.

Concept: Page table size = number of virtual pages × entry size. The trap is using 48 as bytes or forgetting to convert bits to bytes.

C-LOOK services requests upward from 63: 87, 92, 121, 191. Movement 191 - 63 = 128. It then jumps to the lowest pending request, 10: movement 191 - 10 = 181. It then services upward: 11, 38, 47. Movement 47 - 10 = 37. Total = 128 + 181 + 37 = 346. Answer: 346.

Concept: C-LOOK reverses only as far as the last request and jumps to the lowest pending one; the jump is counted as head movement here. The trap is going to cylinder 199 or 0 (C-SCAN) or skipping the jump distance.

LIFO: a₁..a₁₀ fill the frames (10 faults). a₁₁..a₂₀ each replace the most recently loaded page (10 faults), leaving a₁..a₉ fixed plus a₂₀. Second pass: a₁..a₉ hit; a₁₀..a₂₀ are 11 faults. Total 31. Optimal: first pass 20 faults; for a₁₁ onward it evicts the page used farthest ahead, which keeps a₁..a₉ plus the latest page, ending with {a₁..a₉, a₂₀}. Second pass: a₁..a₉ hit; a₁₀..a₁₉ fault (10), each evicting a dead page, and a₂₀ is still resident, a hit. Total 30. Difference = 31 - 30 = 1. Answer: 1.

Concept: Simulating LIFO and OPT on a cyclic reference string. The trap is assuming LIFO is far worse; both keep a₁..a₉ resident, and they differ only on a₂₀ in the second pass.

This is Lamport's bakery algorithm without the tie-break on process id. The c[j] wait ensures Pi sees Pj's final ticket. Pi enters only after every other process j has t[j] = 0 or t[j] > t[i]; two processes cannot both see the other's ticket as strictly larger, so mutual exclusion holds: (A) is true. But two processes can compute pmax concurrently and receive the same ticket. Then each sees t[j] <= t[i] and waits for the other forever: a deadlock. So (D) is false, and progress (C) and bounded waiting (B) fail. Answer: (A).

Concept: The bakery algorithm needs the (ticket, id) tie-break; without it equal tickets deadlock, but safety still holds. The trap is assuming it is a correct bakery algorithm and picking (D).

All locks are acquired before any is released, so the protocol is two-phase locking (in fact conservative/strict), which guarantees conflict serializability. All transactions acquire locks in the same global order (increasing address). A wait-for cycle would require some transaction to hold a higher-addressed lock while waiting for a lower one, which the ordering forbids. So no deadlock can occur. Answer: (A).

Concept: 2PL gives serializability; a global lock ordering removes circular wait. The trap is recalling that basic 2PL can deadlock and missing the ordered acquisition.

A digital signature is created by the sender encrypting the message digest with the sender's own private key, so anyone (here A) can verify it with the sender's public key K_B⁺. B is the sender, so the signature is K_B⁻(H(m)), sent along with m. B does not have A's private key, and encrypting with a public key gives confidentiality, not authentication. Answer: (B).

Concept: Signing uses the signer's private key; verification uses the signer's public key. The trap is confusing signing with encryption for confidentiality (receiver's public key).

Data in the datagram = 1000 - 20 = 980 bytes. Each fragment carries at most 100 - 20 = 80 data bytes, and 80 is a multiple of 8, as fragment offsets require. Fragments = ⌈980 / 80⌉ = ⌈12.25⌉ = 13 (12 of 80 bytes and one of 20 bytes). Answer: 13.

Concept: Fragment by data payload, with each fragment's data a multiple of 8 except the last. The trap is dividing 1000 by 100 (giving 10) and forgetting the header repeats in every fragment.

Burst phase: sending at 20 MB/s while tokens arrive at 10 MB/s drains the full 1 MB bucket at a net 10 MB/s, so the burst lasts S = C / (M - ρ) = 1 / (20 - 10) = 0.1 s, sending 20 × 0.1 = 2 MB. The remaining 10 MB go at the token rate, 10 MB/s: 1 s. Total = 0.1 + 1 = 1.1 s. Answer: 1.1.

Concept: Token bucket burst length S = C / (M - ρ). The trap is computing 12 / 20 = 0.6 s, ignoring that the bucket empties and the rate then falls to the token rate.

Frame transmission time = 8000 bits / 80000 bps = 0.1 s. ACK transmission time = 800 bits / 8000 bps = 0.1 s. Propagation: 0.1 s each way, 0.2 s total. Cycle per frame = 0.1 + 0.1 + 0.1 + 0.1 = 0.4 s. Throughput = 1000 bytes / 0.4 s = 2500 bytes/second. Answer: 2500.

Concept: Stop-and-wait cycle time includes the ACK's transmission time when it is not negligible. The trap is ignoring the ACK time and getting 1000 / 0.3 ≈ 3333.