GATE CS 2019 Set 1

The subject of the sentence is "The expenditure", which is singular. Therefore, the verb must also be singular. The phrasal verb "breaks down" is used to describe the act of separating something into its component parts or categories. Thus, "breaks down" is the grammatically correct choice.

The idiomatic expression "revolves around" means to have something as a main subject or interest. In this context, it signifies that the business model is centered on the concept of trust.

Step 1: Calculate the relative speed of the two cars. Since they are moving in the same direction, the relative speed is the difference between their individual speeds.
Relative Speed = $60\text{ km/h} - 50\text{ km/h} = 10\text{ km/h}$.Step 2: Use the formula for time, which is distance divided by speed.
Time = $\frac{\text{Distance}}{\text{Relative Speed}} = \frac{20\text{ km}}{10\text{ km/h}} = 2\text{ hours}$.Therefore, it takes 2 hours for the distance between them to be 20 km.

Let the total cost of the gift be $C$.
Initially, 10 friends planned to share the cost equally. So, the share of each friend was $\frac{C}{10}$.When 2 friends decided not to contribute, the number of friends contributing became $10 - 2 = 8$.
The new share of each friend became $\frac{C}{8}$.According to the problem, the new share is Rs. 150 more than the original share.
So, $\frac{C}{8} - \frac{C}{10} = 150$$\Rightarrow C \left( \frac{1}{8} - \frac{1}{10} \right) = 150$$\Rightarrow C \left( \frac{5 - 4}{40} \right) = 150$$\Rightarrow C \left( \frac{1}{40} \right) = 150$$\Rightarrow C = 150 \times 40 = 6000$The cost of the gift was Rs. 6000.

This is an analogy question based on the relationship between a professional and their workplace.
A judge works in a court.
Similarly, a teacher works in a school.Therefore, the correct word to complete the analogy is 'a school'.

Let's analyze the statements assuming each person is the criminal one by one. We are given that only one person committed the crime and only one statement is true.Statements:Case 1: P committed the crime.

• P's statement (Q did it) is False.
• Q's statement (S did it) is False.
• R's statement (I didn't do it) is True.
• S's statement (S didn't do it) is True.

Result: Two true statements (R and S). Violates the condition.Case 2: Q committed the crime.

• P's statement (Q did it) is True.
• Q's statement (S did it) is False.
• R's statement (I didn't do it) is True.
• S's statement (S didn't do it) is True.

Result: Three true statements (P, R, S). Violates the condition.Case 3: R committed the crime.

• P's statement (Q did it) is False.
• Q's statement (S did it) is False.
• R's statement (I didn't do it) is False (since R did it).
• S's statement (S didn't do it) is True.

Result: Only one true statement (S). This satisfies the condition.Case 4: S committed the crime.

• P's statement (Q did it) is False.
• Q's statement (S did it) is True.
• R's statement (I didn't do it) is True.
• S's statement (S didn't do it) is False.

Result: Two true statements (Q and R). Violates the condition.Therefore, R committed the crime.

Sum all the numbers in the diagram: $70 + 10 + 20 + 20 + 40 = 160$. Administrators are represented by the rectangle. The numbers inside the rectangle are $10, 20, \text{ and } 20$.
Total administrators = $10 + 20 + 20 = 50$. Percentage = $\left( \frac{\text{Number of administrators}}{\text{Total number of people}} \right) \times 100$
Percentage = $\left( \frac{50}{160} \right) \times 100 = \frac{5}{16} \times 100 = 31.25\%$. $31.25\%$ falls within the range of 31 to 45.

The passage states that begging should be regarded as a "symptom" rather than a disease. It explicitly identifies the "underlying disease" as the "failure of the state to protect citizens who fall through the social security net." This implies that the lack of a social security net (social welfare schemes) is the root cause of begging. Therefore, statement (B) is the correct inference.

Let $A$ be the Drama club, $B$ be the Dance club, and $C$ be the Maths club.Given:

• $n(\text{only } A) = 60$
• $n(\text{only } B) = 80$
• $n(\text{only } C) = 30$
• $n(A \cap B) = 40$
• $n(B \cap C) = 12$
• $n(A \cap C) = 7$
• $n(A \cap B \cap C) = 2$

