GATE 2014 CS (Computer Science) Set 3 question paper with solutions

The sentence narrates completed past events: he fell down and then lost consciousness. "Fell down" is simple past, so the parallel verb joined by "and" should also be simple past: "lost consciousness". The past continuous "was losing consciousness" breaks the sequence. Parts I, II and III are correct. Answer: (D) IV.

Concept: Tense consistency between verbs joined by 'and' in a narrative of completed events. The trap is 'from under the table', which looks odd but is a correct double preposition.

The main clause ends with "done", a past participle, so it needs "could/would have done": an unreal past (third) conditional. The third conditional takes the past perfect in the if-clause: "If she had known ..., she could have done the experiment." Answer: (C) had known, could have.

Concept: Third conditional: if + past perfect, could/would have + past participle. The trap is option D, which puts a modal ('should have known') inside the if-clause.

The terms are n² + 1 for n = 1, 2, 3, ...: 2, 5, 10, 17, 26, 37, 50, 65. Equivalently the differences are 3, 5, 7, 9, 11, 13, 15. The last term should be 50 + 15 = 65, not 64. Answer: (C) 64.

Concept: Recognising n² + 1 (or successive odd differences). The trap is noticing that 64 is a perfect square and assuming it fits.

Number of students = 21 + 17 + 6 = 44 (each row sums to 44). Total marks scored = 21 × 2 + 15 × 3 + 23 × 2 = 42 + 45 + 46 = 133. Average per student = 133 / 44 ≈ 3.02. Answer: (C) 3.02.

Concept: The class size is the row total, and the average is per student over the whole exam. The trap is averaging per question (133/132 or 133/3) or dividing by the number who answered correctly.

D: x ∈ f⁻¹(S ∩ T) ⇔ f(x) ∈ S and f(x) ∈ T ⇔ x ∈ f⁻¹(S) and x ∈ f⁻¹(T). So preimage always preserves intersection - true. Counter-example for the rest: X = {1, 2}, Y = {y}, f(1) = f(2) = y, A = {1}, B = {2}. Then A ∩ B = ∅, so f(A ∩ B) = ∅ but f(A) ∩ f(B) = {y} (B and C fail), and |f(A ∪ B)| = 1 ≠ 1 + 1 (A fails). Answer: (D).

Concept: Preimages commute with unions and intersections; images commute only with unions, and only when the function is injective for intersections. The trap is B, which holds only for one-to-one functions.

dim(V₁ + V₂) = dim V₁ + dim V₂ - dim(V₁ ∩ V₂). Since V₁ + V₂ ⊆ V, dim(V₁ + V₂) ≤ 6, so 4 + 4 - dim(V₁ ∩ V₂) ≤ 6, giving dim(V₁ ∩ V₂) ≥ 2. The value 2 is attained, e.g. V₁ = span(e₁..e₄), V₂ = span(e₃..e₆). Answer: 2.

Concept: Dimension formula for the sum of subspaces. The trap is answering 0, forgetting that two large subspaces of a small space must overlap.

On [0, 2π], x ≥ 0, so |x sin x| = x|sin x|. sin x ≥ 0 on [0, π] and ≤ 0 on [π, 2π]. An antiderivative of x sin x is sin x - x cos x. ∫ from 0 to π of x sin x dx = [sin x - x cos x] from 0 to π = π. ∫ from π to 2π of -x sin x dx = -[sin x - x cos x] from π to 2π = -(-2π - π) = 3π. Total = 4π, so k = 4. Answer: 4.

Concept: Split an absolute-value integrand at the sign changes, then integrate by parts. The trap is integrating x sin x over [0, 2π] directly, which gives -2π.

Required 1s: 0, 5, 10, 15; don't cares: 2, 7, 8, 13. Q̄S̄ (Q = 0, S = 0) is minterms 0, 2, 8, 10 - covers 0 and 10 using don't cares 2 and 8. QS (Q = 1, S = 1) is minterms 5, 7, 13, 15 - covers 5 and 15 using don't cares 7 and 13. Two quads cover everything. Answer: (B) Q̄S̄ + QS.

Concept: Using don't cares to enlarge groups in a K-map (the corner quad here). The trap is option C or D, which ignore the don't cares and leave four-literal or three-literal terms.

The clock period of a pipeline is the slowest stage latency. P1: 2 ns (500 MHz). P2: 1.5 ns (667 MHz). P3: 1 ns (1 GHz). P4: 1.1 ns (909 MHz). P3 has the shortest period and hence the highest frequency. Answer: (C) P3.

Concept: Pipeline clock is set by the bottleneck stage. The trap is summing stage latencies or picking P4 for having many short stages.

