GATE CSE 2017 SET 2

The words 'yielding' and 'resistant' are antonyms, not synonyms. 'Yielding' implies giving way or surrendering, while 'resistant' means opposing or withstanding. The other pairs consist of words with similar meanings: 'aversion' and 'dislike' both mean a strong feeling of not liking something; 'luminous' and 'radiant' both mean shining or bright; and 'plunder' and 'loot' both refer to stealing goods, typically during a war or riot.

The word 'enough' functions as an adverb modifying the adjective 'bright'. In English grammar, when 'enough' is used as an adverb to qualify an adjective, it must be placed after the adjective it modifies. Therefore, the grammatically correct construction is "bright enough". The other options are syntactically incorrect.

The relative positions of the buildings can be established from the given statements. "Z is to the West of V" and "V is to the West of W" gives the order Z-V-W. "Z is to the East of X" means X is West of Z, giving X-Z-V-W. Finally, "W is to the West of Y" completes the sequence from West to East as: X, Z, V, W, Y. In this arrangement of five buildings, the one in the middle is V.

Let $m$ be the number of multiple-choice questions and $e$ be the number of essay questions. The given conditions form a system of linear equations:

1. $m + e = 20$ (total questions)
2. $3m + 11e = 100$ (total marks)
   From the first equation, $e = 20 - m$. Substituting this into the second equation gives $3m + 11(20 - m) = 100$, which simplifies to $3m + 220 - 11m = 100$, or $8m = 120$. Solving for $m$ gives $m = 15$.

There are a total of $3+4+3=10$ socks. The total number of ways to choose 2 socks from 10 is given by the combination formula $^{10}C_2 = \frac{10 \times 9}{2} = 45$.
The number of ways to choose 2 socks of the same color is the sum of the ways to choose 2 red ($^3C_2=3$), 2 green ($^4C_2=6$), or 2 blue ($^3C_2=3$).
The total number of favorable outcomes is $3+6+3=12$.
The probability is the ratio of favorable outcomes to total outcomes, which is $\frac{12}{45} = \frac{4}{15}$.

The word "seemingly" is used to describe ideology as "seemingly more urgent". This adverb casts doubt on the stated urgency, suggesting it is more of an appearance than a fact. By questioning the importance of ideology in this subtle way, the author implies their belief that literature possesses a more genuine and fundamental value, which is being overlooked for something of only apparent urgency.

Since all three boxes are labeled incorrectly, the box marked 'Apples and Oranges' must contain either only apples or only oranges. You should open this box. If you pull out an apple, you know this is the 'Apples' box. Consequently, the box labeled 'Oranges' must contain 'Apples and Oranges' (as it cannot be 'Oranges' or 'Apples'). This leaves the box labeled 'Apples' to be the 'Oranges' box. A similar deduction follows if you pull out an orange.

To estimate the number of digits in $X^3$, where $X$ is a 30-digit number, we can use a general property. If a number $N$ has $d$ digits, then $N^k$ will have approximately $k \times d$ digits. In this case, $X$ has 30 digits. The solution approximates the number of digits in its cube, $X^3$, by multiplying the number of digits by 3. This gives an estimate of $3 \times 30 = 90$ digits.

To find the number of roots for the equation $f(x) = e^x + 0.5x^2 - 2 = 0$ in the interval [-5, 5], we can use the Intermediate Value Theorem by checking for sign changes in the function's value.
Evaluating the function at key points:

• $f(-2) \approx 0.135$ (positive)
• $f(-1) \approx -1.13$ (negative)
• $f(1) \approx 1.21$ (positive)
  A sign change occurs between $x=-2$ and $x=-1$, indicating one root. A second sign change occurs between $x=-1$ and $x=1$, indicating another root. Thus, there are at least two roots in the given range.

A thunderstorm is most likely in a region with a rapid change in air pressure. On the contour map, this corresponds to the area with the steepest pressure gradient, indicated by the most closely spaced contour lines. The solution quantifies this by calculating the pressure difference across each region.

• Region P: $0.95 - 0.90 = 0.05$
• Region Q: $0.80 - 0.75 = 0.05$
• Region R: $0.85 - 0.65 = 0.20$
• Region S: $0.95 - 0.90 = 0.05$
  Region R has the largest pressure difference (0.20 bar), indicating the most rapid change and the highest likelihood of a thunderstorm.

