GATE CS 2022 Set 1

The sentence tests the knowledge of homophones: fair and fare.In the context of the sentence:

• The first blank refers to a cost, so "**fare**" is the correct choice.
• The second blank refers to whether that cost is reasonable, so "**fair**" is the correct choice.

Sentence: "The fare is too high for it to be considered fair."

• Option (A) is incorrect as it reverses the words.
• Option (B) is incorrect because "faer" is not a standard English word.
• Option (C) is incorrect because the second blank requires an adjective, not the noun "fare".
• Option (D) is correct as it uses the noun "fare" for the cost and the adjective "fair" for the reasonableness.

The area under the curve $y(x)$ from $x=0$ to $x=1$ is given by the integral $\int_{0}^{1} y(x) dx$. Since the function is defined piecewise, we split the integral into three parts corresponding to the intervals:$$\text{Area} = \int_{0}^{1/3} 2 \, dx + \int_{1/3}^{3/4} 3 \, dx + \int_{3/4}^{1} 1 \, dx$$Calculating each part:Summing the areas:$$\text{Total Area} = \frac{2}{3} + \frac{5}{4} + \frac{1}{4} = \frac{2}{3} + \frac{6}{4} = \frac{2}{3} + \frac{3}{2}$$$$= \frac{4 + 9}{6} = \frac{13}{6}$$

Given that $r$ is a root of $x^2 + 2x + 6 = 0$, we have:$$r^2 + 2r + 6 = 0 \implies r^2 + 2r = -6$$We need to find the value of $(r + 2)(r + 3)(r + 4)(r + 5)$.
Rearranging the terms to group $(r+2)$ with $(r+5)$ and $(r+3)$ with $(r+4)$:$$E = [(r+2)(r+5)] \cdot [(r+3)(r+4)]$$$$E = [r^2 + 7r + 10] \cdot [r^2 + 7r + 12]$$We know $r^2 = -2r - 6$. Substituting this into the expressions:$$r^2 + 7r = (-2r - 6) + 7r = 5r - 6$$So,$$E = [(5r - 6) + 10] \cdot [(5r - 6) + 12]$$$$E = (5r + 4)(5r + 6)$$$$E = 25r^2 + 30r + 20r + 24$$$$E = 25r^2 + 50r + 24$$$$E = 25(r^2 + 2r) + 24$$Since $r^2 + 2r = -6$:$$E = 25(-6) + 24$$$$E = -150 + 24$$$$E = -126$$

We analyze the statements using the Square of Opposition in logic:

• Statement 1 (A): All students are inquisitive.
• Statement 2 (I): Some students are inquisitive.
• Statement 3 (E): No student is inquisitive.
• Statement 4 (O): Some students are not inquisitive.

Analysis of pairs:

• Statement 1 and Statement 3: These are contrary statements. If "All" is true, "None" must be false. If "None" is true, "All" must be false. They cannot both be true at the same time (though both can be false). Thus, they cannot be true simultaneously.
• Statement 1 and Statement 2: If "All" is true, "Some" is necessarily true (subalternation). They can be true simultaneously.
• Statement 2 and Statement 4: "Some are" and "Some are not" are sub-contraries. They can both be true simultaneously (e.g., if the class is mixed).
• Statement 3 and Statement 4: If "No student is inquisitive" is true, then it implies "Some students are not inquisitive". They can be true simultaneously.

Therefore, Statement 1 and Statement 3 cannot be true simultaneously.

The player starts with letters A and D.
To form a 5-letter palindrome, the set of 5 letters must consist of two pairs of matching letters and one central letter (e.g., $X Y Z Y X$).Let's analyze the options (allowing for rotation):

• Option (A): Contains D, O/Q, J. Total set: {A, D, D, O, J}. We have a pair of Ds, but A, O, J are singles. Cannot form a palindrome.
• Option (B): Contains R, an inverted 'A' (which becomes A when rotated), and a rotated 'R' (which becomes R). Total set: {A, D, R, A, R}. This gives us two As, two Rs, and one D. We can arrange these as R A D A R, which is a palindrome.
• Option (C): Contains Z, 3, D. Total set: {A, D, Z, 3, D}. Pair of Ds, but A, Z, 3 are singles. Cannot form a palindrome.
• Option (D): Contains I, 7, Y. Total set: {A, D, I, 7, Y}. All singles. Cannot form a palindrome.