The body swaps A[i][j] and A[j][i] (Temp holds A[i][j] + 100, and Temp - 100 restores the original value, so C has no net effect). Both loops run over all (i, j), so each off-diagonal pair is visited twice: once as (i, j) and once as (j, i). The second swap undoes the first. Diagonal elements are swapped with themselves. The matrix is unchanged, and the output is A itself. Answer: (A).

Concept: Transposing in place must iterate only over j > i (or j < i). The trap is answering 'transpose' without noticing the full double loop swaps every pair twice.

Rewrite in nested (Horner-like) form: P(X) = ((X² + 4)·X² + 6)·X + 5. With one temporary t: t = X * X (1) t = t + 4 (2) t = t * X (3) t = t * X (4) now t = X⁴ + 4X² t = t + 6 (5) t = t * X (6) t = t + 5 (7) Seven operations. Fewer is not possible with one temporary, since X² cannot be kept while t is reused. Answer: 7.

Concept: Horner-style factoring to minimise operations. The trap is computing X² once and reusing it, which needs a second temporary (giving 6 with two variables).

For a general (ordered) tree, in-order visits the first subtree, then the node, then the remaining subtrees left to right. At P: in-order(Q), P, in-order(R). in-order(Q) = in-order(S), Q = S Q. in-order(R) = in-order(T), R, in-order(U), in-order(V) = T R W U V (U's first subtree is W, then U). Result: S Q P T R W U V. Answer: (A) SQPTRWUV.

Concept: In-order on a non-binary tree: first child subtree, root, then the other children. The trap is visiting R only after all its children, as in post-order.

Recursion depth = number of vertices on the DFS stack = length of a simple path DFS can follow, and DFS can be steered along any simple path. So find the longest simple path. Colour each 3 × 3 grid like a chessboard: corners and centre (5) versus edge-middles (4). A path through all 9 vertices must start and end on corners/centre. Path: snake through all 9 of the left grid ending at corner L(3,3) (9), go to X (10), enter R(3,1), a corner, and snake through all 9 of the right grid ending at a corner (19). To also reach Z the path would have to end the right grid at R(2,3), an edge-middle, which forces skipping a grid vertex, so still 19. Y is a dead end beside X. Answer: 19.

Concept: DFS recursion depth equals the longest simple path DFS can be steered along. The trap is counting all 21 vertices, ignoring the pendant vertices and the grid parity constraint.

Any fixed pivot rule (first, last or middle element) has an adversarial input where the chosen pivot is always the smallest or largest remaining element. Each partition then removes only one element, giving n + (n - 1) + ... = Θ(n²) comparisons. Choosing the middle position is not the same as choosing the median value. Answer: (A) O(n²).

Concept: Worst-case quicksort with a deterministic pivot position is quadratic. The trap is confusing 'central element' with the median, which would give O(n log n).

Length 0: ε is in. Length 1: a, b are in. Length 2: aa (a*), ab (a*b*), ba ((ba)*), bb (b*) are all in. Length 3: try bab. After any a* (none here) and b* = b, the remainder ab must match (ba)*a*, which it cannot (it would need to start with b or be all a's). With b* = ε, (ba) consumes ba and the leftover b cannot match a*. So bab is not in the language. Shortest missing string has length 3. Answer: 3.

Concept: Systematic enumeration of short strings against a regular expression. The trap is stopping at length 2 and concluding every short string is covered.

Intermediate code separates the front end (language-specific) from the back end (machine-specific). Optimisations written on the intermediate representation are independent of both the source language and the target machine, so the same optimiser can be reused across compilers. Parsing and error reporting happen before IR generation, and register allocation is a back-end concern. Answer: (C).

Concept: Purpose of an IR: retargetability and reuse of machine-independent optimisation. The trap is option D; register allocation is done on target code, not because of the IR.

Recursion needs a fresh activation record for each active call. With purely static allocation there is one record per procedure, so recursion is impossible (1 true) and dynamic allocation of activation records is required (3 true). A stack alone suffices; no heap or garbage collector is needed (2 and 4 false). Answer: (D) 1 and 3 only.

Concept: Run-time storage organisation for recursion. The trap is statement 4: a heap is needed for dynamic data, not for recursion.

By definition an attribute is prime if it is a member of at least one candidate key of R; otherwise it is non-prime. This is the notion 3NF uses. Answer: (B) in some candidate key of R.

Concept: Definition of prime attribute, used in 2NF and 3NF tests. The trap is option A (all candidate keys) or D (primary key only); any candidate key suffices.

Routing is a network layer function, end-to-end process communication is the transport layer's job, and channel sharing (multiple access) is the MAC sub-layer's job. Bit synchronization - agreeing on bit timing on the medium - belongs to the physical layer; the data link layer handles framing and frame-level error control. Answer: (B).

Concept: Mapping functions to OSI layers. The trap is confusing bit synchronization (physical layer) with frame synchronization (data link layer).

Every router decrements TTL, so TTL changes. Because the header changed, each router recomputes the header checksum, so the checksum changes. If a link on the path has a smaller MTU, a router fragments D, and the fragments that reach B carry non-zero fragment offsets. All three may differ. Answer: (D) (i), (ii) and (iii).

Concept: Which IPv4 header fields routers rewrite. The trap is forgetting fragmentation along the path, which changes the fragment offset (the question says 'may').

Use the 32-bit IPv4 address to make IDs unique across hosts. To distinguish up to 1000 IDs within one second needs ⌈log₂ 1000⌉ = 10 bits. That leaves 50 - 32 - 10 = 8 bits for the clock (seconds counter). An 8-bit counter covers 2⁸ = 256 distinct seconds before repeating, so the IDs wrap around after 256 seconds. Answer: 256.

Concept: Bit budgeting for a unique ID: host part + per-second sequence + time part. The trap is using all 18 non-address bits for time and forgetting the per-second counter.

The join pairs each employee with his/her own dependents (empId = eId) whose age is at least the employee's age. Its projection is the set of employees having at least one own dependent at least as old as themselves. Subtracting this from all employees leaves those for whom no own dependent has depAge ≥ empAge, i.e. the employee is older than every one of his/her dependents. Answer: (D) all of his/her dependents.

Concept: Set difference turns 'exists a counterexample' into 'for all'. The trap is option B: the join condition empId = eId restricts the comparison to the employee's own dependents, not all dependents.

Worst case: each program holds one fewer unit than it needs, i.e. 2 units each, and waits for one more. With 3 × 2 = 6 units that state is a deadlock. With one more unit (7), at least one program can get its third unit, finish and release its units, so the others can proceed. Minimum = 3 × (3 - 1) + 1 = 7. Answer: 7.

Concept: Deadlock-free resource count: Σ(maxᵢ - 1) + 1. The trap is answering 9 (enough for all at once) or 6.

Timeline: 0-2 P1 (remaining 10). At 2, P2 (4) preempts. 2-6 P2 completes. At 6, P3 (6) is shortest. At 8, P4 arrives with 5 but P3 has 4 left, so P3 continues: 6-12 P3 completes. 12-17 P4. 17-27 P1. Waiting = completion - arrival - burst: P1 27 - 0 - 12 = 15, P2 6 - 2 - 4 = 0, P3 12 - 3 - 6 = 3, P4 17 - 8 - 5 = 4. Average = 22 / 4 = 5.5. Answer: 5.5.

Concept: SRTF compares the newcomer's burst with the running process's remaining time. The trap is preempting P3 at time 8 by comparing P4's 5 with P3's original 6.

TLB hit: TLB search + one memory access = 10 + 80 = 90. TLB miss: TLB search + page table access + memory access = 10 + 80 + 80 = 170. EMAT = 0.6 × 90 + 0.4 × 170 = 54 + 68 = 122. Answer: 122.

Concept: Effective access time with a TLB and a single-level page table. The trap is omitting the TLB search time on a miss, which gives 118.

L₁: a DPDA pushes on 0s and pops on 1s, accepting on empty count - deterministic. L₂: push symbols of w until the marker c, then pop and match; the marker tells the machine exactly where the middle is - deterministic. L₃: even-length palindromes have no middle marker, so the PDA must guess the midpoint; this language is context-free but not deterministic CF. Answer: (C) Only L₁ and L₂.

Concept: Deterministic vs non-deterministic CFLs: a centre marker makes palindromes deterministic. The trap is treating wwʳ like wcwʳ.

From position 9 there are exactly two possible moves: a unit step to 10, or the shortcut to 15 (9 is involved in only this one shortcut). Each costs one step, so T(9) = 1 + min(T(10), T(15)). Hence {y, z} = {10, 15} and yz = 150. Answer: 150.

Concept: Writing the DP recurrence from the available transitions. The trap is overthinking other shortcuts; 'at most one shortcut involving any number' rules them out at 9.

Search down the tree for L: O(log n) since the tree is balanced. Then do an in-order walk from there, adding each key until a key exceeds H. The walk visits the m keys in range plus O(log n) boundary nodes, so the total is O(log n + m). Match O(nᵃ logᵇ n + mᶜ logᵈ n): a = 0, b = 1, c = 1, d = 0. a + 10b + 100c + 1000d = 0 + 10 + 100 + 0 = 110. Answer: 110.

Concept: Range queries on a balanced BST cost O(log n + m). The trap is O(m log n), from searching for each in-range key separately.

With simple uniform hashing each key independently lands in any of the 100 slots with equal probability, and chaining lets several keys share a slot. For the first 3 slots to stay empty each insertion must land in one of the other 97 slots: probability 97/100 each, independently. Total = (97 × 97 × 97)/100³. Answer: (A).

Concept: Independence of insertions under uniform hashing with chaining. The trap is option C, which assumes later keys cannot reuse an occupied slot (as with open addressing).

Each iteration takes the midpoint k. If x < listA[k] only j = k - 1 runs; if x > listA[k] only i = k + 1 runs; the range shrinks every time, so the loop terminates (A false). If x == listA[k], both conditions hold: j = k - 1 and i = k + 1, so i > j and the loop exits with k pointing at x, and the function returns k. So it finds x when present (D false) and returns -1 otherwise. This is binary search; it searches for x, not the maximum (C false). Answer: (B).

Concept: Tracing a binary search with two non-exclusive ifs. The trap is thinking the equality case causes an extra step that loses k; both updates fire together and end the loop at the right index.

Old design: clock = slowest stage = 2.2 ns. A branch resolves at the end of EX (stage 3), so the next fetch waits 2 extra cycles. CPI = 0.8 × 1 + 0.2 × 3 = 1.4. Time per instruction = 1.4 × 2.2 = 3.08 ns. New design: stages IF 1, ID 0.733, RF1 0.733, RF2 0.733, EX1 1, EX2 1, MEM 1, WB 0.75; clock = 1 ns. A branch resolves at the end of EX2 (stage 6), a 5-cycle stall. CPI = 0.8 × 1 + 0.2 × 6 = 2.0. Time per instruction = 2.0 ns. P/Q = 3.08 / 2.0 = 1.54. Answer: 1.54 (official range 1.50 to 1.60).

Concept: Deeper pipelines raise frequency but enlarge the branch penalty. The trap is counting the penalty as the branch's stage number instead of stage number minus one.

Instruction fetches are reads: 100 + 60 = 160 reads, 40 writes, 200 accesses in all. Average read time = 0.9 × 1 + 0.1 × 5 = 1.4 ns. Average write time = 0.9 × 2 + 0.1 × 10 = 2.8 ns. Total = 160 × 1.4 + 40 × 2.8 = 224 + 112 = 336 ns. Average = 336 / 200 = 1.68 ns. Answer: 1.68.

Concept: Weighted average memory access time over reads and writes. The trap is forgetting that instruction fetches are read operations, or averaging the read and write times without weighting.

JK rules: J=1,K=0 sets; J=0,K=1 resets; J=K=1 toggles; J=K=0 holds. From 000: J₂=Q̄₁=1, K₂=Q₀=0 -> Q₂=1. J₁=Q₂=0, K₁=1 -> Q₁=0. J₀=Q₁=0, K₀=Q̄₀=1 -> Q₀=0. State 100. From 100: J₂=1, K₂=0 -> 1. J₁=1, K₁=0 -> 1. J₀=0, K₀=1 -> 0. State 110. From 110: J₂=0, K₂=0 -> hold 1. J₁=1, K₁=0 -> 1. J₀=1, K₀=1 -> toggle to 1. State 111. Answer: (C) 100, 110, 111.

Concept: Next-state analysis of JK flip-flops using the present state for every input simultaneously. The trap is updating one flip-flop and then using its new value for the next one within the same clock.

Mutually exclusive and exhaustive: P(A) + P(B) = P(S) = 1. Let P(A) = p, so P(B) = 1 - p and the product is p(1 - p). This is maximised at p = 1/2 (derivative 1 - 2p = 0), giving 1/4. Answer: 0.25.

Concept: Complementary events and maximising p(1 - p). The trap is treating A and B as independent, which contradicts their being mutually exclusive with positive probabilities.

"All rainy days are cold" is ∀d (Rainy(d) → Cold(d)). Negating it: ¬∀d (Rainy(d) → Cold(d)) ≡ ∃d ¬(Rainy(d) → Cold(d)) ≡ ∃d (Rainy(d) ∧ ¬Cold(d)): there is a rainy day that is not cold. Answer: (D).

Concept: Negation of a universally quantified implication. The trap is option A, which says every day is rainy and not cold.

For each employee E, the subquery lists E's customers whose rating is not 'GOOD'. NOT EXISTS keeps E only when that list is empty, i.e. E has no customer with a non-GOOD rating. Since every employee has at least one customer, this means all of E's customers are rated 'GOOD'. Answer: (D).

Concept: NOT EXISTS over a negated condition expresses universal quantification. The trap is option C, which ignores the <> in the subquery.