To convert the hexadecimal number BCA9 to octal, we first convert it to its 16-bit binary representation. Each hexadecimal digit corresponds to four binary digits:
B (11) → 1011
C (12) → 1100
A (10) → 1010
9 (9) → 1001
So, BCA9₁₆ = 1011110010101001₂.

Next, we group the binary digits into sets of three from right to left, padding with a leading zero if necessary, to convert to octal.
1 | 011 | 110 | 010 | 101 | 001
Converting each 3-bit group to its octal equivalent gives:
1 | 3 | 6 | 2 | 5 | 1
Thus, the octal representation is 136251₈.

This question matches C language declarations and statements with their memory-related descriptions.
(P) static char var;: A static variable is allocated in the data segment of the program's memory. This matches (ii).
(Q) m = malloc(10); m = NULL;: malloc allocates memory on the heap. Reassigning the pointer m to NULL without freeing the allocated block results in a memory leak, as the memory becomes inaccessible. This matches (iv).
(R) char *ptr[10];: This declares an array of 10 pointers. An array is a contiguous sequence of memory locations, and in this case, each location stores a memory address. This matches (i).
(S) register int var1;: The register keyword suggests to the compiler that the variable should be stored in a CPU register for faster access. This matches (iii).

The time complexities for the given algorithms are standard results in algorithm analysis.
(P) Towers of Hanoi with n disks: The problem has a recurrence relation $T(n) = 2T(n-1) + 1$, which resolves to an exponential time complexity of $\theta(2^n)$.
(Q) Binary search: On a sorted array of n elements, binary search halves the search space in each step, leading to a logarithmic time complexity of $\theta(\log n)$.
(R) Heap sort: The worst-case time complexity for heap sort on n numbers is $\theta(n \log n)$, which involves building the heap and then extracting elements one by one.
(S) Addition of two n×n matrices: This requires adding corresponding elements for all $n^2$ positions, resulting in a time complexity of $\theta(n^2)$.

The question tests the closure properties of context-free languages (CFLs).
I. The union of two CFLs ($L_1 \cup L_2$) is always a CFL. This is a standard closure property. Thus, statement I is correct.
III. The difference between a CFL and a regular language ($L_1 - R$) is also a CFL. This is because $L_1 - R = L_1 \cap \bar{R}$. Since regular languages are closed under complement, $\bar{R}$ is regular. The intersection of a CFL and a regular language is a CFL. Thus, statement III is correct.
CFLs are not closed under intersection or complement, so statements II and IV are incorrect.

This question matches inputs to their corresponding phases in a compiler's front end.
(Q) Character stream: The raw source code is first read as a stream of characters. This is the input to the Lexical Analyzer. This matches (iv).
(S) Token stream: The Lexical Analyzer processes the character stream and groups characters into a sequence of tokens. This token stream is the input to the Syntax Analyzer (Parser). This matches (ii).
(P) Syntax tree: The Syntax Analyzer parses the token stream to create a hierarchical structure like a syntax tree. This tree is then processed by the Semantic Analyzer. This matches (iii).
(R) Intermediate representation: After semantic analysis, the compiler generates an intermediate representation (IR) of the program. This IR is the input to the Code Generator. This matches (i).

The power of LR parsers is determined by the amount of lookahead information they use to make parsing decisions. The hierarchy of power among these parsers is: Canonical LR (CLR) > Look-Ahead LR (LALR) > Simple LR (SLR). CLR is the most powerful as it uses the most contextual information. LALR is a compromise between power and size, and is more powerful than SLR. Therefore, the statement "Canonical LR is more powerful than SLR" is correct, while the other two statements are incorrect.

Threads within the same process share certain resources while maintaining their own execution context. The shared resources include the address space (which contains the code, data, and heap sections). However, each thread has its own program counter, stack, and set of registers to manage its independent execution flow. Therefore, only the address space is shared among all threads of a process.

External fragmentation occurs when there is enough total free space to satisfy a request, but it is not contiguous. Contiguous allocation can lead to external fragmentation as files are deleted and created. In contrast, linked and indexed allocation methods store file blocks in a non-contiguous manner. This flexibility allows them to use any available free block, thus eliminating the problem of external fragmentation.

