GATE DA 2024 - W3Colleges

Question 41

MCQ · 2 marks · −0.66

Consider the following Python function:

def fun(D, s1, s2):
       if s1 < s2:
          D[s1], D[s2] = D[s2], D[s1]
          fun(D, s1+1, s2-1)

What does this Python function fun() do? Select the ONE appropriate option below.

It finds the smallest element in D from index s1 to s2, both inclusive. It performs a merge sort in-place on this list D between indices s1 and s2, both inclusive. It reverses the list D between indices s1 and s2, both inclusive. It swaps the elements in D at indices s1 and s2, and leaves the remaining elements unchanged.

Explanation

Answer: (C)

Each call swaps the two outer elements D[s1] and D[s2], then recurses on the next pair inward, s1+1 and s2-1. It stops when the indices meet or cross, so the middle element of an odd-length range stays where it is.

For example, with D = [1, 2, 3, 4, 5], fun(D, 0, 4) swaps 1 and 5, then 2 and 4, giving [5, 4, 3, 2, 1]: the segment from s1 to s2 is reversed in place.

Option D describes only the first call, but the recursion keeps swapping the inner pairs. The function never compares values, so it cannot find a minimum (A) or sort (B).

Answer: C

Question 42

MCQ · 2 marks · −0.66

Consider the table below, where the \((i, j)^{th}\) element of the table is the distance between points \(x_{i}\) and \(x_{j}\). Single linkage clustering is performed on data points, \(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\).

	\(x_{1}\)	\(x_{2}\)	\(x_{3}\)	\(x_{4}\)	\(x_{5}\)
\(x_{1}\)	0	1	4	3	6
\(x_{2}\)	1	0	3	5	3
\(x_{3}\)	4	3	0	2	5
\(x_{4}\)	3	5	2	0	1
\(x_{5}\)	6	3	5	1	0

Which ONE of the following is the correct representation of the clusters produced?

Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x4 joins x5 at the lowest level, x3 then joins the x4, x5 pair, and finally the x1, x2 pair joins the x3, x4, x5 group at the top.

Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x4 joins x5 at the lowest level, x3 then joins the x1, x2 pair, and finally the x1, x2, x3 group joins the x4, x5 pair at the top.

Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x3 joins x4 at the lowest level, x5 then joins the x3, x4 pair, and finally the x1, x2 pair joins the x3, x4, x5 group at the top.

Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x3 joins x4 at the lowest level, the two pairs then merge, and finally x5 joins the x1, x2, x3, x4 group at the top.

Explanation

Answer: (A)

Single linkage repeatedly merges the two clusters whose closest members are nearest to each other.

Distance 1: \(x_{1}\) joins \(x_{2}\), and \(x_{4}\) joins \(x_{5}\).
Distance 2: \(x_{3}\) joins \(\{x_{4}, x_{5}\}\) through \(d(x_{3}, x_{4}) = 2\); the pair \(\{x_{1}, x_{2}\}\) is at least 3 from every other point.
Distance 3: \(\{x_{1}, x_{2}\}\) joins \(\{x_{3}, x_{4}, x_{5}\}\), for example through \(d(x_{1}, x_{4}) = 3\).

Dendrogram A shows exactly this. B attaches \(x_{3}\) to \(\{x_{1}, x_{2}\}\), where its nearest link is 3, not 2. C and D pair \(x_{3}\) with \(x_{4}\) first, although \(d(x_{4}, x_{5}) = 1\) is smaller than \(d(x_{3}, x_{4}) = 2\).

Answer: A

Question 43

MCQ · 2 marks · −0.66

Consider the two neural networks (NNs) shown in Figures 1 and 2, with \(ReLU\) activation (\(ReLU(z) = \max\{0, z\}, \forall z \in \mathbb{R}\)). \(\mathbb{R}\) denotes the set of real numbers. The connections and their corresponding weights are shown in the Figures. The biases at every neuron are set to 0. For what values of \(p, q, r\) in Figure 2 are the two NNs equivalent, when \(x_{1}, x_{2}, x_{3}\) are positive?

Figure 1