To find the number of students in at least one club, we use the formula for the union of three sets:
$n(A \cup B \cup C) = \sum n(\text{only one}) + \sum n(\text{only two}) + n(\text{all three})$Calculate students in exactly two clubs:

• $n(\text{only } A \cap B) = n(A \cap B) - n(A \cap B \cap C) = 40 - 2 = 38$
• $n(\text{only } B \cap C) = n(B \cap C) - n(A \cap B \cap C) = 12 - 2 = 10$
• $n(\text{only } A \cap C) = n(A \cap C) - n(A \cap B \cap C) = 7 - 2 = 5$

Total students in clubs:
$n(A \cup B \cup C) = (60 + 80 + 30) + (38 + 10 + 5) + 2 = 170 + 53 + 2 = 225$It is given that $75\%$ of students are not in any club. This means $25\%$ of the total students ($T$) are in at least one club.
$0.25 \times T = 225$
$T = \frac{225}{0.25} = 225 \times 4 = 900$The total number of students in the college is 900.

• The compass shows North (N) is up, East (E) is right, South (S) is down, West (W) is left.
• WR (Washroom): Located in the top-left corner (North-West).
• Garden: Located along the right edge (East).

2. Analyze the Requests:

• Request by X: "Avoid a wing next to the garden." Since the garden is on the East, X cannot be in the East wing.
• Request by Y: "Live as far from the washrooms as possible." WR is in the NW corner. The farthest point diagonally is the South-East (SE) corner.
• Request by Z: "Stay in the South-west wing." Z must be in the SW corner.

3. Evaluate the Options:

• (A) Z is in the West wing, not SW. Y is in the South wing, not SE. Incorrect.
• (B) X is in the East wing (next to the garden). Violates X's request. Incorrect.
• (C) Z is in the North-West wing. Violates Z's request. Incorrect.
• (D)
• Z is in the South-West (SW) corner. (Satisfied)
• Y is in the South-East (SE) corner, which is farthest from the NW washroom. (Satisfied)
• X is in the South wing. This is not the East wing (next to the garden). (Satisfied)

Therefore, option (D) is the correct allocation.

Given:

• Cache Size = 16 kB = $2^{14}$ bytes
• Block Size = 16 bytes = $2^4$ bytes
• Main Memory Address = 32 bits
• Mapping: Fully Associative

In Fully Associative mapping, the physical address is divided into two fields: Tag and Block Offset.
Since any block from main memory can be placed in any line of the cache, there is no need for a set index. Thus, the Index field is 0 bits.Block Offset:
Determined by the block size.
$\text{Block Offset bits} = \log_2(\text{Block Size}) = \log_2(16) = 4$ bits.Tag:
The remaining bits of the address are used for the Tag.
$\text{Tag bits} = \text{Total Address bits} - \text{Block Offset bits}$
$\text{Tag bits} = 32 - 4 = 28$ bits.So, Tag = 28 bits, Index = 0 bits.

The Chip Select (CS) signal is generated by a logic gate (AND gate) taking inputs from address lines $A_{15}$ through $A_{11}$. For the chip to be enabled, CS must be active (High/1).Based on the diagram:

• $A_{15}$ is connected directly $\rightarrow$ must be 1.
• $A_{14}$ is connected directly $\rightarrow$ must be 1.
• $A_{13}$ has a bubble (inverter) $\rightarrow$ must be 0.
• $A_{12}$ has a bubble (inverter) $\rightarrow$ must be 0.
• $A_{11}$ is connected directly $\rightarrow$ must be 1.

So, the prefix of the address ($A_{15} \dots A_{11}$) is fixed as $11001$.The remaining address lines $A_{10} \dots A_0$ are not part of the selection logic and can vary from all 0s to all 1s.Binary Address:
Prefix: $1100\ 1$
Full 16-bit address: $1100\ 1xxx\ xxxx\ xxxx$Lower Bound (Min Address):
Set all $x$ to 0: $1100\ 1000\ 0000\ 0000_2$
Hex: $C\ 8\ 0\ 0 \rightarrow$ C800Upper Bound (Max Address):
Set all $x$ to 1: $1100\ 1111\ 1111\ 1111_2$
Hex: $C\ F\ F\ F \rightarrow$ CFFFThe range is C800 to CFFF.

