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

The blank names a job he held before becoming Municipal Commissioner. "A security guard" is right because he was one of many guards (indefinite). "The university" is right because a specific, identifiable university is meant. So the phrase is "a security guard at the university". Answer: (B).

Concept: Definite versus indefinite article. A job held among many people takes "a"; a specific place takes "the". The trap is "the security guard", which implies he was the only guard.

"Cope with" means to deal with or endure a difficult situation. "Put up with" means to tolerate or endure. "Put down to" means to attribute, "put up against" means to pit against, and "put in with" is not an idiom with this sense. Answer: (A) put up with.

Concept: Phrasal-verb meaning in context. All options share "put", so only the particle decides the meaning; only "put up with" carries the sense of enduring.

Mock, deride and jeer all mean to ridicule or scorn. Praise means to express approval, the opposite sense. Answer: (C) praise.

Concept: Odd-one-out by meaning: three near-synonyms and one antonym. Knowing that "deride" means ridicule is the only hurdle.

Write letter positions. CADBE = 3,1,4,2,5: steps -2,+3,-2,+3. JHKIL = 10,8,11,9,12: -2,+3,-2,+3. XVYWZ = 24,22,25,23,26: -2,+3,-2,+3. ONPMQ = 15,14,16,13,17: -1,+2,-3,+4. Only ONPMQ breaks the pattern. Answer: (D) ONPMQ.

Concept: Letter-series pattern: convert letters to alphabet positions and compare the differences. Judging by the look of the letters instead of the step sizes is the trap.

α⁻ⁿ + β⁻ⁿ = 1/αⁿ + 1/βⁿ = (αⁿ + βⁿ)/(αβ)ⁿ. So the ratio is (αⁿ + βⁿ) × (αβ)ⁿ/(αⁿ + βⁿ) = (αβ)ⁿ = 4ⁿ. Answer: (B) 4ⁿ.

Concept: Negative powers combine over the common denominator (αβ)ⁿ. Trying to find the actual roots is unnecessary and is the time trap.

Faculty with at least one account = 150 - 30 = 120. By inclusion-exclusion, both = 55 + 85 - 120 = 20. Only Facebook = 55 - 20 = 35. Answer: (A) 35.

Concept: Two-set inclusion-exclusion. The traps are answering 55 (all Facebook users) or not removing the 30 with neither account first.

(i): the author only wonders whether the developments are good; no belief that computers are bad is stated, so (i) cannot be inferred. (ii): the passage says many believe the internet is an unintended consequence, which contradicts (ii). Neither follows. Answer: (D).

Concept: Inference versus over-reading. Raising a question is not asserting a conclusion, and a statement the passage contradicts cannot be inferred.

"All hill-stations have a lake" means at least one lake; it does not limit the number. So a hill-station may have two lakes and (ii) does not follow. Ooty having two lakes is consistent with being a hill-station, so (i) does not follow either. Answer: (D).

Concept: Reading "have a lake" as "exactly one lake" is the trap. Neither conclusion is forced by the premises.

A rectangle is fixed by choosing 2 of the 3 horizontal lines and 2 of the 5 vertical lines. Count = C(3,2) × C(5,2) = 3 × 10 = 30. Answer: (C) 30.

Concept: Rectangles in an m × n grid: C(m+1,2) × C(n+1,2). The trap is counting only the 8 cells or missing multi-cell rectangles.

The graph is an inverted V with its peak at x = 1, so f(x) = k - |x - 1| with k = f(1) = 2. Check: f(-3) = 2 - 4 = -2 and f(3) = 2 - 2 = 0, both match. Answer: (C) f(x) = 2 - |x - 1|.

Concept: Reading an absolute-value graph: the vertex gives the shift and height, and a downward V means a minus sign. Options with + |x - 1| open upward.