Network with inputs x1, x2 and x3, a first layer of three neurons, a second layer of two neurons and one output neuron. All input edges have weight 1 (x1 connects to all three first-layer neurons, x2 to the top and bottom ones, x3 to the middle and bottom ones); every first-layer neuron connects to both second-layer neurons with weight 2, and both second-layer neurons connect to the output with weight 3.

Figure 2

Network in which inputs x1, x2 and x3 connect directly to a single output neuron with weights p, q and r respectively.

\(p = 36, q = 24, r = 24\) \(p = 24, q = 24, r = 36\) \(p = 18, q = 36, r = 24\) \(p = 36, q = 36, r = 36\)

Explanation

Answer: (A)

The inputs and all weights are positive, so every neuron receives a positive value and \(ReLU\) acts as the identity. Both networks are then linear, and only the total weight from each input to the output matters.

First layer (weights 1): the neurons receive \(x_{1} + x_{2}\), \(x_{1} + x_{3}\) and \(x_{1} + x_{2} + x_{3}\), which add up to \(s = 3x_{1} + 2x_{2} + 2x_{3}\).
Second layer: each of its two neurons receives \(2s\).
Output: \(3(2s) + 3(2s) = 12s\).

So Figure 1 computes \(36x_{1} + 24x_{2} + 24x_{3}\), giving \(p = 36\), \(q = 24\), \(r = 24\). Option D would need \(x_{2}\) and \(x_{3}\) to reach all three first-layer neurons, but each has only two connections.

Answer: A

Question 44

MCQ · 2 marks · −0.66

Consider a state space where the start state is number 1. The successor function for the state numbered \(n\) returns two states numbered \(n+1\) and \(n+2\). Assume that the states in the unexpanded state list are expanded in the ascending order of numbers and the previously expanded states are not added to the unexpanded state list.

Which ONE of the following statements about breadth-first search (BFS) and depth-first search (DFS) is true, when reaching the goal state number 6?

BFS expands more states than DFS. DFS expands more states than BFS. Both BFS and DFS expand equal number of states. Both BFS and DFS do not reach the goal state number 6.

Explanation

Answer: (C)

Successors come out as \(n+1\) and then \(n+2\), and the smaller number always goes first.

BFS: expanding 1 queues 2 and 3; expanding 2 adds 4 (3 is already waiting); expanding 3 adds 5; expanding 4 adds 6; expanding 5 adds 7. Then 6 leaves the queue. Expanded: 1, 2, 3, 4, 5.
DFS: it always dives into the smaller child \(n+1\), so it expands 1, 2, 3, 4, 5 and then reaches 6.

Both searches expand the same five states before reaching the goal (or four each if the goal is tested when it is generated, since both then stop while expanding 4). State 6 is reachable, so option D is false.

Answer: C

Question 45

MCQ · 2 marks · −0.66

Consider the following sorting algorithms:

(i) Bubble sort
(ii) Insertion sort
(iii) Selection sort

Which ONE among the following choices of sorting algorithms sorts the numbers in the array [4, 3, 2, 1, 5] in increasing order after exactly two passes over the array?

(i) only (iii) only (i) and (iii) only (ii) and (iii) only

Explanation

Answer: (B)

Trace two passes of each algorithm on [4, 3, 2, 1, 5]:

Bubble sort: pass 1 carries 4 to its place, giving [3, 2, 1, 4, 5]; pass 2 carries 3, giving [2, 1, 3, 4, 5]. Not yet sorted.
Insertion sort: pass 1 inserts 3, giving [3, 4, 2, 1, 5]; pass 2 inserts 2, giving [2, 3, 4, 1, 5]. Not yet sorted.
Selection sort: pass 1 swaps the minimum 1 into the first position, giving [1, 3, 2, 4, 5]; pass 2 swaps 2 into the second position, giving [1, 2, 3, 4, 5]. Sorted.

Only selection sort is done, because its two swaps happen to fix every misplaced element; bubble sort and insertion sort each need a third pass.

Answer: B

Question 46

MSQ · 2 marks

Given the relational schema \(R = (U, V, W, X, Y, Z)\) and the set of functional dependencies:

\[\{U \to V, U \to W, WX \to Y, WX \to Z, V \to X\}\]

Which of the following functional dependencies can be derived from the above set?

