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

To "cope with" conditions is to manage or adjust to them. "Adapt to" means to adjust oneself to new conditions, which is the same sense. "Adopt" means to take up or accept something as one's own, "adept in" means skilled at, and "accept with" is not idiomatic here. Answer: (B) adapt to.

Concept: Vocabulary in context. The trap is the near-homophones adopt / adapt / adept: only "adapt to" carries the sense of adjusting to circumstances.

Let the roots of ax² + bx + c = 0 be p and q, both positive. For x ≥ 0, |x| = x and the equation is ax² + bx + c = 0, whose roots p and q are both positive, so both are valid: 2 roots. For x < 0, |x| = -x and the equation becomes ax² - bx + c = 0, whose roots are -p and -q (replace x by -x). Both are negative, so both are valid: 2 more roots. Total 4 real roots: p, q, -p, -q. Answer: (D) 4 real roots.

Concept: ax² + b|x| + c is an even function of x, so every positive root has a mirror negative root. The trap is solving only the x ≥ 0 case and answering 2.

"Not all that glitters is gold" is ¬∀x (glitters(x) → gold(x)). Push the negation in: ∃x ¬(glitters(x) → gold(x)) = ∃x (glitters(x) ∧ ¬gold(x)). So some thing glitters and is not gold. Option A says nothing that glitters is gold (too strong), B and C talk about gold things. Answer: (D) ∃x: glitters(x) ∧ ¬gold(x).

Concept: Negating a universal conditional gives an existential conjunction: ¬∀x(P→Q) ≡ ∃x(P ∧ ¬Q). The trap is option A, which reads "no glittering thing is gold", a much stronger claim.

Let the break point X be uniform on [0, 1]. The shorter piece has length min(X, 1 - X). For X in [0, 0.5] the shorter piece is X; for X in [0.5, 1] it is 1 - X. By symmetry, E = 2 ∫ from 0 to 0.5 of x dx = 2 × (0.5²/2) = 0.25. Answer: 0.25 (official range 0.24 to 0.27).

Concept: Expectation of a function of a uniform random variable. The trap is answering 0.5 (the expected break point) instead of the expected minimum of the two pieces.

At θ = π/6 the first row equals the second row, so f(π/6) = 0. At θ = π/3 the first row equals the third, so f(π/3) = 0. f is continuous on [π/6, π/3] and differentiable inside (tan is smooth there). By Rolle's theorem some θ in (π/6, π/3) has f′(θ) = 0, so I is true. Expanding along row 1: f(θ) = A sin θ - B cos θ + C tan θ with constant A = cos(π/6)tan(π/3) - tan(π/6)cos(π/3) = 3/2 - 1/(2√3) ≠ 0, so f is not identically zero; a non-constant differentiable function with equal end values must have f′ ≠ 0 somewhere, so II is true. Answer: (C) Both I and II.

Concept: Rolle's theorem applied to a determinant whose value vanishes at the endpoints because two rows coincide. The trap is assuming f is constant (zero) on the interval, which would make II false.

Factor out Q: F = Q(P + P̄R + P̄R̄S). P + P̄R = P + R, so F = Q(P + R + P̄R̄S). P + R + P̄R̄S: the term P̄R̄S is covered except when P = 0 and R = 0, where it reduces to S, so P + R + P̄R̄S = P + R + S. F = Q(P + R + S) = PQ + QR + QS. Check with minterms: F = {5, 6, 7, 12, 13, 14, 15}; QR covers 6, 7, 14, 15, QS covers 5, 7, 13, 15, PQ covers 12-15. Answer: (A) PQ + QR + QS.

Concept: Absorption: X + X̄Y = X + Y, applied twice after factoring the common literal Q. The trap is reading the third term as P̄Q̄R̄S; the Q in that term is not complemented.

DFS visits each vertex once. When a vertex is visited, finding its neighbours in an adjacency matrix means scanning its entire row of n entries, regardless of how many edges it actually has. n vertices × n entries = Θ(n²). Answer: (C) Θ(n²).

Concept: The cost of DFS/BFS depends on the representation: Θ(n + m) with adjacency lists, Θ(n²) with an adjacency matrix. The trap is quoting Θ(n + m) out of habit.

Do one post-order traversal. For each node compute size(node) = 1 + size(left) + size(right), using the sizes already returned by the children, and increment a counter whenever size(node) = 4. Each node is processed once with O(1) work, so the time is O(n) = O(n¹ log⁰ n). So a = 1, b = 0 and a + 10b = 1. Answer: 1.

