GATE CS 2024 Set 2 - W3Colleges

Question 41

MCQ · 2 marks · −0.66

Let \(M\) be the 5-state NFA with \(\epsilon\)-transitions shown in the diagram below.

NFA with states 1 to 5: state 1 is the start state and states 2 and 5 are accepting (double circles). State 1 has epsilon-transitions to states 2 and 4, states 2 and 3 are joined by 0-transitions in both directions, state 3 has an epsilon-transition to state 5, and states 4 and 5 are joined by 1-transitions in both directions.

Which one of the following regular expressions represents the language accepted by \(M\) ?

\((00)^{*} + 1(11)^{*}\) \(0^{*} + (1 + 0(00)^{*})(11)^{*}\) \((00)^{*} + (1 + (00)^{*})(11)^{*}\) \(0^{+} + 1(11)^{*} + 0(11)^{*}\)

Explanation

Answer: (B)

Follow the two \(\epsilon\)-moves out of the start state 1.

Into state 2, which accepts: the 0-loop through state 3 accepts \((00)^{*}\). From state 3, reached after an odd number of 0s, the \(\epsilon\)-move enters the accepting state 5, where the 1-loop adds any number of 11s: \(0(00)^{*}(11)^{*}\).
Into state 4: one 1 reaches state 5, and each further 11 returns there: \(1(11)^{*}\).

So \(L(M) = (00)^{*} + 0(00)^{*}(11)^{*} + 1(11)^{*}\). Because \(0^{*} = (00)^{*} + 0(00)^{*}\) and \(0(00)^{*}\) is already inside \(0(00)^{*}(11)^{*}\), this is exactly option (B). Option (A) misses 0, (C) misses 0 and wrongly accepts 11, and (D) misses the empty string and 00011.

Answer: B

Question 42

MCQ · 2 marks · −0.66

Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices.

The C code snippet given below has been written to compute the length of the longest subarray of X that contains at most two distinct integers. The code has two missing expressions labelled \((P)\) and \((Q)\).

int first=0, second=0, len1=0, len2=0, maxlen=0;
for (int i=0; i < n; i++) {
  if (X[i] == first) {
    len2++; len1++;
  } else if (X[i] == second) {
    len2++;
    len1 = ___(P)___;
    second = first;
  } else {
    len2 = ___(Q)___;
    len1 = 1; second = first;
  }
  if (len2 > maxlen) {
    maxlen = len2;
  }
  first = X[i];
}

Which one of the following options gives the CORRECT missing expressions?

(Hint: At the end of the i-th iteration, the value of len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)

\((P)\) len1+1 \((Q)\) len2+1 \((P)\) 1 \((Q)\) len1+1 \((P)\) 1 \((Q)\) len2+1 \((P)\) len2+1 \((Q)\) len1+1

Explanation

Answer: (B)

During iteration i, first holds the previous element and second the other value in the current two-value window.

X[i] == second: the window still has only two values, so len2 grows by 1. But X[i] differs from the previous element, so the run of equal values ending at X[i] starts again: (P) is 1.
A new value: the window must drop second. The longest valid subarray ending at X[i] is the final run of first values, of length len1, plus X[i]: (Q) is len1+1.

For example, for 1, 2, 1, 3 the correct value at 3 is 2 (the subarray 1, 3), which len1+1 gives, while len2+1 would give 4.

Answer: B

Question 43

MCQ · 2 marks · −0.66

Consider the following expression: \(x[i] = (p + r) * -s[i] + u/w\). The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6).

(0)	+	\(p\)	\(r\)
(1)
(2)	uminus	(1)
(3)
(4)	/	\(u\)	\(w\)
(5)	+	(3)	(4)
(6)
(7)	=	(6)	(5)

Which one of the following options fills in the missing entries CORRECTLY?

(1) =[] \(s\) \(i\) (3) * (0) (2) (6) []= \(x\) \(i\) (1) []= \(s\) \(i\) (3) – (0) (2) (6) =[] \(x\) (5) (1) =[] \(s\) \(i\) (3) * (0) (2) (6) []= \(x\) (5) (1) []= \(s\) \(i\) (3) – (0) (2) (6) =[] \(x\) \(i\)

Explanation

Answer: (A)

Triples have no result names: an operand is either a name or the number of an earlier triple.

