GATE CS 2014 Set 1

The phrase "cope with" means to deal effectively with something difficult. In the context of life forms and environmental conditions, "adapt to" (meaning to become adjusted to new conditions) is the closest in meaning. "Adopt to" is grammatically incorrect (adopt means to choose or take up). "Adept in" means skilled at. "Accept with" means to receive.

The sentence implies a contrast: he could not understand why she won, which means he must have thought her performance was not good. "Mediocre" means of only moderate quality; not very good. This fits the context. "Superb" and "exhilarating" are positive adjectives which would justify the prize. "Medium" is typically used for size or state, not quality of performance.

The idiom "the buck stops here" is used to indicate that the speaker accepts ultimate responsibility for decisions and actions and will not pass the blame to anyone else.

Given the equation:$$(z + \frac{1}{z})^2 = 98$$Expanding the left-hand side using the algebraic identity $(a + b)^2 = a^2 + 2ab + b^2$, where $a = z$ and $b = \frac{1}{z}$:$$z^2 + 2(z)\left(\frac{1}{z}\right) + \left(\frac{1}{z}\right)^2 = 98$$$$z^2 + 2 + \frac{1}{z^2} = 98$$To find the value of $z^2 + \frac{1}{z^2}$, subtract 2 from both sides of the equation:$$z^2 + \frac{1}{z^2} = 98 - 2$$$$z^2 + \frac{1}{z^2} = 96$$Therefore, the value of $(z^2 + 1/z^2)$ is 96.

Let the roots of the quadratic equation $ax^2 + bx + c = 0$ be $\alpha$ and $\beta$.
Given that the roots are real and positive, we have $\alpha > 0$ and $\beta > 0$.The second equation is $ax^2 + b|x| + c = 0$.
Since $x^2 = |x|^2$, we can rewrite the equation as:$$a(|x|)^2 + b(|x|) + c = 0$$Let $y = |x|$. The equation becomes $ay^2 + by + c = 0$, which is identical in form to the original equation. Therefore, the roots for $y$ are the same as the roots for the original equation:$$y = \alpha \quad \text{or} \quad y = \beta$$Substituting back $y = |x|$:Assuming the roots $\alpha$ and $\beta$ are distinct (as is implied by the option for 4 roots), we get 4 distinct real roots: $\alpha, -\alpha, \beta, -\beta$.Thus, the equation has 4 real roots.

The passage states that the existence of the Palghat Gap results in neighbouring regions of Tamil Nadu getting more rainfall and neighbouring regions of Kerala having higher summer temperatures. This implies that the physical geography (low terrain) of the gap influences the weather patterns (rainfall and temperature) in the adjacent areas.(A) is incorrect because the passage states the reasons for the formation of the gap are not clear.
(B) is incorrect because the passage describes the gap as lower than the hills to its north and south, but does not explicitly describe the elevation of the neighbouring regions in Tamil Nadu and Kerala.
(D) is incorrect because the passage lists higher temperatures and higher rainfall as separate results of the gap, not that one causes the other.

The argument states that geneticists are close to confirming the genetic roots of psychiatric illnesses and concludes that doctors will be able to eradicate them through gene therapy. This conclusion relies on the fundamental assumption that these illnesses indeed have a genetic basis. If they did not, confirming genetic roots would be impossible, and gene therapy would not be a viable eradication method. Therefore, the statement relies on the assumption that certain psychiatric illnesses have a genetic basis.

• One-way fare per person = Rs 100
• Round-trip fare per person = $100 \times 2 = Rs 200$
• Number of tourists = 5
• Total base fare = $200 \times 5 = Rs 1000$

2. Calculate discounts:

• Round-trip discount = 10% on the total fare.
• Group discount (4 or more) = 5% on the total fare.
• Since both discounts are "on the total fare", they are additive.
• Total discount percentage = $10\% + 5\% = 15\%$

3. Calculate final amount:

• Total discount amount = $15\% \text{ of } 1000 = 0.15 \times 1000 = Rs 150$
• Amount charged = $1000 - 150 = Rs 850$