Thus, Option (B) is the correct choice.

The passage states: "In organizations with good work culture, metrics help improve outcomes."Let's evaluate the options:

• (A) The passage says metrics are "counterproductive" in poor work culture, so they are not useful. Incorrect.
• (B) Since metrics "help improve outcomes" in good work culture, it is logically valid to infer they are "useful". Correct.
• (C) Contradicts the passage which says they improve outcomes in good culture. Incorrect.
• (D) Contradicts the passage. Incorrect.

Let $N_{appeared}$ be the total number of candidates who appeared, and $N_{qualified}$ be the total number of candidates who qualified.From the given information:Analyzing the options:
(A) $B_Q = G_Q \implies 0.40 N_{qualified} = 0.60 N_{qualified}$, which is false.
(B) $B_A = G_A \implies 0.65 N_{appeared} = 0.35 N_{appeared}$, which is false.
(C) $B_A < G_A \implies 0.65 N_{appeared} < 0.35 N_{appeared}$, which is false.
(D) $B_Q < G_Q \implies 0.40 N_{qualified} < 0.60 N_{qualified}$, which is true.Thus, the number of boys who qualified is less than the number of girls who qualified.

Let $G$ denote drawing a green ball and $O$ denote drawing an orange ball.
Initial state: 3 Green, 2 Orange. Total = 5.Case 1: First ball is Green ($G_1$).
Probability $P(G_1) = \frac{3}{5}$.
Since green is not replaced, the box now has 2 Green, 2 Orange. Total = 4.
Probability of drawing Orange next ($O_2|G_1$) = $\frac{2}{4} = \frac{1}{2}$.Case 2: First ball is Orange ($O_1$).
Probability $P(O_1) = \frac{2}{5}$.
Since orange is replaced with another orange ball, the composition remains 3 Green, 2 Orange. Total = 5.
Probability of drawing Orange next ($O_2|O_1$) = $\frac{2}{5}$.Total Probability of $O_2$:
$P(O_2) = P(G_1) \times P(O_2|G_1) + P(O_1) \times P(O_2|O_1)$
$P(O_2) = \left(\frac{3}{5} \times \frac{1}{2}\right) + \left(\frac{2}{5} \times \frac{2}{5}\right)$
$P(O_2) = \frac{3}{10} + \frac{4}{25}$
$P(O_2) = \frac{15}{50} + \frac{8}{50} = \frac{23}{50}$

Let's analyze the geometry and statements: In a triangle, a line segment is parallel to another only if one connects two midpoints and the other connects the two corners of the third side (Midpoint Theorem). Thus, one pair (e.g., P, R) are corners and the other pair (Q, S) are midpoints, or vice versa.

• If P were a midpoint, for PR to be parallel to QS, P and R would likely be midpoints of the sides adjacent to a vertex, and QS would be the base. However, if P is on the side opposite to T, and T is a corner, P lies on the base. This suggests P is a corner on the base line.
• Let's assume P and R are the corners of the base. Then the line PR is the base side.
• For QS to be parallel to PR, Q and S must be the midpoints of the other two sides.
• In this configuration: P and R are corners. Q and S are midpoints.
• T must be the third corner (opposite to side PR). This satisfies "P is placed on the side opposite to the corner T" (since P is an endpoint of that side).

3. "S and U cannot be placed on the same side."

• We have corners: P, R, T. Midpoints: Q, S, U.
• Q and S are midpoints of sides TP and TR (or vice versa).
• U is the midpoint of the base PR.
• S is on side TR (or TP). U is on side PR. They are on different sides. This satisfies the condition.

Verification of the alternative case:

• Suppose Q and S are corners (base QS) and P, R are midpoints.
• Then P is a midpoint on a side adjacent to the top vertex.
• Statement 2 says P is on the side opposite to corner T. If P is a midpoint, T must be the opposite vertex. But in this setup, the vertex opposite to P's side is one of the base corners (Q or S). So T would be Q or S.
• Statement 3 says S and U cannot be on the same side. If T=S, then S is a corner. U would be the midpoint of the base QS. Thus S and U would both be on the side QS. This contradicts Statement 3.

