GATE CS 2017 Set 1

The sentence describes a sequence of events that happened in the past. The first event, 'Rajendra Chola returned', is in the simple past tense. The action of wishing to visit the temple happened after his return.Let's analyze the options:

• (A) 'was wishing' (past continuous) is used for an ongoing action in the past. It doesn't fit the context of a single desire or decision that followed an event.
• (B) 'is wishing' (present continuous) is incorrect because the entire context is in the past.
• (C) 'wished' (simple past) correctly indicates a completed action or state that occurred in the past, following the action of returning.
• (D) 'had wished' (past perfect) would imply that the wish occurred before he returned, which contradicts the logical flow suggested by 'After...'.

Therefore, the simple past tense 'wished' is the most appropriate choice to maintain the chronological sequence of past events.

This question tests the difference between the words 'beside' and 'besides'.

• Beside is a preposition that means 'next to' or 'at the side of'. For example, "He sat beside the driver."
• Besides is a preposition or an adverb that means 'in addition to' or 'apart from'. For example, "What other languages do you know besides Spanish?"

The sentence implies that people work for many reasons in addition to money. Therefore, 'besides' is the correct word.Let's look at the options:

• (A) money beside: Incorrect word order and wrong word.
• (B) beside money: This would mean 'next to money', which is semantically incorrect in this context.
• (C) money besides: Incorrect word order.
• (D) besides money: This means 'in addition to money', which fits the context perfectly.

Thus, the correct option is (D).

Let the positions around the square table be 1, 2, 3, 4 in clockwise order.

• If Murali is at position 1, Rahul is at position 2 (assuming facing the center, left is clockwise).
• Sequence: Murali $\rightarrow$ Rahul.

2. Srinivas is sitting to the right of Arul.

• Right is anti-clockwise. If Arul is at position $X$, Srinivas is at position $X-1$.
• In clockwise terms, this means Arul is to the left of Srinivas, or Srinivas $\rightarrow$ Arul.

Combining these, we have two blocks: (Murali, Rahul) and (Srinivas, Arul) in clockwise order. Placing them around the table:

• Position 1: Murali
• Position 2: Rahul
• Position 3: Srinivas
• Position 4: Arul

Check conditions:

• Rahul (2) is left of Murali (1)? Yes.
• Srinivas (3) is right of Arul (4)? Yes (4's right is 3).

Opposite pairs are (1, 3) and (2, 4):

• Murali and Srinivas are opposite.
• Rahul and Arul are opposite.

Option (C) matches Srinivas and Murali.

First, find the prime factorization of 162:$$162 = 2 \times 81 = 2 \times 3^4$$For a number to be a perfect cube, the exponent of every prime factor in its factorization must be a multiple of 3.
Currently, we have:

• $2^1$ (needs 2 more to become $2^3$)
• $3^4$ (needs 2 more to become $3^6$, the next multiple of 3)

The smallest number $y$ must supply these missing factors:$$y = 2^2 \times 3^2$$$$y = 4 \times 9$$$$y = 36$$Verification: $162 \times 36 = 5832 = 18^3$.

The set of all possible digits is $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, which has 10 digits.
The digits to be excluded are $\{0, 5, 9\}$.
The allowed digits are $\{1, 2, 3, 4, 6, 7, 8\}$, which is a set of 7 digits.Assuming each digit position is independent and can be any of the 10 digits with equal probability (ignoring the leading zero constraint for 'number' vs 'string' distinction based on the options provided):The probability of choosing an allowed digit for one position is:$$P(\text{valid digit}) = \frac{\text{Number of allowed digits}}{\text{Total digits}} = \frac{7}{10} = 0.7$$For a $k$-digit number, since the choice for each position is independent:$$P(\text{valid } k\text{-digit number}) = (0.7) \times (0.7) \times \dots \times (0.7) \quad (k \text{ times})$$$$P = 0.7^k$$

The author states that the "nationalist imagination" has such a strong hold on the colonial past that anything not fitting the nationalist narrative ("inadequately or improperly nationalist") is dismissed as "not history". This implies that the perception of history is heavily biased or filtered by nationalism. Therefore, option (B) "History is viewed through the filter of nationalism" best reflects the author's opinion.

Let $n_W$ be the number of women and $n_M$ be the number of men. Total people = 6.
Given constraints:From constraint 4, all women are left-handed. Since $n_{RH} \ge 3$, and women cannot be right-handed, all right-handed people must be men. Therefore, $n_M \ge 3$.Since $n_W + n_M = 6$ and $n_W \ge 2$, the possible values for $n_W$ are 2, 3, or 4. However, since $n_M \ge 3$, $n_W$ can only be 2 or 3.Case 1: $n_W = 3$
Then $n_M = 3$. Since we need at least 3 right-handed people, all 3 men must be right-handed. All 3 women are left-handed.
Constraint 3 says every woman must have a left-handed person to her right. Since all men are right-handed, a woman cannot have a man to her right. She must have another woman to her right. This implies the 3 women must be seated consecutively: $W_1 \to W_2 \to W_3$. The person to the right of $W_3$ must also be left-handed. But the remaining people are men (who are right-handed). This is a contradiction. Thus, $n_W \neq 3$.Case 2: $n_W = 2$
Then $n_M = 4$. We need $\ge 3$ right-handed people. Since women are left-handed, we have 2 left-handed women. The men can be right-handed or left-handed. To satisfy $n_{RH} \ge 3$, at least 3 men must be right-handed. Let's assume 3 men are right-handed and 1 man is left-handed.
Let the two women be $W_1, W_2$. Since $W_1$ needs a left-handed person to her right, and $W_2$ is left-handed, we can place them adjacent: $W_1 \to W_2$. Now $W_2$ needs a left-handed person to her right. We can place the left-handed man ($M_L$) there. The sequence becomes $W_1(L) \to W_2(L) \to M_L(L) \to M_R(R) \to M_R(R) \to M_R(R)$.
This arrangement satisfies all constraints:

• 2 Women, 4 Men (satisfies $n_W \ge 2, n_M \ge 2$).
• 3 Right-handed people (satisfies $n_{RH} \ge 3$).
• Every woman has a left-handed person to her right ($W_1 \to W_2$, $W_2 \to M_L$).
• No woman is right-handed.

Thus, the number of women is 2.

To determine what the expression $\frac{(x+y)-|x-y|}{2}$ represents, we consider two cases based on the relative values of $x$ and $y$: If $x \geq y$, then $|x-y| = x-y$.
Substituting this into the expression:
$$\frac{(x+y) - (x-y)}{2} = \frac{x + y - x + y}{2} = \frac{2y}{2} = y$$ Since $x \geq y$, $y$ is the minimum of $x$ and $y$. If $x < y$, then $|x-y| = -(x-y) = y-x$.
Substituting this into the expression:
$$\frac{(x+y) - (y-x)}{2} = \frac{x + y - y + x}{2} = \frac{2x}{2} = x$$ Since $x < y$, $x$ is the minimum of $x$ and $y$.In both cases, the expression simplifies to $\min(x, y)$. Thus, the expression is equal to the minimum of $x$ and $y$.Correct option is (B).

Total number of ways to distribute 4 distinct shirts to 4 people is $4! = 24$.Let the people be A, G, N, S and shirts be R, P, B, W.
Constraints:Let $U$ be the set of all permutations. $|U| = 24$.
Let $X$ be the set of permutations where A chooses R.
Let $Y$ be the set of permutations where S chooses W.We want to find the number of valid permutations, which is $|U| - |X \cup Y|$.Using the Inclusion-Exclusion Principle:
$|X \cup Y| = |X| + |Y| - |X \cap Y|$ A is fixed to R. The remaining 3 people (G, N, S) can be arranged in $3! = 6$ ways.
$|X| = 6$. S is fixed to W. The remaining 3 people (A, G, N) can be arranged in $3! = 6$ ways.
$|Y| = 6$. A is fixed to R, and S is fixed to W. The remaining 2 people (G, N) can be arranged in $2! = 2$ ways.
$|X \cap Y| = 2$.Now, $|X \cup Y| = 6 + 6 - 2 = 10$.The number of valid ways is $|U| - |X \cup Y| = 24 - 10 = 14$.

The problem asks to identify villages with an elevation less than 525 m, as these will be submerged.

• The lines are at 25 m intervals.
• We see labels for 425, 450, 500, and 550.
• Between the 500 m line and the 550 m line, there must be one intermediate line representing 525 m (since $500 + 25 = 525$).
• Similarly, between 450 m and 500 m, there is a line for 475 m.

2. Analyze the elevation of each village:

• Village P: It is enclosed by the 550 m contour line. Since contour values increase towards the center of the peak (indicated by the progression 425 -> 450 -> ... -> 550), the elevation of P is $> 550$ m. P is safe.
• Village Q: It is inside a separate closed loop on the right. Given the topography, this is likely another peak or high ground similar to P. Assuming it follows the general rising trend or is a local peak above the surrounding 500+ m terrain, Q is likely $> 525$ m. If Q were in a depression (sinkhole), it would typically be marked with hachures, which are absent. Thus, Q is safe.
• Village R: It is located in the region between the 450 m and 500 m contours (specifically near the 475 m line). Its elevation is clearly $< 500$ m, so it is $< 525$ m. R will be submerged.
• Village S: It is located near the 450 m contour. Its elevation is $< 525$ m. S will be submerged.
• Village T: It is located near the 500 m contour line but outside the 525 m contour line (which is the line immediately surrounding the 550 m peak area). Its elevation is approximately 500 m, which is $< 525$ m. T will be submerged.

Conclusion: Villages R, S, and T are at elevations lower than the flood level of 525 m.

The given statement is $(\neg p) \Rightarrow (\neg q)$.

• Contrapositive of $(\neg p) \Rightarrow (\neg q)$ is $\neg(\neg q) \Rightarrow \neg(\neg p)$, which simplifies to $q \Rightarrow p$.
• This matches statement II.

2. Implication Law: The implication $A \Rightarrow B$ is logically equivalent to $(\neg A) \lor B$.

• Applying this to $(\neg p) \Rightarrow (\neg q)$, we get $\neg(\neg p) \lor (\neg q)$, which simplifies to $p \lor (\neg q)$.
• Since disjunction is commutative, $p \lor (\neg q)$ is equivalent to $(\neg q) \lor p$.
• This matches statement III.

Statement I ($p \Rightarrow q$) is the inverse, not equivalent.
Statement IV ($(\neg p) \lor q$) is equivalent to $p \Rightarrow q$, not the original statement.Thus, statements II and III are logically equivalent to the given statement.

The sentence $F$ is $\forall x(\exists y R(x, y))$.

• Statement IV: $\neg \exists x(\forall y \neg R(x, y))$

Using De Morgan's laws for quantifiers:
$\neg \exists x (\dots) \equiv \forall x \neg (\dots)$
$\neg (\forall y \neg R(x, y)) \equiv \exists y \neg(\neg R(x, y)) \equiv \exists y R(x, y)$
So, IV becomes $\forall x (\exists y R(x, y))$, which is exactly $F$. Thus, IV is implied (equivalent).

• Statement I: $\exists y(\exists x R(x, y))$

Since the domain is non-empty, let $c$ be an element in the domain. From $F$, for $x=c$, there exists a $y$ such that $R(c, y)$ is true. Thus, there exists a pair $(x, y)$ for which $R(x, y)$ holds. Therefore, $\exists x \exists y R(x, y)$ is true. Since existential quantifiers commute, this is equivalent to $\exists y \exists x R(x, y)$. Thus, I is implied.

• Statement II: $\exists y(\forall x R(x, y))$

This states there is a single $y$ that works for all $x$. $F$ only states that for each $x$, there is a corresponding $y$ (which may differ for different $x$). II is a stronger condition and is not implied by $F$.

• Statement III: $\forall y(\exists x R(x, y))$

This states that every $y$ in the domain is related to some $x$. $F$ does not guarantee that the range of the relation covers the entire domain. Not implied.Therefore, I and IV are implied.

To arrange the functions in increasing order of asymptotic complexity, we analyze their growth rates as $n \to \infty$:Combining these, the increasing order is:$$\frac{100}{n} < 10 < \log_2 n < \sqrt{n} < n$$This matches option (B).

The correct matching is based on the design paradigms of the algorithms:Thus, the correct correspondence is (P) $\leftrightarrow$ (ii), (Q) $\leftrightarrow$ (i), (R) $\leftrightarrow$ (iii).

The height of a tree is defined as the number of edges on the longest path from the root to a leaf. For a single node, height is 0.Minimum Height:
A binary tree has minimum height when it is as complete as possible. The maximum number of nodes in a binary tree of height $h$ is given by $2^{h+1} - 1$.
We need $2^{h+1} - 1 \ge 15$
$2^{h+1} \ge 16$
$h+1 \ge 4 \implies h \ge 3$
For $h=3$, max nodes $= 2^4 - 1 = 15$. Thus, a complete binary tree of height 3 has exactly 15 nodes.
Minimum height = 3.Maximum Height:
A binary tree has maximum height when it is a skewed tree (each node has only one child).
For $n$ nodes, the number of edges in a skewed tree is $n-1$.
Maximum height $= 15 - 1 = 14$.Therefore, the minimum and maximum heights are 3 and 14 respectively.

In an unsigned fixed-point representation with $n$ bits total and $f$ fractional bits:

• The smallest value is when all bits are 0, which represents $0$.
• The largest value is when all bits are 1.

The value of the number is given by $V = \sum_{k=-f}^{i-1} b_k 2^k$.
With $i$ integer bits and $f$ fractional bits:

• The maximum integer part (all 1s) is $2^i - 1$.
• The maximum fractional part (all 1s) is $1 - 2^{-f}$ (geometric series sum).

However, a simpler way to see the maximum value is:
Max value = (Max integer value of $n$ bits) $\times$ (weight of LSB)
Max integer value of $n$ bits = $2^n - 1$.
Weight of LSB = $2^{-f}$.
Max value = $(2^n - 1) \times 2^{-f} = 2^{n-f} - 2^{-f} = 2^i - 2^{-f}$.Thus, the range is $0$ to $(2^i - 2^{-f})$.

The function join attempts to append list m to the end of list n.Scenario 1: n is not NULL (non-empty list)
The code works as intended. p traverses to the last node, and m is appended. Result: m appended to n.Scenario 2: n is NULL (empty list)
p becomes NULL. The condition p->next in the while loop attempts to dereference a NULL pointer, causing a crash (segmentation fault).Since n being NULL is a valid state for a "valid NULL-terminated linked list" (an empty list), the code is not safe for all inputs.Therefore, it will either cause a null pointer dereference (if n is NULL) or append list m to n (if n is not NULL).

In 2's complement addition, overflow occurs when the result of adding two numbers with the same sign yields a result with the opposite sign.Let $A_7$ and $B_7$ be the sign bits of the operands, and $S_7$ be the sign bit of the sum.Combining these two cases, overflow occurs if:
$(A_7 \cdot B_7 \cdot \overline{S_7} + \overline{A_7} \cdot \overline{B_7} \cdot S_7) = 1$.Alternatively, overflow is defined as $C_{in} \oplus C_{out}$ for the MSB, i.e., $C_6 \oplus C_7$, but the expression in option (C) is the standard logic expression derived from the sign bits.

The grammar is:
$S \rightarrow abScT \mid abcT$
$T \rightarrow bT \mid b$First, analyze $T$. $T$ generates one or more $b$'s, i.e., $L(T) = b^+$.Now analyze $S$. The recursive production is $S \rightarrow abScT$. The base case is $S \rightarrow abcT$.
Expanding $S$:
$S \Rightarrow abcT$
$S \Rightarrow ab(abcT)cT = (ab)^2 c T c T$
$S \Rightarrow ab(abScT)cT \Rightarrow (ab)^3 c T c T c T$
In general, after $n$ applications (where $n \ge 1$), we get:
$(ab)^n c T c T \dots c T$ (with $n$ occurrences of $cT$).Since each $T$ independently generates $b^+$, let the number of $b$'s generated by the $i$-th $T$ be $m_i \ge 1$.
The string becomes:
$(ab)^n c b^{m_1} c b^{m_2} \dots c b^{m_n}$
where $n \ge 1$ and each $m_i \ge 1$.This matches option (B): $\{(ab)^n cb^{m_1} cb^{m_2} \dots cb^{m_n} \mid n, m_1, m_2, \dots, m_n \geq 1\}$.

The structure student has the following layout (assuming int is 4 bytes and char is 1 byte):

• marks: Array of 100 integers. Size = $100 \times 4 = 400$ bytes. Offset 0.
• grade: Character. Offset 400.
• cnumber: Integer. Offset 401 (or 404 with padding).

The base address of student is in R1. To access student.grade, we need to access the memory location at R1 + 400.This corresponds to Index addressing mode (also known as Base-Displacement or Displacement addressing), denoted as X(R1), where X is the constant offset (400).

Static Single Assignment (SSA) form is an intermediate representation used in compilers where each variable is assigned exactly once, and every variable is defined before it is used.Original code:To convert this to SSA, we must create a new version of a variable every time it is assigned. Let's trace the data flow:

• Line 1: $p$ is assigned. Let's call this version $p_1$. So, $p_1 = a - b$.
• Line 2: $q$ is assigned. Let's call this version $q_1$. It uses the current value of $p$, which is $p_1$. So, $q_1 = p_1 * c$.
• Line 3: $p$ is assigned again. We must use a new version, $p_2$. So, $p_2 = u * v$.
• Line 4: $q$ is assigned again. We must use a new version, $q_2$. It uses the current value of $p$ (from line 3, which is $p_2$) and the current value of $q$ (from line 2, which is $q_1$). So, $q_2 = p_2 + q_1$.

Now let's evaluate the options:

• Option (A): $p_1$ and $q_1$ are assigned twice, which violates the fundamental rule of SSA.
• Option (B): Every assignment uses a unique variable name ($p_3, q_4, p_4, q_5$). The data dependencies are correctly maintained: $q_4$ uses $p_3$ (the result of the first line), and $q_5$ uses $p_4$ (the result of the third line) and $q_4$ (the result of the second line). This is a valid SSA form.
• Option (C): Uses variables like $p_2, p_4,$ and $q_3$ that are never defined in the code.
• Option (D): Uses unversioned variables $p$ and $q$ in the expressions, which is not allowed in SSA.

Therefore, Option (B) is the correct representation.

The program allocates memory to x using malloc. Inside the if(x) block, x is reassigned to a new memory block allocated by a second malloc call. The address of the first allocated block is overwritten without being freed, causing a memory leak. The free(x) at the end only frees the second block.

A birthday attack allows finding two distinct messages $m$ and $m'$ such that $H(m) = H(m')$.

• (I) is possible: The sender S can generate a collision pair $(m, m')$, sign $m$, and later claim to have signed $m'$ (since the signature on the hash is valid for both). This allows S to repudiate the original message.
• (II) and (III) are not possible via birthday attack: For a third party or R to replace $m$ with $m'$, they would need to find an $m'$ that hashes to the same value as the specific $m$ already chosen and signed by S. This requires breaking second preimage resistance, which is computationally much harder than a birthday attack (finding any collision).