Let's evaluate each statement:
I. RIP is a distance-vector routing protocol, which is correct.
II. RIP uses UDP for sending its routing updates. This is also correct.
III. OSPF does not use TCP or UDP. It operates directly on top of the IP protocol. Thus, this statement is incorrect.
IV. OSPF is a link-state routing (LSR) protocol, which is correct.
Therefore, statements I, II, and IV are the correct ones.

Given the function $f(x)=R \sin(\frac{\pi x}{2})+S$.
First, find the derivative: $f'(x) = R \cos(\frac{\pi x}{2}) \cdot \frac{\pi}{2}$.
Using the condition $f'(\frac{1}{2})=\sqrt{2}$:
$R \cos(\frac{\pi}{4}) \cdot \frac{\pi}{2} = \sqrt{2} \implies R (\frac{1}{\sqrt{2}}) \frac{\pi}{2} = \sqrt{2} \implies R = \frac{4}{\pi}$.

Next, use the integration condition $\int_{0}^{1}f(x)dx=\frac{2R}{\pi}$:
$\int_{0}^{1} (R \sin(\frac{\pi x}{2}) + S) dx = [ -R\frac{2}{\pi}\cos(\frac{\pi x}{2}) + Sx ]_0^1 = (0+S) - (-R\frac{2}{\pi}) = S + \frac{2R}{\pi}$.
Since this must equal $\frac{2R}{\pi}$, we have $S + \frac{2R}{\pi} = \frac{2R}{\pi}$, which implies $S=0$.

The given English statement has two parts connected by "and".
The first part is "It is not raining and it is pleasant". Translating this using the given symbols gives $\neg p \wedge r$.
The second part is "it is not pleasant only if it is raining and it is cold". The logical structure "A only if B" is equivalent to the implication $A \rightarrow B$. Therefore, this part translates to $\neg r \rightarrow (p \wedge q)$.
Combining both parts with a logical AND ($\wedge$) results in the final expression: $(\neg p \wedge r) \wedge (\neg r \rightarrow (p \wedge q))$.

The 32-bit IEEE-754 number is parsed into three parts: sign (S), exponent (E), and mantissa (M).

• Sign bit (S): 0 (The number is positive).
• Exponent (E): 01111100 in binary, which is $124$ in decimal.
• Mantissa (M): 110110100...
  The decimal value is calculated using the formula $(-1)^S \times (1.M)_2 \times 2^{E-127}$.
  Substituting the values: $(-1)^0 \times (1.1101101)_2 \times 2^{124-127}$.
  This simplifies to $(1.1101101)_2 \times 2^{-3}$.
  The binary fraction $(1.1101101)_2$ is approximately $1.8515625$ in decimal.
  So, the value is $1.8515625 \times 2^{-3} = 1.8515625 / 8 \approx 0.2314$. This value is closest to $0.227$, which is $2.27 \times 10^{-1}$.

For a circular queue implemented with a singly linked list to support O(1) insertion and deletion, an efficient structure is required. Deletion occurs at the front and insertion at the rear.
If the next pointer of the rear node points to the front node, we can access the front from the rear in O(1) time. This allows for efficient deletion of the front node and insertion after the rear node.
Statement II, "Next pointer of rear node points to the front node," describes this correct and efficient implementation.
Statement I is incorrect; having the front node's pointer point to the rear node does not facilitate standard O(1) queue operations.

The function printxy is called with arguments by value, so local variables x and y are created inside the function with initial values of 1.

1. x = 0;: The local variable x is updated to 0.
2. ptr = &x;: The pointer ptr is assigned the memory address of the local x.
3. y = *ptr;: The value at the address ptr (which is the value of x, i.e., 0) is assigned to y. So, y becomes 0.
4. *ptr = 1;: The value at the address ptr is changed to 1. Since ptr points to x, the value of x becomes 1.
   Finally, printf prints the current values of x and y, which are 1 and 0, respectively.

Breadth-First Search (BFS) explores a graph level by level, starting from a source node. It uses a queue to manage the nodes to be visited. A valid BFS traversal visits all nodes at a certain distance (level) from the source before visiting any nodes at the next level.
Let's trace the option POQNMR starting with P:

