GATE DA 2024

In a topological order every edge points forward, so each vertex comes after all of its predecessors. The edges are \(P \to Q\), \(R \to Q\), \(Q \to S\), \(Q \to V\), \(S \to U\) and \(V \to T\): P and R must precede Q, Q must precede S and V, S must precede U, and V must precede T.

• A and C fail: both place Q before R, which breaks the edge \(R \to Q\).
• B holds: after P, R, Q come V, S, U, T, so U follows S and T follows V.
• D holds: P, R, Q, S, V, T, U also respects every edge.

More than one order is valid because the chains \(S \to U\) and \(V \to T\) do not depend on each other.

Answer: B, D

Height here is the number of edges on the longest root-to-leaf path, so a single node has height 0; the bounds in the options use this convention.

• A holds: if \(n_{2}\) nodes have two children, the tree has exactly \(L = n_{2} + 1\) leaves, and those \(n_{2}\) nodes are internal, so \(L \le I + 1\).
• B holds: the longest path alone has \(H + 1\) nodes, and levels 0 to \(H\) hold at most \(1 + 2 + \dots + 2^{H} = 2^{H+1} - 1\) nodes.
• C holds: the first \(H\) nodes on the longest path are internal, and internal nodes can sit only on levels 0 to \(H - 1\), which hold at most \(2^{H} - 1\) nodes.
• D fails: a path of height 2 has a single leaf, so \(H \le L\) breaks, and a perfect tree has \(2^{H}\) leaves, more than \(2^{H-1}\).

Answer: A, B, C

A dataset is linearly separable when a single straight line puts every circle on one side and every square on the other.

• A holds: in (i) the circles have \(y \ge 2\) and the squares lie around \(y = 1\) or lower, so the line \(y = 1.6\) splits them.
• B fails: in (ii) the circle at (2, 2) is the midpoint of the squares at (1, 2) and (3, 2). A half-plane holding both squares also holds their midpoint, so the circle cannot be cut off.
• C fails: (iii) is the XOR pattern. The circles (1, 1), (3, 3) and the squares (1, 3), (3, 1) have the same midpoint (2, 2), which would have to lie on both sides.
• D holds: in (iv) the squares sit to the upper left and the circles to the lower right, so a slanted line such as \(y = x - 0.3\) works.

Answer: A, D

The assertion says two things about every ball: a ball not used in rugby is round, and a ball used in rugby is not round.

• s1 states the first part, and s2 is its contrapositive (a ball that is not round is used in rugby), so s1 and s2 say the same thing.
• s3 states the second part, and s4 is its contrapositive, so s3 and s4 say the same thing.

A correct representation needs one sentence from each pair, so \(s1 \wedge s3\) (A) and \(s2 \wedge s3\) (C) both work. Option B repeats the first part and would still allow a round rugby ball; option D repeats the second part and would allow a non-rugby ball that is not round.

Answer: A, C

The query has one range condition, Movie.CustomerRating > 3.4, and only equality conditions otherwise: Genre.Name = "Comedy" and the two join conditions on the IDs.

• A B⁺ tree keeps its keys in sorted order, so it serves range searches as well as equality lookups.
• A hash index places keys by their hash values, so it can only find exact matches; it cannot list all ratings above 3.4.

A (B⁺ trees everywhere) and B (a hash index only on the equality attribute Genre.Name, B⁺ trees elsewhere) give every condition an index it can use. C and D put a hash index on CustomerRating, which cannot help the range condition, so the selection on Movie would still need a full scan.

Answer: A, B

By independence, \((X, Y)\) is uniform on the rectangle \([1, 3] \times [2, 4]\), whose area is 4, so a probability is the favourable area divided by 4.

Since \(Y\) is never below 2, \(X \ge Y\) can only happen when \(X \ge 2\). The favourable region is the triangle \(2 \le Y \le X \le 3\), with both legs of length 1:

\[ \text{area} = \int_{2}^{3} (x - 2)\,dx = \frac{1}{2}, \qquad P(X \ge Y) = \frac{1/2}{4} = \frac{1}{8} = 0.125 \]

Answer: 0.125

For an exponential random variable with rate \(\lambda\):

\[ E(X) = \int_{0}^{\infty} x\lambda e^{-\lambda x}\,dx = \frac{1}{\lambda}, \qquad Var(X) = E(X^{2}) - E(X)^{2} = \frac{2}{\lambda^{2}} - \frac{1}{\lambda^{2}} = \frac{1}{\lambda^{2}} \]

The condition \(5E(X) = Var(X)\) becomes \(\frac{5}{\lambda} = \frac{1}{\lambda^{2}}\). Multiplying by \(\lambda^{2}\), which is allowed because \(\lambda > 0\), gives \(5\lambda = 1\), so \(\lambda = 0.2\).

Taking the mean as \(\lambda\) instead of \(1/\lambda\) is the usual slip; it would give \(\lambda = 5\).

Answer: 0.2

First, \(P(T) = 1 - P(\overline{T}) = 0.4\). By the law of total probability,

\[ P(S) = P(S|T)P(T) + P(S|\overline{T})P(\overline{T}) = 0.3 \times 0.4 + 0.6 \times 0.6 = 0.12 + 0.36 = 0.48 \]

Bayes' theorem then reverses the conditioning:

\[ P(T|S) = \frac{P(S|T)P(T)}{P(S)} = \frac{0.12}{0.48} = 0.25 \]

Note that \(P(T|S) = 0.25\) differs from the given \(P(S|T) = 0.3\); confusing the two is the common trap.

Answer: 0.25

The marks went to all because the printed function is not a valid density: over its region it integrates to \(\int_{0}^{2}\int_{0}^{x} 2xy\,dy\,dx = \int_{0}^{2} x^{3}\,dx = 4\), not 1.

The conditional expectation can still be found as printed, because a constant factor cancels in a conditional density. For a fixed \(x\),

\[ f_{Y|X}(y|x) = \frac{2xy}{\int_{0}^{x} 2xy\,dy} = \frac{2xy}{x^{3}} = \frac{2y}{x^{2}}, \quad 0 < y < x \]

\[ E[Y|X = x] = \int_{0}^{x} y \cdot \frac{2y}{x^{2}}\,dy = \frac{2x}{3}, \qquad E[Y|X = 1.5] = \frac{2 \times 1.5}{3} = 1 \]

Answer: 1

The logarithm of a product splits into a sum:

\[ \frac{\ln((x^{2}+1)\cos x)}{x^{2}} = \frac{\ln(1 + x^{2})}{x^{2}} + \frac{\ln(\cos x)}{x^{2}} \]

• Since \(\ln(1 + t) \approx t\) for small \(t\), the first term tends to 1.
• Since \(\cos x \approx 1 - \frac{x^{2}}{2}\), we get \(\ln(\cos x) \approx -\frac{x^{2}}{2}\), so the second term tends to \(-\frac{1}{2}\).

The limit is \(1 - \frac{1}{2} = 0.5\). L'Hôpital's rule agrees: differentiating the top and the bottom gives \(\frac{2x/(1 + x^{2}) - \tan x}{2x}\), which also tends to \(1 - \frac{1}{2}\).

Answer: 0.5