Conclusion:

• The valid configuration is: P and R are corners; Q and S are midpoints.
• Since S is a midpoint, it cannot be placed at a corner.
• Therefore, statement (B) is correct.

The problem asks for the minimum number of additional straight ropes to divide the land into four plots of similar shape. The existing shape is a square with a corner removed (an L-shape) formed by a $4 \times 4$ grid of dots. The existing ropes R1 and R2 partially divide the area.To divide an L-shaped region into 4 smaller similar L-shaped regions, we typically need to add lines that partition the central area and extend to the boundaries. By adding 3 additional ropes, we can complete the division into 4 identical smaller L-shapes.

Let's analyze the options:(A) If $f(n)$ is a polynomial, let $f(n) = c n^k$ for some constants $c > 0, k \ge 0$.
Then $f(n^2) = c (n^2)^k = c n^{2k}$.
And $(f(n))^2 = (c n^k)^2 = c^2 n^{2k}$.
Since $c n^{2k} = \frac{1}{c} (c^2 n^{2k})$, $f(n^2) = \Theta(f(n)^2)$. This statement is TRUE.(C) If $f(n)$ is an exponential function, let $f(n) = 2^n$.
Then $f(n^2) = 2^{n^2}$.
And $(f(n))^2 = (2^n)^2 = 2^{2n}$.
Since $2^{n^2}$ grows much faster than $2^{2n}$, $f(n^2) \neq O(f(n)^2)$. This statement is FALSE.(B) and (D) are not true for all positive functions (counterexamples can be found using the functions above).

The finite automaton (NFA) has the following structure:

• Start state $S$.
• Transition $S \xrightarrow{a} Q_1$ (where $Q_1$ is an accepting state).
• Transition $S \xrightarrow{b} Q_2$ (where $Q_2$ is an accepting state).
• From $Q_1$: Self-loop $b$, and transition $b$ back to $S$. This creates a loop $S \xrightarrow{a} Q_1 \xrightarrow{b^*} Q_1 \xrightarrow{b} S$, represented by $ab^*b$.
• From $Q_2$: Self-loop $a$, and transition $a$ back to $S$. This creates a loop $S \xrightarrow{b} Q_2 \xrightarrow{a^*} Q_2 \xrightarrow{a} S$, represented by $ba^*a$.

The machine can loop on the start state any number of times using these paths: $(ab^*b + ba^*a)^*$.
Finally, to accept, it must transition to $Q_1$ (path $ab^*$) or $Q_2$ (path $ba^*$).Combining these, the regular expression is: $(ba^*a + ab^*b)^*(ab^* + ba^*)$.

Option (D) is correct. $LR(1)$ parsers are capable of parsing all Deterministic Context-Free Languages (DCFLs).Option (A) is incorrect. The construction of an $LALR(1)$ parser involves merging states from the $LR(1)$ automaton that have the same core items. This merging process can introduce Reduce-Reduce conflicts (but not Shift-Reduce conflicts), even if the original $LR(1)$ parser was conflict-free.Option (B) is incorrect. The symbol table is a data structure used throughout the compilation process, including syntax analysis, semantic analysis, and code generation, not just lexical analysis.Option (C) is incorrect. Data flow analysis is a technique used primarily for code optimization (e.g., constant propagation, liveness analysis), not for run-time memory management.

Option (A) is correct. Consider a relation $R$ with two attributes, say $A$ and $B$. The possible non-trivial functional dependencies are A → B, B → A, or both. In any of these cases, the determinant (left-hand side) is a superkey, which satisfies the condition for Boyce-Codd Normal Form (BCNF). If there are no non-trivial dependencies, the only superkey is $AB$, and the relation is trivially in BCNF.Option (B) is incorrect. A relation where all attributes are prime is always in 3NF, but not necessarily in BCNF. For example, R(A, B, C) with dependencies AB → C and C → B has keys $AB$ and $AC$. All attributes are prime, but C → B violates BCNF because $C$ is not a superkey.Option (C) is incorrect. A relation can be composed entirely of prime attributes (e.g., the example in B).Option (D) is incorrect. Decomposition into BCNF is lossless but not always dependency preserving.