Concept: Subtree sizes are computable bottom-up in a single post-order pass. The trap is recomputing each subtree's size from scratch, which suggests O(n²) or O(n log n).

The graph has no cycle, so a topological order exists. P and S have no incoming edges. R has incoming edges from P and S only. Q has incoming edges from P, R and S. So P and S must come first (in either order), then R, then Q. The valid orders are PSRQ and SPRQ. PQRS fails (Q before R), SRQP fails (P last), and PSRQ is not unique. Answer: (C).

Concept: A topological order places every vertex after all its predecessors; when two sources are independent, both orders are valid. The trap is assuming the order is unique.

Track the set of active states of the NFA. Start: {q0}. Read 0: q0 -> q0. {q0}. Read 0: {q0}. Read 1: q0 -> q0, q1. {q0, q1}. Read 1: q0 -> q0, q1; q1 -> q2. {q0, q1, q2}. Answer: (A) {q0, q1, q2}.

Concept: Simulating an NFA by tracking the set of current states. The trap is following one path only, or forgetting that q0 keeps looping and stays in the set.

A is the definition of a basic block - true. B: an expression available at a point need not be recomputed, which is exactly common subexpression elimination - true. C: an assignment to a variable that is not live afterwards is dead and can be removed - true. D: replacing 4 ∗ 5 by 20 at compile time is constant folding, not common subexpression elimination - false. Answer: (D).

Concept: Matching each data-flow analysis to the optimisation it enables. The trap is confusing constant folding (evaluate constant expressions at compile time) with CSE (reuse an already computed value).

SSTF always picks the pending request nearest the current head position. At 100: request 100 is at distance 0 - serve it (1). At 100: 105 (5) vs 90 (10) - serve 105 (2). At 105: 110 (5) vs 90 (15) - serve 110 (3). At 110: 90 (20) vs 135 (25) - serve 90. So 90 is serviced after 3 requests. Answer: 3.

Concept: Greedy nearest-request scheduling. The trap is skipping the request at cylinder 100 itself, which is at distance 0 and is served first, giving 2 instead of 3.

E, F and H never appear on the right side of any FD, so every key must contain all three. {E, F, H}⁺: EF → G; F → I, J; EH → K, L; K → M; L → N. Closure = {E, F, G, H, I, J, K, L, M, N} = R. So {E, F, H} is a key, and it is minimal since none of E, F, H can be derived. {E, F} misses H; {E, F, H, K, L} is a superkey but not minimal. Answer: (B) {E, F, H}.

Concept: Attributes absent from every right-hand side must be in every candidate key; then check the closure. The trap is choosing the non-minimal superkey in option C.

S2: a foreign key must reference the whole primary (or a unique) key of the referenced table. R's primary key is (a, b), but S declares FOREIGN KEY (a) references R, a single column, so the definition is invalid. S2 is FALSE. S1: a foreign key also carries referential actions (ON DELETE / ON UPDATE CASCADE, SET NULL) and is enforced when the referenced table changes; a CHECK constraint on the referencing table cannot express that (standard CHECK cannot even refer to other tables in most systems). So it cannot always be replaced. S1 is FALSE. Answer: (D) Both S1 and S2 are FALSE.

Concept: Foreign keys must match the full referenced key, and they are more than a static check. The trap is accepting S2 because column a exists in R - a partial key is not a valid reference target.

S1: each link state router floods LSAs and runs Dijkstra over the whole 500-node, 4000-link topology, far more computation than a distance vector router's Bellman-Ford update from neighbours. True. S2: split horizon only prevents two-node loops; distance vector can still suffer count-to-infinity loops with three or more nodes. Link state, with a full topology at every node, does not form persistent loops. The statement has it backwards. False. S3: link state floods the change immediately and every router recomputes, so it converges faster than distance vector's iterative exchange. True. Answer: (D) S1 and S3 are true, but S2 is false.

Concept: Trade-offs between LS and DV routing: LS costs more computation but converges fast and is loop-resistant. The trap is believing split horizon fully cures distance vector's loop problem.

A message digest is produced by a cryptographic hash function. SHA-1 and MD5 are hash functions. RSA is a public-key encryption / signature algorithm and DES is a symmetric block cipher; neither produces a digest. Answer: (C) Q and S only.

Concept: Distinguishing hash functions (digests) from encryption algorithms. The trap is picking RSA because it is used in digital signatures - the signature signs a digest computed by a hash such as SHA-1 or MD5.