GATE DA 2024

To insert a key with open addressing, we follow the key's probe sequence until we reach an empty slot and store the key there. An unsuccessful search for the same key follows the same sequence and also stops at the first empty slot, so an insertion makes exactly the probes of an unsuccessful search. Its average cost therefore has the same bound, at most \(\frac{1}{1-\alpha}\) probes.

Options A and C are smaller than this bound for every \(0 < \alpha < 1\), so they understate the cost; they resemble formulas for successful searches. Option D is even below 1, although every insertion probes at least one slot.

Answer: B

At the maximum the gradient of \(J\) is zero. Both matrices are symmetric, so by the quotient rule

\[\nabla J(u) = \frac{2 S_{B} u \,(u^{T} S_{W} u) - 2 S_{W} u \,(u^{T} S_{B} u)}{(u^{T} S_{W} u)^{2}} = 0 \;\Rightarrow\; S_{B} u^{*} = J(u^{*})\, S_{W} u^{*} = \lambda S_{W} u^{*}.\]

Since \(S_{W}\) is non-singular, multiplying by \(S_{W}^{-1}\) gives \(S_{W}^{-1} S_{B} u^{*} = \lambda u^{*}\): \(u^{*}\) is an eigenvector of \(S_{W}^{-1} S_{B}\) for its largest eigenvalue \(\lambda\).

Option B has \(\lambda\) on the wrong side (it would hold with \(1/\lambda\)), C multiplies by \(S_{W}\) instead of its inverse, and D fails because \(J\) does not depend on the length of \(u\), so \(u^{*}\) can be rescaled freely.

Answer: A

A heuristic is admissible when \(0 \leq h(n) \leq h^{*}(n)\) for every node \(n\), where \(h^{*}(n)\) is the true cost of reaching the goal. Because both values are non-negative,

\[|h_{1}(n) - h_{2}(n)| \leq \max(h_{1}(n), h_{2}(n)) \leq h^{*}(n),\]

so option D never overestimates.

The other expressions can overestimate. With \(h^{*}(n) = 5\) and \(h_{1}(n) = h_{2}(n) = 5\), both admissible, the sum is 10 and the product is 25. With \(h_{1}(n) = 5\) and \(h_{2}(n) = 0.1\), the ratio is 50.

Answer: D

The factorisation is the Bayesian network \(U \rightarrow W \leftarrow V\), \(W \rightarrow X\), \(W \rightarrow Y\).

• A and B: \(U\) and \(V\) reach \(X\) and \(Y\) only through chains such as \(V \rightarrow W \rightarrow Y\), and observing \(W\) blocks a chain. Both are true.
• D: \(X \leftarrow W \rightarrow Y\) has \(W\) as a common cause, so \(X\) and \(Y\) are independent once \(W\) is known. True.
• C: \(U\) and \(V\) are independent on their own (the factor \(P(U)P(V)\)), but \(W\) is their common effect. Observing a common effect couples its causes (explaining away): once \(W\) is known, learning \(U\) changes what \(V\) is likely to be. So C does not hold in general.

Answer: C

Alpha–beta pruning carries two bounds down the game tree:

• \(\alpha\) is the value MAX can already guarantee along the path. MAX wants large values, so \(\alpha\) is the highest value found so far.
• \(\beta\) is the value MIN can already guarantee. MIN wants small values, so \(\beta\) is the lowest value found so far.

A branch is pruned as soon as \(\alpha \geq \beta\), because the player choosing above it already has a better alternative and would never let play reach it. The other options give MAX, MIN or both the preference of the opponent, so the bounds would no longer be values that player can guarantee.

Answer: C

The condition says that the set of Team names is contained in the set of names that occur in Defender or Forward:

\[\Pi_{\mathit{name}}(\text{Team}) \subseteq \Pi_{\mathit{name}}(\text{Defender}) \cup \Pi_{\mathit{name}}(\text{Forward}).\]

A set \(A\) is a subset of \(B\) exactly when \(A \setminus B = \phi\): nothing in \(A\) is left over after removing the members of \(B\). That is option C.

• A uses \(\cap\), so it would demand that every Team name occur in both Defender and Forward.
• B and D test the opposite inclusion, that the players' names all occur in Team.

Answer: C

z-score normalization subtracts the mean and divides by the standard deviation:

\[z = \frac{x - \mu}{\sigma} = \frac{106000 - 96000}{21000} = \frac{10000}{21000} \approx 0.476.\]

The minimum and maximum play no part here. They are what min-max normalization uses, and that would give \(\frac{106000 - 46000}{170000 - 46000} \approx 0.484\), which is not an option either. Option A divides the difference from the mean by the minimum instead of the standard deviation, and D divides the income itself by the minimum.

Answer: B

Take the node labels to be distinct. In a full binary tree every node has 0 or 2 children.

• With inorder (A, B): the root is the first node in preorder or the last in postorder, and its position in inorder splits the other nodes into the left and right subtrees. Repeating this rebuilds any binary tree.
• Preorder and postorder (C): for general trees a lone child could be left or right, but here an internal node always has two children. The node after the root in preorder is the left child, and its place in postorder marks where the left subtree ends, so the split is again unique.
• Inorder only (D): the full trees with root 2 (children 1 and 4, where 4 has children 3 and 5) and root 4 (children 2 and 5, where 2 has children 1 and 3) both give 1 2 3 4 5.

Answer: A, B, C

An implication is false only when its premise is true and its conclusion is false. Each premise here is true in exactly one row of the truth table, so check the conclusion in that row.

• A: \(\neg x \land y\) needs \(x\) false and \(y\) true. Then \(y \Longrightarrow x\) is true \(\Longrightarrow\) false, which is false. Not a tautology.
• B: \(x \land \neg y\) needs \(x\) true and \(y\) false. Then \(\neg x\) is false, so \(\neg x \Longrightarrow y\) is true. Tautology.
• C: \(x\) false and \(y\) true make \(\neg x \Longrightarrow y\) true \(\Longrightarrow\) true, which is true. Tautology.
• D: \(x\) true and \(y\) false make \(y \Longrightarrow x\) false \(\Longrightarrow\) true, which is true. Tautology.

Answer: B, C, D

The array is already sorted. In the first partition the pivot is 100 and every other element is smaller, so they all already sit on the left side and the pivot is already in its final place. Each later call looks the same: on 60 70 80 90 the pivot 90 is the largest, then 80, then 70.

A Lomuto-style partition would only ever swap an element with itself here, because its two indices are always equal, and such a step moves nothing and can be skipped. No element ever has to change place, so the minimum number of swaps is 0.

Answer: 0