1. Start at P. Visit P. Add its neighbors (O, Q) to the queue.
2. Visit nodes at the next level. Dequeue and visit O, then Q.
3. As O and Q are visited, their unvisited neighbors (N, R) are added to the queue.
4. Visit nodes at the next level. Dequeue and visit N, then M (a neighbor of N).
5. Finally, dequeue and visit R.
   The sequence POQNMR is a valid BFS traversal as it explores nodes layer by layer: {P}, then {O, Q}, then {N, R, M}. The order within a layer depends on the order neighbors are added to the queue.

The grammar is S → XY, with X → aX|a and Y → aYb|ε.
The non-terminal X generates one or more 'a's. So, the language for X is L(X) = {a^k | k ≥ 1}.
The non-terminal Y generates strings with an equal number of 'a's and 'b's, where 'a's precede 'b's. The language for Y is L(Y) = {a^n b^n | n ≥ 0}.
The start symbol S concatenates a string from L(X) with one from L(Y), resulting in strings of the form a^k * a^n * b^n.
This simplifies to a^(k+n) * b^n. Let m = k+n. Since k ≥ 1 and n ≥ 0, it follows that m > n.
Thus, the generated language is {a^m b^n | m > n, n ≥ 0}.

To merge the relational table for relationship R with the table for entity A, two conditions must be met.
First, the relationship R must be many-to-one from A to B. This means each entity in A can be related to at most one entity in B. This allows the primary key of B to be placed as a foreign key in the table for A.
Second, the participation of entity A in relationship R must be total. This ensures that every tuple in the table for A must participate in the relationship, guaranteeing that the foreign key column will not contain any NULL values.

Calling connect() on a UDP socket fixes the destination address for subsequent send() calls and filters incoming datagrams to only those from that specific address. This means the socket is associated with a single peer. Therefore, statement I, which claims communication with multiple peers, is incorrect.
However, for a connectionless socket like UDP, the connect() function can be called multiple times on the same socket to change the peer association to a different address. Thus, statement II is correct.

The initial action is deleting the record (3, 8) from table T1. We must check the foreign key constraints.
Table T2 has a foreign key S that references T1's primary key P, with an ON DELETE SET NULL rule. The record (8, 3) in T2 references the primary key P=3. Due to the rule, this record in T2 is updated to (8, NULL) instead of being deleted.
Since no records are deleted from T2, the ON DELETE CASCADE rule for the foreign key from T1 to T2 is not triggered.
Consequently, no other records in T1 are deleted. The number of additional records deleted from T1 is 0.

The IPv4 header has a maximum size of 60 bytes. With a fixed base header of 20 bytes, this leaves a maximum of 40 bytes for options.
The Record Route (RR) option uses 3 bytes for its own metadata: 1 byte for option type, 1 byte for length, and 1 byte for a pointer. This leaves 40 - 3 = 37 bytes available for storing the IP addresses.
Since each IPv4 address requires 4 bytes, the maximum number of addresses that can be recorded is $\lfloor \frac{37}{4} \rfloor = 9$.

A poset is a lattice if every pair of elements has a unique least upper bound (join) and a unique greatest lower bound (meet). For the given poset (X, R), we can verify that for any pair of elements, a join and a meet already exist within the set X. For example, the join of {b, d} is e, and their meet is a. Since this property holds for all pairs, the poset is already a lattice. Therefore, no additional ordered pairs need to be added.

First, we compute the sum of the matrices P and Q:
$P+Q = \begin{bmatrix} 1 & 1&-1 \\ 2&-3 & 4\\ 3 &-2 & 3 \end{bmatrix} + \begin{bmatrix} -1 & -2&-1 \\ 6 & 12& 6\\ 5&10 & 5 \end{bmatrix} = \begin{bmatrix} 0 & -1 & -2 \\ 8 & 9 & 10 \\ 8 & 8 & 8 \end{bmatrix}$
The rank of a matrix is the number of linearly independent rows. The determinant of P+Q is 0, which means its rank is less than 3. The first two rows are linearly independent. The third row is also not a linear combination of the first two. However, we can see that Row 2 - Row 3 = [0 1 2], which is -1 * Row 1. Thus, the rows are linearly dependent, and there are only 2 linearly independent rows. The rank is 2.