\(VW \to YZ\) \(WX \to YZ\) \(VW \to U\) \(VW \to Y\)

Explanation

Answer: (A), (B), (D)

Compute attribute closures.

\(\{V, W\}^{+}\): \(V \to X\) adds \(X\), and then \(WX \to Y\) and \(WX \to Z\) add \(Y\) and \(Z\). So \(\{V, W\}^{+} = \{V, W, X, Y, Z\}\).
\(\{W, X\}^{+} = \{W, X, Y, Z\}\), straight from the two given dependencies.

Hence \(VW \to YZ\) (A) and \(VW \to Y\) (D) hold, and \(WX \to YZ\) (B) is the union rule applied to \(WX \to Y\) and \(WX \to Z\). But \(U\) is not in \(\{V, W\}^{+}\): no dependency has \(U\) on its right-hand side, so only sets containing \(U\) determine it, and C cannot be derived.

Answer: A, B, D

Question 47

MSQ · 2 marks

Select all choices that are subspaces of \(\mathbb{R}^{3}\).

Note: \(\mathbb{R}\) denotes the set of real numbers.

\(\left\{\mathbf{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} \in \mathbb{R}^{3} : \mathbf{x} = \alpha \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \alpha, \beta \in \mathbb{R}\right\}\) \(\left\{\mathbf{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} \in \mathbb{R}^{3} : \mathbf{x} = \alpha^{2} \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix} + \beta^{2} \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}, \alpha, \beta \in \mathbb{R}\right\}\) \(\left\{\mathbf{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} \in \mathbb{R}^{3} : 5x_{1} + 2x_{3} = 0, 4x_{1} - 2x_{2} + 3x_{3} = 0\right\}\) \(\left\{\mathbf{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} \in \mathbb{R}^{3} : 5x_{1} + 2x_{3} + 4 = 0\right\}\)

Explanation

Answer: (A), (C)

A subset of \(\mathbb{R}^{3}\) is a subspace when it contains \(\mathbf{0}\) and is closed under addition and scalar multiplication.

(A) is the span of \((1, 1, 0)\) and \((1, 0, 0)\), the plane \(x_{3} = 0\): a subspace.
(B) The coefficients \(\alpha^{2}\) and \(\beta^{2}\) are never negative, so the set holds only the non-negative combinations of the two vectors (a cone, not a plane). It contains \((1, 2, 0)\) but not \((-1, -2, 0)\), which would need \(\alpha^{2} = -1\).
(C) is the solution set of a homogeneous linear system, the null space of a \(2 \times 3\) matrix: a subspace.
(D) The zero vector gives \(5(0) + 2(0) + 4 = 4 \ne 0\), so \(\mathbf{0}\) is missing; this is a shifted plane.

Answer: A, C

Question 48

MSQ · 2 marks

Which of the following statements is/are TRUE?

Note: \(\mathbb{R}\) denotes the set of real numbers.