LR parsers are Bottom-Up parsers.

• Top-Down parsers (like LL parsers) generate the string from the start symbol using Leftmost derivation.
• Bottom-Up parsers (like LR parsers) start from the input string and reduce it to the start symbol. This reduction process is the reverse of a derivation. Specifically, at each step, an LR parser reduces the handle, which corresponds to reversing a step in a Rightmost derivation.

Thus, LR parsers use Rightmost derivation in reverse.

To find the 16-bit 2's complement representation of $-28$: $28 = 16 + 8 + 4 = 11100_2$
In 16-bit: $0000\ 0000\ 0001\ 1100$ $1111\ 1111\ 1110\ 0011$ $1111\ 1111\ 1110\ 0011 + 1 = 1111\ 1111\ 1110\ 0100$This matches option (C).

We want to find the size of the set $A = \{(x, X) \mid x \in X, X \subseteq U\}$.Method 1 (Counting by element $x$):
For a fixed element $x \in U$ (there are $n$ choices for $x$), we need to choose a subset $X \subseteq U$ such that $x \in X$. This is equivalent to choosing any subset of $U \setminus \{x\}$. The number of such subsets is $2^{n-1}$.
Total count $|A| = n \times 2^{n-1}$.
Thus, Statement I is TRUE.Method 2 (Counting by subset size $k$):
Let $|X| = k$. The number of subsets of size $k$ is $\binom{n}{k}$. For each such subset, there are $k$ choices for $x$ (since $x \in X$).
Summing over all possible sizes $k$ from 1 to $n$:
$|A| = \sum_{k=1}^n k \binom{n}{k}$.
Thus, Statement II is TRUE.Since both statements are true, the correct option is (C).

Let's analyze each option:(A) $(x \oplus y) \oplus z = x \oplus (y \oplus z)$: This is the associative property of XOR. It is valid.(B) $(x + y) \oplus z = x \oplus (y + z)$: Let's test with values. Let $x=0, y=1, z=1$.
LHS: $(0+1) \oplus 1 = 1 \oplus 1 = 0$.
RHS: $0 \oplus (1+1) = 0 \oplus 1 = 1$.
Since $0 \neq 1$, this identity is NOT valid.(C) $x \oplus y = x + y$, if $xy = 0$: If $xy=0$, it means $x$ and $y$ are not both 1. The XOR operation is $x'y + xy'$. If $xy=0$, then $x+y$ behaves exactly like XOR (no carry/overlap). Valid.(D) $x \oplus y = (xy + x'y')'$: The expression $xy + x'y'$ represents XNOR ($x \odot y$). The complement of XNOR is XOR. Valid.The question asks for the one that is NOT a valid identity.
Answer: (B).

Regular languages are closed under concatenation, reversal, prefix, and suffix operations.Therefore, option (B) is NOT necessarily regular.

In $n$-bit sign-magnitude representation, 1 bit is for the sign and $n-1$ bits are for the magnitude.
The range of representable values is $[-(2^{n-1}-1), +(2^{n-1}-1)]$.Let the maximum positive value be $M = 2^{n-1}-1$.
The range is $[-M, M]$.We are computing $Z = X - Y$.
The maximum possible value of $Z$ occurs when $X$ is maximum positive and $Y$ is minimum negative:
$Z_{max} = M - (-M) = 2M = 2(2^{n-1}-1) = 2^n - 2$.The minimum possible value of $Z$ occurs when $X$ is minimum negative and $Y$ is maximum positive:
$Z_{min} = -M - M = -2M = -(2^n - 2)$.So, $Z$ requires a range of roughly $\pm 2^n$. To represent a magnitude of $2^n - 2$, we need $n$ bits for magnitude (since $2^n - 2 < 2^n - 1$). Adding 1 bit for the sign, we need a total of $n+1$ bits.Thus, $n+1$ bits are required to avoid overflow.

A fundamental property of square matrices is that a matrix $X$ is invertible (non-singular) if and only if its determinant is non-zero ($\det(X) \neq 0$).Therefore:

• If $X$ is invertible, then $\det(X) \neq 0$ (I implies II).
• If $\det(X) \neq 0$, then $X$ is invertible (II implies I).