According to the handshaking lemma for an undirected graph, the sum of the degrees of all vertices is equal to twice the number of edges.
$\sum_{i=1}^{n} \text{deg}(v_i) = 2|E|$
Given that each of the $n$ vertices has a degree of at least 3, the sum of degrees is at least $3n$. The number of edges $|E|$ is 25.
Therefore, we have the inequality:
$3n \le 2 \times 25 \implies 3n \le 50$
$n \le \frac{50}{3} \approx 16.66$
Since the number of vertices $n$ must be an integer, the maximum possible value for $n$ is 16.

For a quadratic equation $x^2 + Bx + C = 0$, the sum of the roots is $-B$ and the product of the roots is $C$. The given equation is $x^2 - (13)_b x + (36)_b = 0$, and the roots are $(5)_b$ and $(6)_b$.

Sum of roots: $(5)_b + (6)_b = (13)_b$.
In base 10, this is $5 + 6 = 1 \cdot b^1 + 3 \cdot b^0$, which simplifies to $11 = b + 3$. Solving for $b$ gives $b=8$.

Product of roots: $(5)_b \times (6)_b = (36)_b$.
In base 10, this is $5 \times 6 = 3 \cdot b^1 + 6 \cdot b^0$, which simplifies to $30 = 3b + 6$. Solving for $b$ gives $3b = 24$, so $b=8$.
Both conditions confirm the base is 8.

The language is $L=\{w_{1}aw_{2}|w_{1},w_{2}\in \{a,b\}^{*},|w_{1}|=2,|w_{2}|\geq 3\}$. This means any string in the language must have 'a' at the third position and must have a total length of at least $2+1+3=6$.

A DFA needs states to track the input string's length and structure:

• States to read the first two symbols ($w_1$): 3 states ($q_0, q_1, q_2$).
• A state to check if the third symbol is 'a': transition from $q_2$ to $q_3$ on 'a'.
• States to read at least three more symbols ($w_2$): 3 states ($q_4, q_5, q_6$). $q_6$ is the first accepting state.
  This requires 7 states ($q_0$ to $q_6$). Additionally, a dead/trap state is needed for any input that violates the pattern (e.g., the third symbol is 'b'). This brings the total minimum number of states to 8.

Let P be the event that P applies and Q be the event that Q applies.
We are given:
$P(P) = 1/4$
$P(P|Q) = 1/2$
$P(Q|P) = 1/3$

From the conditional probability formula, $P(Q|P) = \frac{P(P \cap Q)}{P(P)}$.
So, $P(P \cap Q) = P(Q|P) \times P(P) = \frac{1}{3} \times \frac{1}{4} = \frac{1}{12}$.

Also, $P(P|Q) = \frac{P(P \cap Q)}{P(Q)}$.
So, $P(Q) = \frac{P(P \cap Q)}{P(P|Q)} = \frac{1/12}{1/2} = \frac{1}{6}$.

We need to find $P(\bar{P}|\bar{Q}) = \frac{P(\bar{P} \cap \bar{Q})}{P(\bar{Q})}$.
Using De Morgan's law, $P(\bar{P} \cap \bar{Q}) = P(\overline{P \cup Q}) = 1 - P(P \cup Q)$.
$P(P \cup Q) = P(P) + P(Q) - P(P \cap Q) = \frac{1}{4} + \frac{1}{6} - \frac{1}{12} = \frac{3+2-1}{12} = \frac{4}{12} = \frac{1}{3}$.
So, $P(\bar{P} \cap \bar{Q}) = 1 - \frac{1}{3} = \frac{2}{3}$.
And $P(\bar{Q}) = 1 - P(Q) = 1 - \frac{1}{6} = \frac{5}{6}$.
Finally, $P(\bar{P}|\bar{Q}) = \frac{2/3}{5/6} = \frac{2}{3} \times \frac{6}{5} = \frac{4}{5}$.

The question asks to identify the incorrect Boolean identity. Let's analyze option C.
The expression is $(w\bar{x}(y+x\bar{z})+\bar{w}\bar{x})y=x\bar{y}$.

Let's simplify the Left Hand Side (LHS):
LHS = $(w\bar{x}y + w\bar{x}x\bar{z} + \bar{w}\bar{x})y$ (Distributive law)
Since $x \cdot \bar{x} = 0$, the term $w\bar{x}x\bar{z}$ becomes 0.
LHS = $(w\bar{x}y + \bar{w}\bar{x})y$
LHS = $w\bar{x}y \cdot y + \bar{w}\bar{x}y$ (Distributive law)
Using the idempotent law ($y \cdot y = y$):
LHS = $w\bar{x}y + \bar{w}\bar{x}y$
Factoring out $\bar{x}y$:
LHS = $(w+\bar{w})\bar{x}y$
Using the complement law ($w+\bar{w}=1$):
LHS = $1 \cdot \bar{x}y = \bar{x}y$