(1) =[] s i reads the element \(s[i]\), the value that (2) negates. The operator []= stores into an array element and produces no value for uminus to use.
(3) * (0) (2) multiplies \(p + r\) by \(-s[i]\), which (5) then adds to \(u/w\). The expression contains no subtraction, so the options with – fail here too.
(6) []= x i marks the array location \(x[i]\), and (7) assigns the value of (5) to it. Putting (5) inside (6) would lose the index \(i\) and duplicate the work of (7).

Answer: A

Question 44

MCQ · 2 marks · −0.66

Let \(x\) and \(y\) be random variables, not necessarily independent, that take real values in the interval \([0,1]\). Let \(z = xy\) and let the mean values of \(x, y, z\) be \(\overline{x}, \overline{y}, \overline{z}\), respectively. Which one of the following statements is TRUE?

\(\overline{z} = \overline{x}\,\overline{y}\) \(\overline{z} \le \overline{x}\,\overline{y}\) \(\overline{z} \ge \overline{x}\,\overline{y}\) \(\overline{z} \le \overline{x}\)

Explanation

Answer: (D)

Because \(0 \le y \le 1\) and \(x \ge 0\), every outcome has \(z = xy \le x\). Taking expectations keeps the inequality, so \(\overline{z} \le \overline{x}\) always holds.

Options (A) to (C) compare \(E[xy]\) with \(E[x]\,E[y]\); the difference is the covariance of \(x\) and \(y\), which can have either sign when they are dependent. Take \(x\) uniform on \([0,1]\):

\(y = x\): \(\overline{z} = E[x^{2}] = \tfrac{1}{3} > \tfrac{1}{4} = \overline{x}\,\overline{y}\), so (A) and (B) fail.
\(y = 1 - x\): \(\overline{z} = \tfrac{1}{2} - \tfrac{1}{3} = \tfrac{1}{6} < \tfrac{1}{4} = \overline{x}\,\overline{y}\), so (C) fails.

Answer: D

Question 45

MCQ · 2 marks · −0.66

The relation schema, Person(pid,city), describes the city of residence for every person uniquely identified by pid. The following relational algebra operators are available: selection, projection, cross product, and rename.

To find the list of cities where at least 3 persons reside, using the above operators, the minimum number of cross product operations that must be used is

1 2 3 4

Explanation

Answer: (B)

With no grouping or counting, “at least 3 persons” has to be found as three tuples with the same city and pairwise different pids. Two cross products bring three renamed copies together:

\[\pi_{P_1.\mathit{city}}\big(\sigma_{C}(\rho_{P_1}(\mathit{Person}) \times \rho_{P_2}(\mathit{Person}) \times \rho_{P_3}(\mathit{Person}))\big)\]

where \(C\) requires equal cities and \(P_1.\mathit{pid} \ne P_2.\mathit{pid}\), \(P_1.\mathit{pid} \ne P_3.\mathit{pid}\), \(P_2.\mathit{pid} \ne P_3.\mathit{pid}\).

One cross product is not enough. An expression with at most one cross product builds each answer from at most two Person tuples. If it reported a city with three residents, it would also report that city for a relation holding only the two tuples it used, where that city has at most two residents.

Answer: B

Question 46

MSQ · 2 marks

Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also share a global variable x (initialized to 0). The threads execute the code shown below.

// code of T1
wait(s1);
x = x+1;
print(x);
wait(s2);
signal(s1);

// code of T2
wait(s1);
x = x+1;
print(x);
signal(s2);
signal(s1);

Which of the following outcomes is/are possible when threads T1 and T2 execute concurrently?

T1 runs first and prints 1, T2 runs next and prints 2 T2 runs first and prints 1, T1 runs next and prints 2 T1 runs first and prints 1, T2 does not print anything (deadlock) T2 runs first and prints 1, T1 does not print anything (deadlock)

Explanation

Answer: (B), (C)

Only one thread at a time can be between wait(s1) and signal(s1), and s2 starts at 0.

If T2 gets s1 first, it prints 1, and its signal(s2) and signal(s1) never block. T1 then enters, prints 2, finds s2 at 1 and finishes. So (B) is possible, and (D) is not: T1 cannot stay blocked.
If T1 gets s1 first, it prints 1 and blocks on wait(s2) while still holding s1. Only T2 could signal s2, but it is stuck at wait(s1), so both wait forever and T2 prints nothing. So (C) is possible and (A) is not.

Answer: B, C

Question 47

MSQ · 2 marks

Let \(A\) be an \(n \times n\) matrix over the set of all real numbers \(\mathbb{R}\). Let \(B\) be a matrix obtained from \(A\) by swapping two rows. Which of the following statements is/are TRUE?