There exist \(\boldsymbol{M} \in \mathbb{R}^{3 \times 3}\), \(\boldsymbol{p} \in \mathbb{R}^{3}\), and \(\boldsymbol{q} \in \mathbb{R}^{3}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has a unique solution and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has infinite solutions. There exist \(\boldsymbol{M} \in \mathbb{R}^{3 \times 3}\), \(\boldsymbol{p} \in \mathbb{R}^{3}\), and \(\boldsymbol{q} \in \mathbb{R}^{3}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has no solutions and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has infinite solutions. There exist \(\boldsymbol{M} \in \mathbb{R}^{2 \times 3}\), \(\boldsymbol{p} \in \mathbb{R}^{2}\), and \(\boldsymbol{q} \in \mathbb{R}^{2}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has a unique solution and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has infinite solutions. There exist \(\boldsymbol{M} \in \mathbb{R}^{3 \times 2}\), \(\boldsymbol{p} \in \mathbb{R}^{3}\), and \(\boldsymbol{q} \in \mathbb{R}^{3}\) such that \(\boldsymbol{M}\mathbf{x} = \boldsymbol{p}\) has a unique solution and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) has no solutions.

Explanation

Answer: (B), (D)

A consistent system \(\boldsymbol{M}\mathbf{x} = \boldsymbol{b}\) has a unique solution exactly when the null space of \(\boldsymbol{M}\) is \(\{\mathbf{0}\}\); otherwise every consistent right-hand side has infinitely many solutions.

(A) False. A unique solution forces a trivial null space, so the square \(\boldsymbol{M}\) is invertible and \(\boldsymbol{M}\mathbf{x} = \boldsymbol{q}\) also has exactly one solution.
(B) True. Take \(\boldsymbol{M} = \operatorname{diag}(1, 1, 0)\), \(\boldsymbol{p} = (0, 0, 1)^{\top}\) (no solution) and \(\boldsymbol{q} = \mathbf{0}\) (infinitely many).
(C) False. With 3 unknowns and rank at most 2, the null space is never trivial, so no solution is unique.
(D) True. Let \(\boldsymbol{M}\) have columns \((1, 0, 0)^{\top}\) and \((0, 1, 0)^{\top}\). Then \(\boldsymbol{p} = (1, 1, 0)^{\top}\) has the single solution \((1, 1)\), while \(\boldsymbol{q} = (0, 0, 1)^{\top}\) lies outside the column space.

Answer: B, D

Question 49

MSQ · 2 marks

Let \(\mathbb{R}\) be the set of real numbers, \(U\) be a subspace of \(\mathbb{R}^{3}\) and \(\boldsymbol{M} \in \mathbb{R}^{3 \times 3}\) be the matrix corresponding to the projection on to the subspace \(U\).

Which of the following statements is/are TRUE?

If \(U\) is a 1-dimensional subspace of \(\mathbb{R}^{3}\), then the null space of \(\boldsymbol{M}\) is a 1-dimensional subspace. If \(U\) is a 2-dimensional subspace of \(\mathbb{R}^{3}\), then the null space of \(\boldsymbol{M}\) is a 1-dimensional subspace. \(\boldsymbol{M}^{2} = \boldsymbol{M}\) \(\boldsymbol{M}^{3} = \boldsymbol{M}\)

Explanation

Answer: (B), (C), (D)

A projection onto \(U\) leaves every vector of \(U\) unchanged and sends the complementary directions to \(\boldsymbol{0}\). So its column space is \(U\), and by rank–nullity its null space has dimension \(3 - \dim U\).

A fails: a line \(U\) leaves a null space of dimension \(3 - 1 = 2\), a plane.
B holds: a plane \(U\) leaves a null space of dimension \(3 - 2 = 1\), a line.
C holds: \(\boldsymbol{M}\boldsymbol{x}\) already lies in \(U\), so projecting it again changes nothing, which gives \(\boldsymbol{M}^{2} = \boldsymbol{M}\).
D holds: \(\boldsymbol{M}^{3} = \boldsymbol{M}^{2}\boldsymbol{M} = \boldsymbol{M}\boldsymbol{M} = \boldsymbol{M}\).

Answer: B, C, D

Question 50

MSQ · 2 marks

Consider the function \(f: \mathbb{R} \to \mathbb{R}\) where \(\mathbb{R}\) is the set of all real numbers.

\[ f(x) = \frac{x^{4}}{4} - \frac{2x^{3}}{3} - \frac{3x^{2}}{2} + 1 \]

Which of the following statements is/are TRUE?

\(x = 0\) is a local maximum of \(f\) \(x = 3\) is a local minimum of \(f\) \(x = -1\) is a local maximum of \(f\) \(x = 0\) is a local minimum of \(f\)

Explanation

Answer: (A), (B)

Differentiate and factor:

\[ f'(x) = x^{3} - 2x^{2} - 3x = x(x - 3)(x + 1) \]

so the critical points are \(x = -1, 0, 3\). Test each with the second derivative \(f''(x) = 3x^{2} - 4x - 3\):

\(f''(0) = -3 < 0\): a local maximum at \(x = 0\), so A holds and D fails.
\(f''(3) = 27 - 12 - 3 = 12 > 0\): a local minimum at \(x = 3\), so B holds.
\(f''(-1) = 3 + 4 - 3 = 4 > 0\): \(x = -1\) is a local minimum, not a maximum, so C fails.

Answer: A, B

Data Science and Artificial Intelligence