Thus, statements I and II are equivalent.

$R_1$ is the conjugacy relation, which is a known equivalence relation. Proof:$R_2$ is defined by $a = b^{-1}$.Therefore, only $R_1$ is an equivalence relation.

Statement I is TRUE: Strict Two-Phase Locking (Strict 2PL) ensures that a transaction holds all its exclusive locks until it commits or aborts. This property guarantees that the schedule is strict (and thus recoverable and cascadeless). Since it follows 2PL, it also guarantees conflict serializability.Statement II is TRUE: Thomas' Write Rule is an optimization on the Timestamp Ordering protocol that ignores obsolete write operations (writes that arrive late). By ignoring these writes, it allows schedules that would otherwise be rejected by basic TO or conflict serializability checks. These schedules are view serializable but not necessarily conflict serializable.

For a complete graph $K_n$ with $n$ labeled vertices:The number of distinct Hamiltonian cycles is $\frac{(n-1)!}{2}$.

The given limit is of the form $\frac{0}{0}$ at $x=3$:
Numerator: $3^4 - 81 = 81 - 81 = 0$
Denominator: $2(3)^2 - 5(3) - 3 = 18 - 15 - 3 = 0$Using L'Hopital's Rule, we differentiate the numerator and denominator with respect to $x$:
$\lim_{x \to 3} \frac{\frac{d}{dx}(x^4 - 81)}{\frac{d}{dx}(2x^2 - 5x - 3)} = \lim_{x \to 3} \frac{4x^3}{4x - 5}$Substitute $x=3$:
$= \frac{4(3)^3}{4(3) - 5} = \frac{4(27)}{12 - 5} = \frac{108}{7}$

In a B+ tree:

The Pumping Lemma for regular languages states that there exists a constant $p$ (pumping length) such that any string $s \in L$ with $|s| \ge p$ can be split into $xyz$ satisfying specific conditions, primarily that $xy^iz \in L$ for all $i \ge 0$.The language $L$ consists of strings of 'a's with lengths in arithmetic progression $2, 5, 8, \dots$ (period 3) and strings of 'b's with lengths $10, 22, 34, \dots$ (period 12).If we choose a pumping length $p$, it must be sufficient to pump any string in $L$ of length $\ge p$.
Consider the string $b^{10}$. It is in $L$. If $p=9$, we must be able to pump $b^{10}$. Since the string consists only of 'b's, the pumped part $y$ must consist of 'b's. The lengths of 'b' strings in $L$ are separated by 12. Thus, $|y|$ must be a multiple of 12 to stay in $L$. However, the condition $|xy| \le p$ implies $|y| \le 9$. There is no multiple of 12 in the range $[1, 9]$. Thus, 9 cannot be a pumping length. Similarly, 3 and 5 are too small.If $p=24$, any string in $L$ with length $\ge 24$ will have length $\ge$ the period of its respective component (3 for 'a', 12 for 'b'). Specifically, the number of states in the minimal DFA for $L$ would be roughly $3 + 12 + 2 = 17$ (approx). Since $24 \ge$ number of states, it is a valid pumping length.

SMTP (Simple Mail Transfer Protocol) is used for sending emails (push protocol). POP3 (Post Office Protocol version 3) or IMAP (Internet Message Access Protocol) are used for retrieving emails (pull protocols).Therefore, the correct pair for sending and retrieving is SMTP and POP3.

The loop runs for $i = 0$ to $9$ (10 iterations).
The condition if (i%2 == 0) is true for even values of $i$: $0, 2, 4, 6, 8$. This means fork() is called 5 times.The number of child processes created by $n$ fork() calls is $2^n - 1$.
Here, $n = 5$.
Total child processes = $2^5 - 1 = 32 - 1 = 31$.

Let's trace the execution:

• Inside jumble(5, 2): parameter x gets 5, y gets 2.
• x = 2*5 + 2 = 12.
• Returns 12.
• Back in main, y becomes 12. x is still 2.

3. x = jumble(y, x); calls jumble(12, 2).

• Inside jumble(12, 2): parameter x gets 12, y gets 2.
• x = 2*12 + 2 = 26.
• Returns 26.
• Back in main, x becomes 26.

4. printf("%d \n", x); prints 26.