P ∧ (P ⇒ Q) ≡ P ∧ Q, so P and Q are both true whenever the premise holds. false - not implied; Q - implied; true - implied (everything implies true); P ∨ Q - implied; ¬Q ∨ P - implied since P is true. Count = 4. Answer: 4.

Concept: A implies B when B is true in every model of A. P ∧ (P ⇒ Q) is modus ponens, giving P ∧ Q. Forgetting that "true" is implied by everything is the usual slip.

f(x) + f(-x) keeps only the even-power terms of f (doubled), so the highest even power in f is x¹⁰. g(x) - g(-x) keeps only the odd-power terms of g = f′. Odd powers of f′ come from even powers of f: x¹⁰ gives 10x⁹, and a higher odd term in g would need a higher even term in f, which does not exist. Degree = 9. Answer: 9.

Concept: f(x)+f(-x) isolates even terms, g(x)-g(-x) isolates odd terms, and differentiation maps even powers to odd ones. The trap is assuming f itself has degree 10.

By the Four Colour Theorem every planar graph is 4-colourable, and K4 is planar and needs 4 colours, so 4 is sufficient for all planar graphs and cannot be lowered. Answer: 4.

Concept: Four Colour Theorem. Confusing it with the Five Colour Theorem, or with 3 colours that suffice only for special classes, is the usual mistake.

I is false: with m < n a system can still be inconsistent, e.g. x + y + z = 1 and x + y + z = 2. II is false: an overdetermined system can be consistent, e.g. x = 1, 2x = 2, 3x = 3. III is true: the homogeneous system with m = n always has the zero solution. Only III holds. Answer: (C).

Concept: Consistency depends on ranks, not on comparing m and n. Underdetermined does not mean solvable; overdetermined does not mean unsolvable.

Equal numbers of each type, so P(T1) = P(T2) = 0.5. By total probability, P(lasts > 100 h) = 0.5 × 0.7 + 0.5 × 0.4 = 0.35 + 0.20 = 0.55. Answer: 0.55.

Concept: Law of total probability over a partition. With an unequal mix a plain average would be wrong; here the mix is equal, so the weighted and plain averages coincide.

det A = product of eigenvalues = 1 × 2 × 4 = 8. Transposing does not change a determinant, and det(A⁻¹) = 1/det A. So det((A⁻¹)ᵀ) = 1/8 = 0.125. Answer: 0.125 (accepted range 0.124 to 0.126).

Concept: Determinant = product of eigenvalues; det(Aᵀ) = det A; det(A⁻¹) = 1/det A. The trap is answering 8 by forgetting the inverse.

A = 1 = 00000001. Latency is longest when a carry generated at bit 0 propagates through all eight stages, which needs every bit of B to be 1 so each stage passes the carry on: B = 11111111. In 2's complement that is -1, and 1 + (-1) ripples a carry from bit 0 to bit 7. Answer: -1.

Concept: Ripple-carry worst case is a full carry chain: generate at the LSB, propagate everywhere else. The trap is answering 255 or 127 without reading 11111111 as a 2's complement value.

x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0 means x₁ ⊕ x₃ = x₂ ⊕ x₄. Complementing both inputs of an XOR leaves it unchanged (x̄ ⊕ ȳ = x ⊕ y), so x̄₁ ⊕ x̄₃ = x₁ ⊕ x₃ = x₂ ⊕ x₄ = x̄₂ ⊕ x̄₄. All xᵢ = 1 satisfies the premise but breaks (A), (B) and (D). Answer: (C).

Concept: XOR as parity (an even number of 1s). Rearranging XOR terms plus the identity x̄ ⊕ ȳ = x ⊕ y settles it; all-ones is the quick counterexample for the rest.

In 16-bit 2's complement every bit pattern is a distinct integer: X = 2¹⁶. Sign-magnitude has two zeros (+0 and -0), so Y = 2¹⁶ - 1 distinct integers. X - Y = 1. Answer: 1.