Option (A) is correct. A singly linked list can be reversed in place using an iterative algorithm that maintains three pointers: prev, current, and next. This approach iterates through the list once, reversing the next pointer of each node to point to the prev node. This process requires $O(1)$ auxiliary space and takes $\theta(n)$ time, where $n$ is the number of nodes in the list.

Let $n$ be the total number of keys and $m$ be the number of slots.
Let $n_{odd}$ be the number of odd keys and $n_{even}$ be the number of even keys, such that $n = n_{odd} + n_{even}$.For any specific slot $j$:
The probability that a specific odd key hashes to slot $j$ using $h_1$ is $\frac{1}{m}$ (simple uniform hashing).
The expected number of odd keys in slot $j$ is $E[X_{odd}] = n_{odd} \times \frac{1}{m}$.The probability that a specific even key hashes to slot $j$ using $h_2$ is $\frac{1}{m}$ (simple uniform hashing).
The expected number of even keys in slot $j$ is $E[X_{even}] = n_{even} \times \frac{1}{m}$.The total expected number of keys in slot $j$ is:
$E[X] = E[X_{odd}] + E[X_{even}] = \frac{n_{odd}}{m} + \frac{n_{even}}{m} = \frac{n_{odd} + n_{even}}{m} = \frac{n}{m}$.

DMA (Direct Memory Access) allows the I/O device to transfer data directly to/from main memory without the continuous intervention of the CPU. This is much faster for bulk data transfers compared to Programmed I/O (polling) or Interrupt-driven I/O, where the CPU is involved in moving each word or byte.

In 4-bit 2's complement representation, the range of values is $-8$ to $+7$.
Overflow occurs when adding two numbers of the same sign results in a number of the opposite sign.(A) $1011 (-5) + 1110 (-2) = 11001$. Discard carry $\rightarrow 1001 (-7)$. Correct.
(B) $1100 (-4) + 1010 (-6) = 10110$. Discard carry $\rightarrow 0110 (+6)$. Incorrect. Negative + Negative = Positive implies Overflow.
(C) $0011 (+3) + 0100 (+4) = 0111 (+7)$. Correct.
(D) $1001 (-7) + 1111 (-1) = 11000$. Discard carry $\rightarrow 1000 (-8)$. Correct.

To print the sequence BCABCABCA..., the order of execution must be $T_2 \rightarrow T_1 \rightarrow T_3 \rightarrow T_2 \dots$Thus, the initial values must be $S_1 = 1, S_2 = 0, S_3 = 0$.

The trace of a product of two matrices $X$ and $Y$ satisfies $tr(XY) = tr(YX)$ provided that both products $XY$ and $YX$ are square matrices.

• In Statement 1, $A$ is $m \times n$ and $B$ is $n \times m$. Thus $AB$ is $m \times m$ and $BA$ is $n \times n$. Both are square, so $tr(AB) = tr(BA)$ is a standard identity.
• In Statement 2, $C$ and $D$ are both $n \times n$. Thus $CD$ and $DC$ are both $n \times n$. Both are square, so $tr(CD) = tr(DC)$ is also a standard identity.

Therefore, both statements are correct.

Let's trace the program execution:

• &z[0] is the address of the first element of array $z$.
• &z[0] + 1 is the address of the second element, which is &z[1].
• *(&z[0] + 1) is the value at that address, which is $z[1]$.
• z[1] += 3; updates $z[1]$ from 11 to $11 + 3 = 14$.

6. printf("%d, %d, %d\n", x, z[0], z[1]); prints the current values: $x=10, z[0]=10, z[1]=14$.
Thus, the output is 10, 10, 14.

A subnet is required for each segment of the network that is not further subdivided. In a router-based network, each interface of a router connects to a different subnet.
Let's identify the distinct network segments in the given diagram:Counting these up, we have a total of 6 subnets inside the enterprise network.Therefore, the correct answer is 6.

Statement (A) is FALSE. Consider $\Sigma^*$, which is a regular language and thus recursively enumerable. Any undecidable language is a subset of $\Sigma^*$. Therefore, a subset of a recursively enumerable language is not necessarily recursive.Statement (B) is TRUE. This is a standard theorem: A language $L$ is recursive (decidable) if and only if both $L$ and its complement $\overline{L}$ are recursively enumerable.Statement (C) is TRUE. Every context-free language (CFL) is recursive (decidable). The class of recursive languages is closed under complementation. Therefore, the complement of a CFL is recursive.Statement (D) is TRUE. The class of regular languages is closed under intersection. Thus, $L_1 \cap L_2$ is regular. Since every regular language is a deterministic context-free language (DCFL), $L_1 \cap L_2$ must be deterministic context-free.