Given grammar:
$S \to Aa$
A → BD
$B \to b \mid \epsilon$
$D \to d \mid \epsilon$We need to find $FOLLOW(B)$. $FIRST(D) = \{d, \epsilon\}$.
So, $d \in FOLLOW(B)$. So, $a \in FOLLOW(A) \implies a \in FOLLOW(B)$.Thus, $FOLLOW(B) = \{a, d\}$.Using the given indices:
$a \to 3$
$d \to 1$The indices in descending order are 3, 1.
Concatenating them gives 31.

In the QuickSort algorithm, the worst-case partitioning occurs when the pivot element divides the array into a subarray of size 0 and a subarray of size $n-1$. This happens when the pivot is either the smallest element or the largest element in the current subarray.Total number of elements $n = 25$.
The pivot is chosen uniformly at random from the 25 elements.
Total possible choices for pivot = 25.The "worst possible locations" correspond to the pivot being the smallest (rank 1) or the largest (rank 25) element.
Number of favorable outcomes (worst cases) = 2.Probability = $\frac{\text{Number of worst case pivots}}{\text{Total number of pivots}} = \frac{2}{25} = 0.08$.

We need to compute $3^{51} \pmod 5$.Using Fermat's Little Theorem, since 5 is prime and 3 is not divisible by 5:
$3^{5-1} \equiv 1 \pmod 5$
$3^4 \equiv 1 \pmod 5$Now, express the exponent 51 in terms of 4:
$51 = 4 \times 12 + 3$So,
$3^{51} = 3^{4 \times 12 + 3} = (3^4)^{12} \times 3^3$Substitute $3^4 \equiv 1 \pmod 5$:
$3^{51} \equiv (1)^{12} \times 3^3 \pmod 5$
$3^{51} \equiv 1 \times 27 \pmod 5$
$3^{51} \equiv 27 \pmod 5$Since $27 = 5 \times 5 + 2$:
$27 \equiv 2 \pmod 5$Thus, the value is 2.

To find the probability that two independently and uniformly chosen numbers from the set $S = \{1, 2, \dots, 13\}$ have the same most significant bit (MSB) in their 4-bit unsigned binary representation, we analyze the binary representations of the elements in $S$.

Step 1: Determine the MSB of each number in the set

The numbers in the set $S = \{1, 2, \dots, 13\}$ can be represented as 4-bit unsigned binary numbers (from 0000 to 1111):

• Numbers with MSB = 0:

These are the numbers in the range $[1, 7]$, which in 4-bit binary are:

• $1 = 0001_2$
• $2 = 0010_2$
• $3 = 0011_2$
• $4 = 0100_2$
• $5 = 0101_2$
• $6 = 0110_2$
• $7 = 0111_2$

There are $n_0 = 7$ such numbers.

• Numbers with MSB = 1:

These are the numbers in the range $[8, 13]$, which in 4-bit binary are:

• $8 = 1000_2$
• $9 = 1001_2$
• $10 = 1010_2$
• $11 = 1011_2$
• $12 = 1100_2$
• $13 = 1101_2$

There are $n_1 = 6$ such numbers.The total number of elements in the set is $N = 13$.---

Step 2: Calculate the probability

Two numbers, say $X$ and $Y$, are chosen independently and uniformly at random from $S$. The probability that both numbers have MSB = 0 is:$$P(\text{both MSB } 0) = \left(\frac{n_0}{N}\right) \times \left(\frac{n_0}{N}\right) = \left(\frac{7}{13}\right)^2 = \frac{49}{169}$$The probability that both numbers have MSB = 1 is:$$P(\text{both MSB } 1) = \left(\frac{n_1}{N}\right) \times \left(\frac{n_1}{N}\right) = \left(\frac{6}{13}\right)^2 = \frac{36}{169}$$Since these two events are mutually exclusive, the total probability $P$ that both numbers have the same MSB is:$$P = P(\text{both MSB } 0) + P(\text{both MSB } 1)$$$$P = \frac{49}{169} + \frac{36}{169} = \frac{85}{169}$$---

Step 3: Convert to decimal representation

Performing the division:$$P = \frac{85}{169} \approx 0.502958...$$Rounding off to 3 decimal places, we get:$$P \approx 0.503$$