Total respondents = 300.Respondents who do not own a scooter fall into two categories:From the table:

• Car only:
• Men: 40
• Women: 34
• Total Car + 34 = 74$* **Do not own vehicle:** * Men: 20 * Women: 50 * Total No vehicle =$20 + 50 = 70$Total respondents not owning a scooter =$74 + 70 = 144$.

Percentage = $$\frac{144}{300}$\times 100 = 48\%$.

A tetrahedron has 4 vertices. Let the vertices be $A, B, C, D$ and the internal point be $P$. When $P$ is connected to the corners ($A, B, C, D$), the lines $PA, PB, PC, PD$ are formed.The new internal planes are formed by the point $P$ and pairs of vertices (which correspond to the edges of the tetrahedron). A plane is defined by 3 non-collinear points. The internal planes are the triangles formed by $P$ and the edges of the tetrahedron.The edges of the tetrahedron are $AB, AC, AD, BC, BD, CD$. There are 6 edges in a tetrahedron.
For each edge (e.g., $AB$), a new internal plane $PAB$ is created.Since there are 6 edges, there are 6 new internal planes ($PAB, PAC, PAD, PBC, PBD, PCD$). These planes divide the original tetrahedron into 4 smaller tetrahedra ($PABC, PABD, PACD, PBCD$).Thus, 6 new internal planes are created.

To represent the statement "Not all that glitters is gold" in first-order logic, we can break down its meaning step-by-step: "Not all that glitters is gold" means "It is not the case that everything which glitters is gold." "Everything that glitters is gold" is represented as:
$$\forall x \, (glitters(x) \Rightarrow gold(x))$$ "Not all that glitters is gold" is the negation of the above formula:
$$\neg \big( \forall x \, (glitters(x) \Rightarrow gold(x)) \big)$$

• Using the quantifier negation rule, $\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$:

$$\exists x \, \neg (glitters(x) \Rightarrow gold(x))$$

• Using the implication equivalence, $P \Rightarrow Q \equiv \neg P \vee Q$:

$$\exists x \, \neg (\neg glitters(x) \vee gold(x))$$

• Applying De Morgan's Laws to the negation:

$$\exists x \, (glitters(x) \wedge \neg gold(x))$$This final expression translates to: "There exists some object $x$ such that $x$ glitters and $x$ is not gold," which perfectly captures the meaning of the original statement.Therefore, the correct representation is Option D.

Let the stick be represented by the interval $[0, 1]$. We break the stick at a point $X$ chosen uniformly at random from the interval $[0, 1]$. The probability density function (PDF) of $X$ is:$$f(x) = 1 \quad \text{for } 0 \le x \le 1$$When the stick is broken at $X$, it is divided into two pieces of lengths $X$ and $1 - X$. Let $Y$ be the random variable representing the length of the shorter piece. Therefore, $Y$ is defined as:$$Y = \min(X, 1 - X)$$We can express $Y$ as a function of $X$:Y = \begin{cases} $ X & \text{if } 0 \le X < 0.5 \\$ $ 1 - X & \text{if } 0.5 \le X \le 1 $ \end{cases}To find the expected length of the shorter stick, $E[Y]$, we integrate $Y$ over the probability density of $X$:$$E[Y] = \int_{0}^{1} \min(x, 1-x) f(x) \, dx$$Since $f(x) = 1$, we split the integral at the boundary point $x = 0.5$:$$E[Y] = \int_{0}^{0.5} x \, dx + \int_{0.5}^{1} (1 - x) \, dx$$Evaluating the two integrals separately: $$\int_{0}^{0.5} x \, dx = \left[ \frac{x^2}{2} \right]_{0}^{0.5} = \frac{(0.5)^2}{2} - 0 = \frac{0.25}{2} = 0.125$$ $$\int_{0.5}^{1} (1 - x) \, dx = \left[ x - \frac{x^2}{2} \right]_{0.5}^{1} = \left( 1 - \frac{1}{2} \right) - \left( 0.5 - \frac{0.25}{2} \right)$$ $$= 0.5 - (0.5 - 0.125) = 0.125$$Adding the two parts together:$$E[Y] = 0.125 + 0.125 = 0.25$$Thus, the expected length of the shorter stick is $0.25$.