Concept: Sign-magnitude (and 1's complement) spend one pattern on negative zero; 2's complement does not. Counting patterns instead of distinct values gives the wrong answer 0.

40 instructions need ceil(log₂ 40) = 6 opcode bits. 24 registers need ceil(log₂ 24) = 5 bits each, so two register fields take 10 bits. Immediate = 32 - 6 - 10 = 16 bits. Answer: 16.

Concept: Instruction-format sizing with the ceiling of log₂. The trap is using 4 bits for 24 registers or 5 bits for 40 opcodes.

BFS visits level by level. To make t as late as possible, levels 0 to 3 are full and t is the last vertex of a full level 4. Vertices before level 4: 1 + 2 + 4 + 8 = 15; level 4 holds at most 16. So t can be vertex 15 + 16 = 31. Answer: 31.

Concept: BFS order on a tree is level order. A complete binary tree maximises the position of a depth-4 vertex: 2⁵ - 1. Off-by-one errors on the number of levels are the usual trap.

j is passed by value, i by address. Inside f, m = 10 + 5 = 15 (a local copy) and *p = 5 + 15 = 20, so i becomes 20 while j stays 10. Printed value = 20 + 10 = 30. Answer: 30.

Concept: Call by value versus passing a pointer: changing m does not affect j, writing through p does change i. Adding 5 to j as well (35) is the trap.

Floyd-Warshall computes d_k(i,j), the shortest path using only intermediate vertices from {1..k}, from the k - 1 table: d_k(i,j) = min(d_(k-1)(i,j), d_(k-1)(i,k) + d_(k-1)(k,j)). Overlapping subproblems solved bottom-up in a table is dynamic programming. Answer: (C) Dynamic Programming paradigm.

Concept: Floyd-Warshall and Bellman-Ford are DP; Dijkstra and Prim are greedy. The recurrence over growing sets of allowed intermediate vertices is the giveaway.

Delete with a pointer in a doubly linked list is O(1), so Θ(N) deletes cost O(N). Insert into a sorted list needs a linear scan, O(N) each: O(N log N) total. Find is also O(N) each: O(N log N). Decrease-key must move the node backward to keep the order, O(N) each, and Θ(N) of them cost O(N²). Total O(N²). Answer: (C) O(N²).

Concept: Per-operation costs on a sorted doubly linked list: pointer deletes are O(1), searching and repositioning are linear. The Θ(N) decrease-keys dominate.

(0 + 1)*(0 + 1)(0 + 1)* is every string with at least one symbol, i.e. all non-empty strings over {0, 1}. The DFA needs a non-accepting start state (seen nothing) and one accepting state reached on any symbol, which loops on 0 and 1. The two states are distinguishable by the empty string. Answer: 2.

Concept: Simplify the regular expression before building the automaton: it is just Σ⁺. A DFA for Σ⁺ needs 2 states. Counting the three factors as three states is the trap.

L₁ = {aⁿbⁿ : n ≥ 0}, which needs unbounded counting and is not regular (pumping lemma). L₂ = (ab)*, a regular expression, so it is regular; the grammar is right-linear. So P is false and Q is true. Answer: (C).

Concept: Recognise the language behind the grammar. Self-embedding (aSb) gives aⁿbⁿ; a right-linear rule (abS) gives a regular language. Judging only by "it is a CFG" is the trap.

I: recursive languages are closed under complement, so L̄₃ is recursive, hence RE; RE is closed under union, so true. II: every CFL is recursive, so L̄₂ is recursive; recursive ∪ recursive is recursive, true. III: L₁* is regular, and regular ∩ CFL is context-free, true. IV: CFLs are not closed under complement, so L̄₂ need not be context-free and the union need not be either; false. Answer: (D) I, II and III only.

Concept: Closure properties across the Chomsky hierarchy. Key facts: recursive is closed under complement, CFL is not; CFL ∩ regular is CFL; every CFL is recursive.

Tokens are specified by regular expressions (P-iii). Top-down parsers build a leftmost derivation (Q-i). Type checking is part of semantic analysis (R-ii). Runtime environments manage activation records on the stack (S-iv). Answer: (B).

Concept: Compiler phases and their core tools. Top-down gives leftmost derivation; bottom-up gives a rightmost derivation in reverse.

LRU and OPT are stack algorithms: the pages held with k frames are always a subset of those held with k + 1 frames, so faults never increase with more frames. FIFO is not a stack algorithm and shows Belady's anomaly, e.g. reference string 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 faults with 3 frames and 10 with 4. Answer: (D) FIFO.

Concept: Belady's anomaly affects FIFO, not stack algorithms such as LRU and OPT.

B+ tree insertion and deletion split, merge or redistribute nodes and only grow or shrink the tree at the root, so every leaf is always at the same depth. That equal root-to-leaf path length is what "balanced" means here. Node occupancy is bounded (at least half full) but not within 1 of a sibling. Answer: (A).

Concept: B and B+ trees are perfectly height-balanced: all leaves at one level. The "differ by at most 1" option describes AVL trees, which is the trap.

A schedule is conflict serializable exactly when its precedence graph is acyclic. Each edge Ti → Tj means Ti must come before Tj in an equivalent serial schedule, so any topological order of the graph gives a valid serial order. DFS or BFS order, or index order, can violate an edge. Answer: (A) Topological order.

Concept: Conflict serializability test: acyclic precedence graph, serial order = topological sort. Assuming T1, T2, ... index order is the trap.

Anarkali signs with her own private key. Anyone can verify the signature with the matching public key, so Salim uses Anarkali's public key. Salim's keys play no role in a signature. Answer: (A).

Concept: Digital signatures: sign with the sender's private key, verify with the sender's public key. Encryption for confidentiality is the reverse (receiver's public key), which is the usual mix-up.

(A) is false: CSMA/CD keeps sensing while transmitting in order to detect collisions. (B) is false: the jam signal tells all stations a collision occurred; padding is a separate field. (C) is false: the station aborts transmission on detecting a collision. (D) is true: binary exponential backoff widens the random wait range after each collision, reducing the chance of colliding again. Answer: (D).

Concept: CSMA/CD mechanics: listen while talking, abort and jam on collision, then back off exponentially. Confusing the jam signal with padding is the trap.

After a restart the DNS cache is empty, so the host first sends a DNS query to resolve the server name. With the IP address it opens a TCP connection, starting with SYN. Only after the handshake can the HTTP GET be sent over that connection. Answer: (C) DNS query, TCP SYN, HTTP GET request.

Concept: Order of protocols when fetching a page: resolve the name, connect, then request. "Just been restarted" rules out a cached DNS answer.

Reflexive: (a, b)R(a, b) since a ≤ a. So P is true. Transitive: take (5, 5)R(1, 6) because 5 ≤ 6, and (1, 6)R(2, 1) because 1 ≤ 2. But (5, 5)R(2, 1) fails since 5 > 2 and 5 > 1. So Q is false. Answer: (B) P is true and Q is false.

Concept: An "or" condition breaks transitivity: the two steps can be justified by different coordinates. One concrete counterexample is enough; the trap is assuming it behaves like a product order (which uses "and").

(A): ∀x p(x) ⇒ ∀x q(x) ≡ ¬∀x p(x) ∨ ∀x q(x) ≡ ∃x ¬p(x) ∨ ∀x q(x), so it is a tautology. (B): ∃ distributes over ∨, valid. (C): a witness for p ∧ q is a witness for each, valid. (D): over the integers let p = "even", q = "odd". Every x is even or odd, but neither "all even" nor "all odd" holds, so (D) is not valid. Answer: (D).

Concept: ∀ distributes over ∧ and ∃ over ∨; the reverse directions (∀ over ∨, ∃ over ∧) hold only one way. A two-predicate counterexample such as even/odd settles it.

Model compounds as vertices and reactions as edges. The degree sum is even (handshaking lemma). The 9 compounds in S contribute 9 × 3 = 27, an odd number, so the degrees in U \ S must sum to an odd number, which forces at least one vertex in U \ S to have odd degree. That proves II. I and III are not forced: the 14 vertices in U \ S can have a mix of odd and even degrees. Answer: (B) Only II.

Concept: Handshaking lemma: the number of odd-degree vertices is even. Here S already has 9 odd vertices, so U \ S must hold an odd number of odd vertices, at least one.

13 ≡ -4 (mod 17). (-4)² = 16 ≡ -1, so (-4)⁴ ≡ 1. 99 = 4 × 24 + 3, so 13⁹⁹ ≡ (-4)³ = -64 ≡ -64 + 68 = 4 (mod 17). Answer: 4.

Concept: Modular exponentiation: find a small power that is ±1 (order of the element), then reduce the exponent. Fermat (exponent mod 16) also works: 99 mod 16 = 3.

Each F needs its G result first. Pair one U_G with one U_F as a two-stage pipeline and run two such pipelines, 5 items each. The F stage (5 ns) is the bottleneck, so the U_G work stays ahead. In one pipeline: first G finishes at 3 ns, then the 5 F computations run back to back, ending at 3 + 5 × 5 = 28 ns. Both pipelines run in parallel. Answer: 28.

Concept: Pipelining with a slow stage: total time = fill time of earlier stages + (number of items × bottleneck time). Simply adding 10 × 8 / 2 = 40 ignores the overlap.

Opcode for 12 instructions: 4 bits. Each register identifier for 64 registers: 6 bits, three of them: 18 bits. Immediate: 12 bits. Total 4 + 18 + 12 = 34 bits, which needs 5 bytes when byte-aligned. 100 instructions × 5 bytes = 500 bytes. Answer: 500.

Concept: Byte alignment rounds each instruction up to whole bytes: 34 bits becomes 40. Answering 425 (34 × 100 / 8) ignores the alignment.

Cache size 512 KB = 2¹⁹ bytes. With block size 2ᵇ, the number of sets is 2¹⁹ / (8 × 2ᵇ) = 2¹⁶⁻ᵇ, so index + offset = (16 - b) + b = 16 bits whatever the block size. Tag = 40 - 16 = 24 bits. Answer: 24.

Concept: Tag width depends only on address width, cache size and associativity: tag = address bits - log₂(cache size / ways). The block size cancels, which is why it was not given.

Let τ₁ = 6k. Then τ₂ = 8k and τ₃ = 3k. The clock is set by the longest stage τ₂ = 8k = 1/3 ns, so k = 1/24 ns. Splitting τ₂ gives two 4k stages; the longest stage is now τ₁ = 6k = 0.25 ns. New frequency = 1/0.25 ns = 4 GHz. Answer: 4 (accepted range 3.9 to 4.1).

Concept: Pipeline clock period equals the slowest stage. After splitting, the bottleneck moves to the next longest stage; assuming the frequency doubles to 6 GHz is the trap.

In a min-heap every ancestor of a node holds a smaller key. Only 1 to 8 are smaller than 9, so 9 can have at most 8 ancestors, i.e. depth at most 8. This is achievable: place 1, 2, ..., 8 along one root-to-node path at depths 0 to 7 and 9 below at depth 8. The heap of 1023 nodes has depths 0 to 9, so depth 8 exists. Answer: 8.

Concept: Heap order bounds depth by the number of smaller keys. Also check that the tree is deep enough (1023 nodes give depth 9). Answering 9 forgets that only eight keys are smaller.

Initially res = 1, a = X, b = Y, so res × aᵇ = Xʸ. Even b: a becomes a², b becomes b/2, and (a²)^(b/2) = aᵇ, so res × aᵇ is unchanged. Odd b: res becomes res × a and b becomes b - 1, and (res × a) × a^(b-1) = res × aᵇ, unchanged. So Xʸ = res × aᵇ holds before every iteration, and at b = 0 it gives res = Xʸ. (A) fails once res changes. Answer: (C).

Concept: Loop invariant for fast exponentiation: the quantity res × aᵇ stays equal to Xʸ. Check initialisation and preservation for both branches.

Evaluate the RPN to get the tree: ((3 * 4) - 5) ^ 2 is the left operand and (6 * 7) + 1 the right operand of the root "-". New-order is root, right, left. Root: -. Right subtree "+": +, then its right 1, then its left "*": * 7 6. Left subtree "^": ^, its right 2, its left "-": -, then 5, then "*": * 4 3. Sequence: - + 1 * 7 6 ^ 2 - 5 * 4 3. Answer: (C).

Concept: Build the expression tree from postfix with a stack, then apply the custom order. New-order is the reverse of postorder. Option (B) swaps the order inside the leaf pairs, the usual slip.

f returns the maximum of p[i] - p[i+1] over adjacent pairs, and 0 from the base case. Differences: 3 - 5 = -2, 5 - 2 = 3, 2 - 6 = -4, 6 - 4 = 2. Maximum of {0, -2, 3, -4, 2} = 3. Answer: 3.

Concept: Recognise what the recursion computes: the largest drop between adjacent elements, floored at 0. Reading p[0]-p[1] as p[1]-p[0] gives 4, the trap.

Dimensions p = 10, 5, 20, 10, 5. Pairs: A₁A₂ = 1000, A₂A₃ = 1000, A₃A₄ = 1000. Triples: A₁..A₃ = min(1000 + 10·20·10, 1000 + 10·5·10) = 1500; A₂..A₄ = min(1000 + 5·10·5, 1000 + 5·20·5) = 1250. Full: split after A₁: 1250 + 10·5·5 = 1500; after A₂: 1000 + 1000 + 10·20·5 = 3000; after A₃: 1500 + 10·10·5 = 2000. Minimum 1500, from A₁((A₂A₃)A₄). Answer: 1500.

Concept: Matrix chain multiplication DP: m[i][j] = min over k of m[i][k] + m[k+1][j] + pᵢ₋₁pₖpⱼ. Greedy left-to-right order is not optimal.

Count recursive calls on the longest path: 1 (before decision 1) + 2 (decision 1 right branch) + 1 (after decision 2) + 1 (decision 3 call) = 5 calls of A(n/2). Worst case T(n) = 5T(n/2) + O(1). By the master theorem T(n) = Θ(n^(log₂ 5)), and log₂ 5 ≈ 2.32. Answer: 2.32 (accepted range 2.2 to 2.4).

Concept: Worst-case path through branching code determines the recurrence. With a = 5, b = 2 and constant extra work, the master theorem gives n^(log₂ 5). Counting all calls in the chart (6) instead of one path is the trap.

7 nodes with height 6 means the tree is a single path. Each inserted key must be either the smallest or the largest of the keys still to be inserted, otherwise some later key would branch off. The last key is forced, and each of the first 6 insertions has 2 choices (current min or current max). Count = 2⁶ = 64. Answer: 64.

Concept: A degenerate (path) BST arises when each new key is an extreme of the remaining keys. Counting only fully sorted orders (2 ways) misses the zig-zag paths.

Memory is unlimited, so keep an n × n table of entry pointers (allocated without initialising, or with the standard O(1)-initialisation trick). Pass 1: for each vertex u and each entry [v] in its list, store a pointer to that entry at T[u][v]: O(n + m). Pass 2: for each entry [v] in u's list, set its twin to T[v][u]: O(n + m). Every list entry must be touched at least once, so Θ(n + m) is optimal. Answer: (B).

Concept: Unlimited memory permits direct addressing, turning lookups into O(1). Alternatively a radix-sort of the 2m (u, v) pairs also gives linear time. Initialising an n² table naively would cost Θ(n²), the trap behind (A).

I is false: an NFA may have missing transitions, so a string with no run simply dies. E.g. a one-state accepting NFA over {a, b} with a self-loop only on a accepts a*, not Σ*. II is true: take A = ∅; then A ∩ B = ∅ for every B, which is regular (any finite A also works). Answer: (B) Only II.

Concept: NFAs (and partial DFAs) reject by having no run, not only by ending in a non-accepting state. For II, the empty language is the standard witness.

L₁: a PDA pushes a symbol for each a and each b, then pops one for each c; acceptance when the stack empties exactly. Grammar: S → aSc | aBc, B → bBc | bc. So L₁ is context-free. L₂ needs the count of a to equal the count of b and also c to equal 2n, two dependent comparisons; pumping a string aᵖbᵖc²ᵖ cannot keep all three counts in ratio 1:1:2, so L₂ is not context-free. Answer: (B).

Concept: One stack can match one nested count (a and b against c) but not two independent equalities. aⁿbⁿc²ⁿ behaves like aⁿbⁿcⁿ, the classic non-CFL.

In 2016 steps M reads at most the first 2016 input symbols, so whether M runs at least 2016 steps on input w depends only on w's first 2016 symbols (inputs shorter than that are a finite set too). So simulate M for 2016 steps on every input of length at most 2016, a finite set: this decides both L₁ (some run lasts 2016 steps) and L₂ (all do). L₃ is a non-trivial semantic property of the language of M, undecidable by Rice's theorem. Answer: (C) L₁, L₂ recursive, L₃ not.

Concept: Step-bounded properties are decidable by bounded simulation, since only a finite prefix of input matters. Rice's theorem applies to properties of the language, not of running time; misapplying it to L₁ and L₂ is the trap.

(A): A → Aa is immediate left recursion. (C): S → Aa and A → Sc give S ⇒ Aa ⇒ Sca, indirect left recursion. (D): A → Bd and B → Ae give A ⇒ Bd ⇒ Aed, indirect left recursion. (B): S starts with A, B or c; A starts with B or ε; B starts with e. No nonterminal can derive a sentential form starting with itself. Answer: (B).

Concept: Check indirect left recursion by following leftmost symbols through other rules, including through nullable prefixes. Looking only for A → A... misses (C) and (D).

G1: L → id [E and E → num] | num] [E generate id [num] followed by zero or more [num] groups, e.g. int id [num] [num] ; for int a[10][3];. G2: E → E[num] | [num] generates one or more [num] groups (left-recursive), so int id [num][num] ; is also produced. Both generate exactly the declarations with at least one dimension. Answer: (A) Both G1 and G2.

Concept: Grammars can split brackets across productions in unusual ways; derive a sample string to check. Left recursion (G2) does not make a grammar wrong, only unsuitable for top-down parsing.

0-3: P1 runs (remaining 7). At 3, P2 (6) < 7, so P2 runs 3-7 (remaining 2). At 7, P3 (1) < 2, P3 runs 7-8 and finishes. At 8, remaining: P1 7, P2 2, P4 3; P2 runs 8-10 and finishes. P4 runs 10-13. P1 runs 13-20. Turnaround: P1 20 - 0 = 20, P2 10 - 3 = 7, P3 8 - 7 = 1, P4 13 - 8 = 5. Average = 33/4 = 8.25. Answer: 8.25 (accepted range 8.2 to 8.3).

Concept: SRTF re-evaluates at every arrival using remaining time, not original burst. Turnaround = completion - arrival. Using burst instead of remaining time at t = 7 is the trap.

Mutual exclusion holds: turn is either 0 or 1, letting only one process in. But the processes must strictly alternate. If turn = 0 and P0 does not want to enter, P1 is blocked even though the critical section is free; the decision depends on a process outside its critical section. That violates progress. Bounded waiting holds, since each waits at most one turn of the other. Answer: (C).

Concept: Strict alternation guarantees mutual exclusion and bounded waiting but fails progress. Peterson's algorithm adds flags to fix this.

With initial value S₀, the 12 V operations make S₀ + 12 units available in total for the 20 P operations (in the most favourable order). All P operations can complete when S₀ + 12 ≥ 20, i.e. S₀ ≥ 8. At least one P must remain blocked when S₀ + 12 < 20, i.e. S₀ ≤ 7. Largest such value: 7. Answer: 7.

Concept: Count total resource supply against demand: initial value plus V operations versus P operations. Answering 8 confuses the threshold at which all P operations succeed.

Average latency = (1 - m) × 1 + m × 10 = 1 + 9m. Need 1 + 9m < 6, so m < 5/9 ≈ 55.6%. At 20 MB m = 60% gives 6.4 ms (too slow); at 30 MB m = 40% gives 4.6 ms. Even the alternative model (miss costs 1 + 10 ms, latency 1 + 10m) needs m < 50%, again first met at 30 MB. Answer: 30.

Concept: Effective access time with hits and misses, read off a miss-rate curve. Both common latency models give the same cache size here.

Neither transaction reads a value written by the other: r₂(X), r₁(X), r₂(Y), r₁(Y) all read original values, since the only writes are w₁(X) and w₂(X) and no read follows them. With no dirty reads, aborting T₁ forces no other abort, so there is no cascading abort (and the schedule is trivially recoverable, ruling out A and B). It is not strict: w₂(X) overwrites X written by T₁ before T₁ commits or aborts. Answer: (C).

Concept: Recoverable, cascadeless and strict differ by what may follow an uncommitted write: a read (cascadeless forbids) or any read or write (strict forbids). A blind overwrite breaks strictness but not cascadelessness.

total: Ajmer 20, Bikaner 40, Churu 30, Dungargarh 10. total_avg = (20 + 40 + 30 + 10)/4 = 25. Districts with total ≥ 25: Bikaner and Churu. Answer: 2.

Concept: Group-wise aggregate, then an average of those aggregates. Averaging the raw capacities (100/7 ≈ 14.3) instead of the district totals gives 3, the trap.

For collision detection the transmission time must be at least the round-trip propagation time: L/B ≥ 2 × Tp. L = 2 × 40 × 10⁻⁶ × 20 × 10⁶ = 1600 bits = 200 bytes. Answer: 200.

Concept: CSMA/CD minimum frame: L = 2 × Tp × B. Using one-way propagation gives 100 bytes, the trap.

I is true: in the 2.4 GHz band channels 1, 6 and 11 do not overlap. II is false: RTS-CTS is used for collision avoidance (reserving the medium, solving hidden terminals), since wireless stations cannot detect collisions while transmitting. III is true: 802.11 acknowledges every unicast data frame because collisions are not detected. Answer: (B) I and III only.

Concept: 802.11 uses CSMA/CA, not CSMA/CD. RTS-CTS avoids collisions; ACKs replace detection. Calling RTS-CTS collision detection is the trap.

Frame transmission time Tt = 8192 bits / 128000 bps = 64 ms. For 100% utilization the sender window must cover Tt + 2Tp = 64 + 300 = 364 ms, i.e. 364/64 = 5.69, so 6 frames. Selective repeat needs a sequence space of at least twice the window: 12, so ceil(log₂ 12) = 4 bits. (Taking 1 KB = 1000 bytes gives 362.5/62.5 = 5.8, again 6 frames and 4 bits.) Answer: 4.

Concept: Window size = 1 + 2a with a = Tp/Tt, rounded up; for selective repeat the sequence number space must be at least 2 × window. Forgetting the doubling gives 3 bits.