The simplified LHS is $\bar{x}y$, which is not equal to the Right Hand Side (RHS) $x\bar{y}$. Thus, the statement is incorrect.

To find the minimum Product-of-Sums (POS) form, we group the 0s in the Karnaugh map.
The function is given by minterms $f(w,x,y,z) = \sum_{m}(0,1,2,3,7,8,10)$ and don't cares $\sum_{d}(5,6,11,15)$.
The cells corresponding to 0s are those not in the minterm or don't-care lists: {4, 9, 12, 13, 14}.

We create a K-map for these 0s and group them to find the simplified POS expression.
The K-map for the 0s (with don't cares) is:

   yz
wx 00 01 11 10
00  .  .  .  .
01  0  X  .  X
11  0  0  X  0
10  .  0  X  .

We can form two maximal groups of 0s (including don't cares):

1. A group of four covering cells (4, 6, 12, 14). For this group, $x=1$ and $z=0$ is not true for all cells. The common variable is $z=0$ and $x$ changes. This is not a valid group. Let's re-examine. The group for $(\bar{x}+z)$ corresponds to cells where $x=1$ and $z=0$. These are cells 4, 6, 12, 14. Values: 4(0), 6(X), 12(0), 14(0). This is a valid group. The SOP term for $\bar{f}$ is $x\bar{z}$, which gives the POS term $(\bar{x}+z)$ for $f$.
2. A group of four covering cells (9, 11, 13, 15). Values: 9(0), 11(X), 13(0), 15(X). This is a valid group. The SOP term for $\bar{f}$ is $wz$, which gives the POS term $(\bar{w}+\bar{z})$ for $f$.

Combining these two terms gives the minimal POS form: $f = (\bar{w}+\bar{z})(\bar{x}+z)$.

The Average Memory Access Time (AMAT) for a two-level cache system is given by:
AMAT = $H_1 \times T_1 + (1-H_1) \times (H_2 \times (T_1+T_2) + (1-H_2) \times (T_1+T_2+T_M))$
A simpler formula is: AMAT = $T_{L1} + M_{L1} \times (\text{Miss Penalty}_{L1})$
Miss Penalty$_{L1}$ = $T_{L2} + M_{L2} \times (\text{Miss Penalty}_{L2})$
Given: $T_{L1}=1$, $T_{L2}=8$, Miss Penalty$_{L2}$ (from L2 to main memory) = 18. Let $M_{L2} = m$. Then $M_{L1} = 2m$. AMAT = 2.

AMAT = $T_{L1} + M_{L1} \times (T_{L2} + M_{L2} \times 18)$
$2 = 1 + (2m) \times (8 + m \times 18)$
$1 = 2m(8 + 18m)$
$1 = 16m + 36m^2$
$36m^2 + 16m - 1 = 0$
Solving this quadratic equation for $m$:
$m = \frac{-16 \pm \sqrt{16^2 - 4(36)(-1)}}{2(36)} = \frac{-16 \pm \sqrt{256 + 144}}{72} = \frac{-16 \pm \sqrt{400}}{72} = \frac{-16 \pm 20}{72}$
Since miss rate must be positive, $m = \frac{4}{72} = \frac{1}{18} \approx 0.0555$.
So, $M_{L2} = m \approx 0.056$.
And $M_{L1} = 2m \approx 0.111$.

The given recurrence relation is $T(n) = 2T(\sqrt{n}) + 1$.
Let's change the variable to simplify the recurrence. Let $n = 2^m$, so $m = \log_2 n$.
Then $\sqrt{n} = (2^m)^{1/2} = 2^{m/2}$.
The recurrence becomes $T(2^m) = 2T(2^{m/2}) + 1$.
Now, let $S(m) = T(2^m)$. The new recurrence is $S(m) = 2S(m/2) + 1$.
This is a standard form solvable by the Master Theorem. Here, $a=2, b=2, f(m)=1$.
We compare $f(m)=m^0$ with $m^{\log_b a} = m^{\log_2 2} = m^1$.
Since $f(m) = O(m^{1-\epsilon})$ for $\epsilon=1$, this is Case 1 of the Master Theorem.
Thus, $S(m) = \theta(m^{\log_b a}) = \theta(m)$.
Now, we substitute back $m = \log_2 n$.
So, $T(n) = S(\log_2 n) = \theta(\log_2 n) = \theta(\log n)$.

The expectation of a discrete random variable Y, $E(Y)$, can be found from its probability generating function, $g_Y(z)$. One method is to use the cumulant generating function, $K_Y(z) = \log_e g_Y(z)$. The expectation is the first derivative of $K_Y(z)$ with respect to z, evaluated at z=1.

Given $g_Y(z) = (1 - \beta + \beta z)^N$, the cumulant generating function is $K_Y(z) = N \log(1 - \beta + \beta z)$.
Differentiating with respect to z gives:
$\frac{dK_Y(z)}{dz} = N \cdot \frac{\beta}{1 - \beta + \beta z}$
Evaluating at z=1:
$E(Y) = N \cdot \frac{\beta}{1 - \beta + \beta(1)} = N \cdot \frac{\beta}{1} = N\beta$

The given grammar G contains left recursion in the productions for E and T, for example, E → E-T. To make the grammar suitable for top-down parsing, this left recursion must be eliminated. The standard rule for eliminating left recursion of the form A → Aα | β is to replace it with the productions A → βA' and A' → αA' | ε.

Applying this to E → E-T | T, we get E → TE' and E' → -TE' | ε.
Applying this to T → T+F | F, we get T → FT' and T' → +FT' | ε.

The grammar in option (C) applies this transformation, using X for E' and Y for T', resulting in an equivalent, non-left-recursive grammar.

This problem can be solved using the Banker's algorithm for deadlock avoidance.
First, calculate the available resources: Total drives (9) - Allocated drives (3+1+3=7) = 2 available drives.
Next, calculate the remaining need for each process (Need = Max - Allocation):

• P1 needs 7 - 3 = 4
• P2 needs 6 - 1 = 5
• P3 needs 5 - 3 = 2

With 2 available drives, only P3's need can be met. P3 runs to completion and releases its 3 allocated drives.
Available resources become 2 + 3 = 5.
Now, P1's need of 4 can be met. P1 runs and releases its 3 drives.
Available resources become 5 + 3 = 8.
Finally, P2's need of 5 can be met.
Since a safe sequence <P3, P1, P2> exists, the system is in a safe state and is not deadlocked.

The minimum Hamming distance (p) of a code is the smallest number of bit positions in which any two distinct codewords differ. We calculate the distance between all pairs:

• d(00000, 01011) = 3
• d(00000, 10101) = 3
• d(00000, 11110) = 4
• d(01011, 10101) = 4
• d(01011, 11110) = 3
• d(10101, 11110) = 3
  The minimum of these distances is 3, so p = 3.

The maximum number of correctable errors (q) is related to p by the inequality $p \geq 2q + 1$.
Substituting p = 3, we get $3 \geq 2q + 1$, which simplifies to $2 \geq 2q$, or $q \leq 1$. The maximum integer value for q is 1.

The transmission delay (p) is the time required to place the entire message on the link. It is calculated as Message Size / Bandwidth.
Message size = 50,000 bytes = $50,000 \times 8$ bits = 400,000 bits.
Bandwidth = $10^6$ bits/sec.
$p = \frac{400,000 \text{ bits}}{10^6 \text{ bits/sec}} = 0.4 \text{ sec} = 400 \text{ ms}$

The propagation delay (q) is the time it takes for a bit to travel from the source to the destination. It is calculated as Distance / Propagation Speed.
Distance = 10,000 km = $10^7$ m.
$q = \frac{10^7 \text{ m}}{2 \times 10^8 \text{ m/sec}} = 0.05 \text{ sec} = 50 \text{ ms}$

The pre-order traversal of a Binary Search Tree (BST) is given. To find the post-order traversal, we first need to construct the tree. For a BST, the in-order traversal is the sorted sequence of its elements. By sorting the given pre-order sequence, we get the in-order traversal: 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20.

Using the pre-order (Root-Left-Right) and in-order (Left-Root-Right) traversals, the BST is constructed. The first element of the pre-order, 12, is the root. All elements before 12 in the in-order sequence form the left subtree, and all elements after form the right subtree. This process is applied recursively. After constructing the tree, a post-order traversal (Left-Right-Root) yields the sequence: 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12.

The program performs division using the relationship x = y*q + r, where q is the quotient and r is the remainder. This equation must hold as a loop invariant, meaning it must be true before the loop begins. The loop terminates when r < y.

To satisfy the invariant x = y*q + r at the start, we can initialize the variables appropriately. If we set q = 0 and r = x, the equation becomes x = y*0 + x, which simplifies to x = x. This initialization is correct. Additionally, for the division to be meaningful and for the loop to terminate, the divisor y must be greater than 0. Thus, the required pre-conditions are (q == 0) && (r == x) && (y > 0).

The time complexity is determined by the total number of executions of the printf statement. The outer loop, controlled by i, runs from 1 to n. The inner loop, controlled by j, starts at 1 and increments by i until j is no longer less than n.

For a given value of i from the outer loop, the inner loop will execute approximately n/i times. To find the total complexity, we sum the executions of the inner loop for all values of i:
$T(n) \approx \sum_{i=1}^{n} \frac{n}{i} = n \sum_{i=1}^{n} \frac{1}{i}$
The summation $\sum_{i=1}^{n} \frac{1}{i}$ is the n-th Harmonic number, which is asymptotically equivalent to $\log n$. Therefore, the total time complexity is $\theta(n \log n)$.

To find the set of states reachable from $q_2$ on input aba, we trace the transitions using the extended transition function $\hat{\delta}$, which includes $\epsilon$-closures.

1. Start at $q_2$. The $\epsilon$-closure of $\{q_2\}$ is $\{q_0, q_2\}$ because $q_2 \xrightarrow{\epsilon} q_0$.
2. On input 'a': From $\{q_0, q_2\}$, only $q_0$ has a transition on 'a' to $q_1$. The $\epsilon$-closure of $\{q_1\}$ is $\{q_0, q_1, q_2\}$ (since $q_1 \xrightarrow{\epsilon} q_2$ and $q_2 \xrightarrow{\epsilon} q_0$).
3. On input 'b': From $\{q_0, q_1, q_2\}$, we can go to $\{q_0, q_3\}$. The $\epsilon$-closure of $\{q_0, q_3\}$ is $\{q_0, q_2, q_3\}$ (since $q_3 \xrightarrow{\epsilon} q_2$ and $q_2 \xrightarrow{\epsilon} q_0$).
4. On input 'a': From $\{q_0, q_2, q_3\}$, only $q_0$ has a transition on 'a' to $q_1$. The final set of states is the $\epsilon$-closure of $\{q_1\}$, which is $\{q_0, q_1, q_2\}$.

Let's analyze the statements based on the language hierarchy.
Statement III: $L_3 = \{a^n b^n c^{2n} | n \ge 0\}$. This language requires matching the count of 'a's and 'b's, and then matching that count to twice the number of 'c's. A pushdown automaton cannot perform these multiple dependent comparisons. Thus, $L_3$ is not context-free. It is, however, a context-sensitive language (CSL), and all CSLs are recursive. So, statement III is correct.

Statement IV: $L_4 = \{a^n b^n | n \ge 1\}$. This is a classic deterministic context-free language (DCFL). A deterministic PDA can push a symbol onto the stack for each 'a' and then pop a symbol for each 'b', accepting if the stack is empty. Thus, statement IV is correct.
Statements I and II are incorrect.

This question assesses the decidability of standard problems for different classes of languages in the Chomsky hierarchy.
I. Membership problem for regular languages (w ∈ L(R)): This is decidable. A finite automaton can be constructed to check if the string w is accepted.
II. Emptiness problem for context-free languages (L(G) = φ): This is decidable. There are algorithms to check if a CFG can generate any string.
III. Universality problem for context-free languages (L(G) = Σ*): This is undecidable. There is no general algorithm to determine if a CFG generates all possible strings over its alphabet.
IV. Membership problem for recursively enumerable languages (w ∈ L(M)): This is undecidable. This is equivalent to the Halting Problem, which is famously undecidable.
Therefore, problems III and IV are undecidable.