To find which graph has the same strongly connected components (SCCs) as $G = (V, E)$, let us analyze the definition of a strongly connected component and the properties of the given options.

1. Definition of Strongly Connected Components (SCCs)

In a directed graph $G = (V, E)$, two vertices $u$ and $v$ belong to the same strongly connected component if and only if there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$ in $G$. We denote this mutual reachability relation as $u \leftrightarrow v$.

2. Analysis of Option B: The Transpose Graph $G_2$

The graph $G_2 = (V, E_2)$ is defined by reversing the direction of all edges in $G$:$$E_2 = \{(u,v) \mid (v,u) \in E\}$$This graph $G_2$ is known as the transpose graph of $G$, often denoted as $G^T$.Let us determine the reachability relation in $G_2$:

• A directed path from $u$ to $v$ exists in $G$ if and only if there is a directed path from $v$ to $u$ in $G_2$.
• Similarly, a directed path from $v$ to $u$ exists in $G$ if and only if there is a directed path from $u$ to $v$ in $G_2$.

Therefore, two vertices $u$ and $v$ are mutually reachable in $G$ if and only if they are mutually reachable in $G_2$:$$u \leftrightarrow v \text{ in } G \iff u \leftrightarrow v \text{ in } G_2$$Since the equivalence relation of mutual reachability is identical for both $G$ and $G_2$, the equivalence classes (which are the strongly connected components) are exactly the same for both graphs.---

3. Why Other Options are Incorrect

• Option A ($G_1$): $G_1$ is the complement graph. Changing the edge set to non-existent edges completely alters the reachability structure. For example, if $G$ is a single directed cycle of 3 vertices (which is strongly connected), its complement $G_1$ will not be strongly connected.
• Option C ($G_3$): $G_3$ adds transitive shortcut edges of length $\le 2$. This can merge separate SCCs of $G$ into a single SCC. For example, if $G$ is a path $a \to b \to c$, the SCCs of $G$ are $\{a\}$, $\{b\}$, and $\{c\}$. In $G_3$, we add the edge $(a, c)$, but there is still no path back, so the SCCs remain the same in this specific case, but if we have $a \to b \to c$ and $c \to a$, adding paths of length $\le 2$ can create new cycles and merge components that were not originally connected in both directions. More simply, $G_3$ changes the reachability relation and does not preserve the exact SCC boundaries in all graphs.
• Option D ($G_4$): $G_4$ modifies the vertex set by removing isolated vertices ($V_4 \subseteq V$). If $G$ contains any isolated vertices, they form their own single-vertex SCCs. Removing them means $G_4$ will have fewer SCCs than $G$.

Thus, only the transpose graph $G_2$ is guaranteed to have the exact same strongly connected components as $G$.Correct Answer: Option B

We have the system of equations:
1) $3x + 2y = 1$
2) $4x + 7z = 1$
3) $x + y + z = 3$
4) $x - 2y + 7z = 0$From (1), $y = \frac{1-3x}{2}$.
Substitute $y$ into (3):
$x + \frac{1-3x}{2} + z = 3 \implies 2x + 1 - 3x + 2z = 6 \implies -x + 2z = 5 \implies x = 2z - 5$.Substitute $x$ into (2):
$4(2z - 5) + 7z = 1 \implies 8z - 20 + 7z = 1 \implies 15z = 21 \implies z = \frac{21}{15} = 1.4$.Now find $x$:
$x = 2(1.4) - 5 = 2.8 - 5 = -2.2$.Now find $y$:
$y = \frac{1 - 3(-2.2)}{2} = \frac{1 + 6.6}{2} = \frac{7.6}{2} = 3.8$.We have a unique candidate solution $(x, y, z) = (-2.2, 3.8, 1.4)$.
We must verify if this satisfies the fourth equation (4):
$x - 2y + 7z = -2.2 - 2(3.8) + 7(1.4) = -2.2 - 7.6 + 9.8 = -9.8 + 9.8 = 0$.The solution satisfies all equations. Since the system is linear and we found a unique solution by substitution, there is exactly 1 solution.