The determinant of \(B\) is the negative of the determinant of \(A\) If \(A\) is invertible, then \(B\) is also invertible If \(A\) is symmetric, then \(B\) is also symmetric If the trace of \(A\) is zero, then the trace of \(B\) is also zero

Explanation

Answer: (A), (B)

(A) True: swapping two rows multiplies the determinant by \(-1\), so \(\det B = -\det A\).
(B) True: if \(A\) is invertible, \(\det B = -\det A \ne 0\), so \(B\) is invertible too.
(C) False: \(\begin{pmatrix} 1 & 2 \\ 2 & 3 \end{pmatrix}\) is symmetric, but swapping its rows gives \(\begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix}\), which is not.
(D) False: \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) has trace 0, but swapping its rows gives the identity matrix, whose trace is 2. A row swap moves entries onto and off the diagonal, so the trace can change.

Answer: A, B

Question 48

MSQ · 2 marks

Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below.

Stack `S1`
400 (Top)
300
200
100

Stack `S2`

Only the following three operations are available:
PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.

Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack.

Which of the following output sequences can be generated by using the above operations?

100, 200, 400, 300 200, 300, 400, 100 400, 200, 100, 300 300, 200, 400, 100

Explanation

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

Only S1 can output, and S2 can park at most two elements taken from the top of S1.

(A) Impossible: to output 100 first, the three elements above it (400, 300 and 200) must all be parked, but S2 holds only two.
(B) Park 400 and 300, output 200, move 300 back and output it, move 400 back and output it, then output 100.
(C) Output 400, park 300, output 200 and 100, then move 300 back and output it.
(D) Park 400, output 300 and 200, move 400 back and output it, then output 100.

Answer: B, C, D

Question 49

MSQ · 2 marks

Which of the following is/are EQUAL to 224 in radix-5 (i.e., base-5) notation?

64 in radix-10 100 in radix-8 50 in radix-16 121 in radix-7

Explanation

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

Convert every numeral to decimal using its place values.

\(224_5 = 2 \times 5^{2} + 2 \times 5 + 4 = 50 + 10 + 4 = 64\).
(A) \(64_{10} = 64\): equal.
(B) \(100_8 = 1 \times 8^{2} = 64\): equal.
(C) \(50_{16} = 5 \times 16 = 80\): not equal.
(D) \(121_7 = 1 \times 7^{2} + 2 \times 7 + 1 = 49 + 14 + 1 = 64\): equal.

So three of the four numerals name the same value, 64; only the hexadecimal one differs.

Answer: A, B, D

Question 50

MSQ · 2 marks

Consider 4-variable functions \(f1, f2, f3, f4\) expressed in sum-of-minterms form as given below.

\(f1 = \sum(0,2,3,5,7,8,11,13)\)
\(f2 = \sum(1,3,5,7,11,13,15)\)
\(f3 = \sum(0,1,4,11)\)
\(f4 = \sum(0,2,6,13)\)

Logic circuit: inputs f1 and f2 enter an AND gate, inputs f3 and f4 enter an OR gate, and the outputs of the AND gate and the OR gate are the two inputs of an XOR gate whose output is Y.

With respect to the circuit given above, which of the following options is/are CORRECT?

\(\boldsymbol{Y} = \sum(0,1,2,11,13)\) \(\boldsymbol{Y} = \Pi(3,4,5,6,7,8,9,10,12,14,15)\) \(\boldsymbol{Y} = \sum(0,1,2,3,4,5,6,7)\) \(\boldsymbol{Y} = \Pi(8,9,10,11,12,13,14,15)\)

Explanation

Answer: (C), (D)

Work with minterm sets: AND keeps the minterms common to both inputs, OR takes their union, and XOR keeps the minterms that appear in exactly one input.

\(f1 \cdot f2\): common minterms \(\{3, 5, 7, 11, 13\}\).
\(f3 + f4\): \(\{0, 1, 2, 4, 6, 11, 13\}\).
XOR: 11 and 13 are in both sets and cancel, leaving \(\{0, 1, 2, 3, 4, 5, 6, 7\}\).

So \(Y = \sum(0,1,2,3,4,5,6,7)\), which is (C). Its maxterms are the remaining minterms 8 to 15, so (D) is the same function. Options (A) and (B) both describe \(\sum(0,1,2,11,13)\), which is not \(Y\).

Answer: C, D

Computer Science and Information Technology