The question asks for the FALSE statements.(A) Each cache block in WB and WT has a dirty bit.
A dirty bit is required for a write-back (WB) cache to track whether a block has been modified. This is necessary to know if the block needs to be written back to main memory upon eviction. However, in a write-through (WT) cache, every write is immediately propagated to main memory, so the cache and memory are always consistent. Thus, a WT cache does not need a dirty bit. Since the statement claims that WT also has a dirty bit, the statement is FALSE.(B) Every write hit in WB leads to a data transfer from cache to main memory.
This describes a write-through policy. In a write-back (WB) cache, on a write hit, only the cache block is updated, and its dirty bit is set. The data is written to main memory only when the dirty block is evicted. Therefore, the statement is FALSE.(C) Eviction of a block from WT will not lead to data transfer from cache to main memory.
In a write-through (WT) cache, main memory is updated on every write operation. This ensures that the main memory always holds the most recent version of the data. Consequently, when a block is evicted from the cache, there is no need to write it back to memory. The statement is TRUE.(D) A read miss in WB will never lead to eviction of a dirty block from WB.
A read miss requires fetching a new block from memory. If the target cache set is full, a block must be evicted based on the LRU policy. The block chosen for eviction could be clean or dirty. If the LRU block happens to be dirty, it must be evicted (and written back to memory) to make space for the new block. The statement claims this will never happen, which is incorrect. Therefore, the statement is FALSE.The false statements are A, B, and D.

The query asks for the division operation $Own \div \Pi_{bId}(Brand)$. $$\Pi_{eId}(Own) - \Pi_{eId}((\Pi_{eId}(Own) \times \Pi_{bId}(Brand)) - \Pi_{eId, bId}(Own))$$ This logic finds all potential (eId, bId) pairs, subtracts actual owned pairs to find missing pairs, projects to find eIds with missing brands, and subtracts those from the set of all eIds. This is the standard definition of division. This is correct.

To find the $k$-th largest element in a Binary Search Tree (BST), we perform a reverse in-order traversal (Right, Root, Left). Since the tree is also a Complete Binary Tree (CBT) stored in an array, the structure is fixed.Array Indexing Properties:
For a node at index $i$:

• Left Child: $2i + 1$
• Right Child: $2i + 2$
• Parent: $\lfloor \frac{i-1}{2} \rfloor$
• Total nodes $N = 1000$ (indices $0$ to $999$).

Step 1: Find the 1st Largest Element
The largest element in a BST is the rightmost node. We start at the root ($0$) and keep moving to the right child as long as the index is within bounds ($< 1000$).

• $0 \xrightarrow{R} 2 \xrightarrow{R} 6 \xrightarrow{R} 14 \xrightarrow{R} 30 \xrightarrow{R} 62 \xrightarrow{R} 126 \xrightarrow{R} 254 \xrightarrow{R} 510$
• Next right child: $2(510) + 2 = 1022 > 999$. Node $510$ has no right child.
• Does node $510$ have a left child? $2(510) + 1 = 1021 > 999$. No.
• Thus, index 510 is the largest element.

Step 2: Find the 2nd Largest Element
Since node $510$ is a leaf (no left child), the next largest element is its parent (since $510$ was a right child).

• Parent of $510$: $\lfloor \frac{510-1}{2} \rfloor = 254$.
• Thus, index 254 is the 2nd largest element.

Step 3: Find the 3rd Largest Element
After visiting $254$, we must explore its left subtree to find the next largest values. The largest value in the left subtree is the rightmost node of that subtree.

• Left child of $254$: $2(254) + 1 = 509$.
• Does node $509$ have a right child? $2(509) + 2 = 1020 > 999$. No.
• Since node $509$ has no right child, it is the largest element in the left subtree of $254$.
• Thus, index 509 is the 3rd largest element.

Conclusion:
The 3rd largest element is stored at index 509.