GATE DA 2024

(i) A Poisson random variable with parameter \(\lambda\) has \(P(X = k) = \dfrac{e^{-\lambda}\lambda^{k}}{k!}\), and both its mean and its variance equal \(\lambda\). True.

(ii) The standard normal distribution \(N(0, 1)\) is, by definition, the normal distribution with mean 0 and variance 1; any normal variable is brought to it by \(Z = (X - \mu)/\sigma\). True.

Both statements hold.

Answer: A

\(T \cap S\) needs at least two heads and at least two tails, which takes at least four tosses. With three coins, two or more heads leave at most one tail, so the two events can never happen together.

\(T\) and \(S\) are mutually exclusive (in fact complementary, since every outcome of three tosses has a majority of heads or a majority of tails), so \(P(T \cap S) = 0\). The value 0.5 is \(P(T)\) alone.

Answer: A

For a \(2 \times 2\) matrix the characteristic equation is \(\lambda^{2} - (\operatorname{tr}\boldsymbol{M})\lambda + \det \boldsymbol{M} = 0\). Here \(\operatorname{tr}\boldsymbol{M} = 2 + 1 = 3\) and \(\det \boldsymbol{M} = 2 \cdot 1 - (-1) \cdot 3 = 5\), so

\[\lambda^{2} - 3\lambda + 5 = 0, \qquad \lambda = \frac{3 \pm \sqrt{9 - 20}}{2} = \frac{3 \pm i\sqrt{11}}{2}.\]

The discriminant is negative, so the eigenvalues form a complex conjugate pair and none is real, which rules out (A), (C) and (D). A zero eigenvalue would also need \(\det \boldsymbol{M} = 0\).

Answer: B

In a DFS of an undirected graph, every edge ends up as either a tree edge or a back edge. Cross (and forward) edges cannot occur: a vertex finishes only after all of its edges have been explored, so the far end of a newly explored edge is never already finished. Gray is the colour of a vertex that is discovered but not finished, not a kind of edge. So (B) and (D) are out.

The key reads "explored first in the direction from \(u\) to \(v\)" as the search moving from \(u\), the end nearer to \(s\), along this edge out to \(v\). DFS moves along an edge only to a vertex it has not discovered yet, so \(v\) is discovered through \((u, v)\) and the edge becomes a tree edge. A back edge, (C), would need \(v\) to be discovered already, and then the search does not move to \(v\) at all.

Answer: A

This is the second-derivative test. \(f'(x^{*}) = 0\) makes \(x^{*}\) a stationary point, and \(f''(x^{*}) > 0\) means \(f'\) is increasing through \(x^{*}\): \(f' < 0\) just to the left and \(f' > 0\) just to the right. So \(f\) falls and then rises near \(x^{*}\), giving a local minimum; a maximum is impossible.

The test only looks near \(x^{*}\), so a global minimum is not guaranteed: \(f(x) = x^{3} - 3x\) has \(f'(1) = 0\) and \(f''(1) = 6 > 0\), yet \(f(x) \to -\infty\) as \(x \to -\infty\).

Answer: A

Each phrase in Column 1 is the defining behaviour of one structure:

• (p) First In First Out: a queue removes items in the order they arrived, like a line at a counter, so (p) − (ii).
• (q) Lookup: a hash table exists to find a value by its key in expected constant time, so (q) − (iii).
• (r) Last In First Out: a stack always removes the most recently added item, like a pile of plates, so (r) − (i).

Only option (A) has all three pairs; (C) and (D) pair FIFO with stacks, and (B) pairs lookup with stacks.

Answer: A

Each negative point is the mirror image of a positive one through the origin. Write the separator as \(\boldsymbol{w}^{\top}\boldsymbol{x} + b\) with \(\boldsymbol{w} = (w_{1}, w_{2})\). The hard-margin constraints \(y_{i}(\boldsymbol{w}^{\top}\boldsymbol{x}_{i} + b) \geq 1\) for \(\boldsymbol{x}_{1}\) and \(\boldsymbol{x}_{4}\) read \(w_{1} + b \geq 1\) and \(w_{1} - b \geq 1\), so \(w_{1} \geq 1\); \(\boldsymbol{x}_{2}\) and \(\boldsymbol{x}_{3}\) give \(w_{2} \geq 1\) in the same way. So \(\lVert\boldsymbol{w}\rVert^{2} \geq 2\), and \(\boldsymbol{w} = (1, 1)\), \(b = 0\) reaches this while meeting every constraint, so it is the maximum-margin solution.

For this hyperplane, \(\boldsymbol{x}_{1}\) to \(\boldsymbol{x}_{4}\) give \(y_{i}(\boldsymbol{w}^{\top}\boldsymbol{x}_{i} + b) = 1\): they lie on the margin and are the support vectors. \(\boldsymbol{x}_{5}\) and \(\boldsymbol{x}_{6}\) give 4, well outside the margin, which rules out A, B and C (A even holds points of one class only).

Answer: D

Match each method by what it learns.

• (p) Principal Component Analysis projects the data onto the few directions of largest variance, keeping most of the information in fewer features: dimensionality reduction, (ii).
• (q) Naïve Bayes models how the data are generated, through \(P(\text{class})\) and \(P(\text{features} \mid \text{class})\), and gets the class from Bayes' theorem: a generative model, (iii).
• (r) Logistic regression models \(P(\text{class} \mid \text{features})\) directly and never models the features themselves: a discriminative model, (i).

Options A and D call PCA a generative model, and B swaps the two classifiers.

Answer: C

\(k\)-means assigns every point to its nearest centroid, so cluster 3 holds the points that are closer to its centroid \(\boldsymbol{c}_{3}\) than to \(\boldsymbol{c}_{1}\) and \(\boldsymbol{c}_{2}\). For each other centroid \(\boldsymbol{c}_{j}\), the condition \(\lVert\boldsymbol{p} - \boldsymbol{c}_{3}\rVert^{2} \leq \lVert\boldsymbol{p} - \boldsymbol{c}_{j}\rVert^{2}\) simplifies to a linear inequality in \(\boldsymbol{p}\), that is, a half-plane. The region of cluster 3 is an intersection of half-planes, so it is convex: with any two of its points it contains the whole segment between them.

The point \((0, 1)\) is the midpoint of \((1, 1)\) and \((-1, 1)\), so it must belong to cluster 3. The points in A, B and C lie off that segment, and another centroid could be nearer to them.

Answer: D

Naïve Bayes assumes that the attributes are conditionally independent given the class, so it needs only these parameters:

• the class prior \(P(y = 1)\): one parameter, because \(P(y = 0) = 1 - P(y = 1)\);
• for each of the 2 classes and each of the \(K\) attributes, \(P(x_{k} = 1 \mid y)\): \(2K\) parameters, because \(P(x_{k} = 0 \mid y)\) follows from it.

The total is \(2K + 1\). Counts that grow like \(2^{K}\) (A and C) are what a model of the full joint distribution of the attributes within each class would need, which is exactly what the independence assumption avoids.

Answer: B