A key property of real symmetric matrices is that eigenvectors corresponding to distinct eigenvalues are orthogonal. If $\lambda_1$ and $\lambda_2$ are distinct eigenvalues with corresponding eigenvectors $v_1$ and $v_2$, then the dot product $v_1 \cdot v_2 = 0$.Therefore, the value is 0.

The function $f(\theta)$ is defined as a determinant. Notice the structure of the rows.
Row 1 depends on $\theta$.
Row 2 is the values of Row 1 evaluated at $\theta = \pi/6$.
Row 3 is the values of Row 1 evaluated at $\theta = \pi/3$.When $\theta = \pi/6$, Row 1 becomes identical to Row 2. A determinant with two identical rows is 0. Thus, $f(\pi/6) = 0$.
When $\theta = \pi/3$, Row 1 becomes identical to Row 3. Thus, $f(\pi/3) = 0$.Since $f(\theta)$ is a linear combination of differentiable functions ($\sin, \cos, \tan$) on the interval $[\pi/6, \pi/3]$, it is continuous and differentiable.
By Rolle's Theorem, since $f(\pi/6) = f(\pi/3) = 0$, there exists at least one $c \in (\pi/6, \pi/3)$ such that $f'(c) = 0$. So, statement (I) is TRUE.To check statement (II), we need to know if $f(\theta)$ is identically zero (constant). If it were constant zero, $f'(\theta)$ would always be 0.
Expanding the determinant along the first row:
$f(\theta) = \sin\theta(C_1) - \cos\theta(C_2) + \tan\theta(C_3)$, where $C_1, C_2, C_3$ are constants (minors).
Unless all coefficients are zero or the functions cancel out perfectly (which they don't for these specific values), the function is not a constant zero. For example, we can check a point like $\pi/4$. The rows would be linearly independent, so $f(\pi/4) \neq 0$.
Since $f(\theta)$ is not constant, its derivative is not identically zero. Thus, there exists some $\theta$ where $f'(\theta) \neq 0$. So, statement (II) is TRUE.Both statements are true.

Given Boolean expression:
$F(P, Q, R, S) = PQ + P\bar{Q}R + P\bar{Q}\bar{R}S$
Factor out $P$:
$F = P(Q + \bar{Q}R + \bar{Q}\bar{R}S)$
Using the absorption law $A + \bar{A}B = A + B$ on the first two terms inside the parentheses:
$Q + \bar{Q}R = Q + R$
So, $F = P(Q + R + \bar{Q}\bar{R}S)$
Rearrange terms:
$F = P(Q + \bar{Q}\bar{R}S + R)$
Apply $A + \bar{A}B = A + B$ again where $A = Q$ and $B = \bar{R}S$:
$Q + \bar{Q}(\bar{R}S) = Q + \bar{R}S$
So, $F = P(Q + \bar{R}S + R)$
Apply $A + \bar{A}B = A + B$ again where $A = R$ and $B = S$:
$R + \bar{R}S = R + S$
So, $F = P(Q + R + S)$
Expanding the expression:
$F = PQ + PR + PS$
This is the minimal sum-of-products form.

Let the base of the number system be $r$.
Convert the given equation into decimal form:
$\frac{3r^2 + 1r + 2}{2r + 0} = 1r^1 + 3r^0 + 1r^{-1}$
$\frac{3r^2 + r + 2}{2r} = r + 3 + \frac{1}{r}$
Multiply both sides by $2r$:
$3r^2 + r + 2 = 2r(r + 3 + \frac{1}{r})$
$3r^2 + r + 2 = 2r^2 + 6r + 2$
Subtract $2r^2 + 6r + 2$ from both sides:
$r^2 - 5r = 0$
$r(r - 5) = 0$
Since the base $r$ must be greater than the largest digit present in the numbers (which is 3), $r$ cannot be 0.
Therefore, $r = 5$.

Bits for immediate operand = Total bits - Opcode bits - Register bits
Bits for immediate operand = $32 - 6 - 12 = 14$ bits.

The program declares an integer variable i and a pointer pi initialized to the address of i. The scanf function reads an integer from standard input and stores it at the address pointed to by pi (which is &i). Thus, the input value is stored in i. The printf statement then prints the value of i + 5. Therefore, the output is 5 more than the integer value entered.

In a Depth First Search (DFS), every vertex is visited. When a vertex $u$ is visited, we must iterate through all possible neighbors to find adjacent vertices. In an adjacency matrix representation, finding the neighbors of a vertex requires scanning the entire row corresponding to that vertex, which takes $\Theta(n)$ time. Since there are $n$ vertices, the total time complexity is $n \times \Theta(n) = \Theta(n^2)$. Note that for an adjacency list, the complexity would be $\Theta(n+m)$.

To determine the number of subtrees with exactly 4 nodes, we can perform a post-order traversal (bottom-up approach). For each node, we calculate the size of the subtree rooted at that node as:$$\text{size}(u) = 1 + \text{size}(u.\text{left}) + \text{size}(u.\text{right})$$If $\text{size}(u) == 4$, we increment a counter. This process visits each node exactly once and performs constant work at each node. Thus, the time complexity is $O(n)$.Comparing $O(n)$ with $O(n^a \log^b n)$, we get:
$a = 1$
$b = 0$The value of $a + 10b = 1 + 10(0) = 1$.

A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge $uv$ from vertex $u$ to vertex $v$, $u$ comes before $v$ in the ordering. A topological ordering is possible if and only if the graph has no directed cycles (i.e., it is a Directed Acyclic Graph or DAG).Let's analyze the given graph for cycles:

• There is an edge P → Q.
• There is an edge Q → S.
• There is an edge S → P.

This forms a cycle $P \to Q \to S \to P$. Since the graph contains a directed cycle, it is not a DAG, and therefore, it does not have any topological ordering.Thus, option (A) is correct.

We calculate the number of comparisons for each input. In Quicksort, the pivot is compared with every other element in the current sub-array to partition it.For input [1 2 3 4 5] ($t_1$):Total $t_1 = 4 + 3 + 2 + 1 = 10$.For input [4 1 5 3 2] ($t_2$):Total $t_2 = 4 + 2 + 1 = 7$.Comparing $t_1$ and $t_2$:
$t_1 = 10$
$t_2 = 7$
Therefore, $t_1 > t_2$.

Let's analyze each option:(A) $L = \{a^n b^n \mid n \geq 0\}$ is a classic Context-Free Language (CFL) but is not regular. A finite automaton cannot count the number of $a$'s to match with $b$'s for arbitrary $n$.(B) $L = \{a^n \mid n \text{ is prime}\}$ is not regular. This can be proven using the Pumping Lemma.(C) $L = \{w \mid w \text{ has } 3k+1 \text{ } b\text{'s}\}$ means the number of $b$'s is congruent to $1 \pmod 3$. This requires counting modulo 3, which can be done with a finite automaton (DFA) having 3 states (representing remainders 0, 1, 2). Since a DFA can be constructed, the language is regular.(D) $L = \{ww \mid w \in \Sigma^*\}$ is a Context-Sensitive Language (CSL) but not regular (and not even Context-Free). It requires checking if the first half of the string is identical to the second half.Therefore, option (C) is the correct statement.

Let $\delta$ be the transition function. We start at the initial state set $S_0 = \{q_0\}$.Input string: $0011$ $\delta(q_0, 0) = \{q_0\}$
Current set: $\{q_0\}$ $\delta(q_0, 0) = \{q_0\}$
Current set: $\{q_0\}$ $\delta(q_0, 1) = \{q_0, q_1\}$
Current set: $\{q_0, q_1\}$ $\delta(q_0, 1) = \{q_0, q_1\}$
$\delta(q_1, 1) = \{q_2\}$
Union: $\{q_0, q_1\} \cup \{q_2\} = \{q_0, q_1, q_2\}$The set of reachable states is $\{q_0, q_1, q_2\}$.