GATE CSE 2016 SET 2

The word "until" functions as a negative conditional conjunction. Using another negative term like "does not" or "doesn't" would create a double negative, which is grammatically incorrect in this context. The subject, "the minister," is a third-person singular noun, so the verb must take the singular form "meets." Thus, the grammatically correct and most suitable sentence is the one using "until the minister meets me."

This question tests the correct usage of articles. The role "security guard" is being introduced for the first time in a non-specific sense, so the indefinite article "a" is appropriate. The location "university" is treated as a specific place in the context of the sentence, warranting the use of the definite article "the". Therefore, "a security guard at the university" is the grammatically correct phrase. The PDF solution confirms this choice.

The phrasal verb "cope with" means to deal effectively with something difficult or challenging. Among the given options, "put up with" is the closest synonym. It means to tolerate or endure a difficult situation or person. The solution in the PDF directly equates "cope with" to "put up with" in this context.

The words "mock," "deride," and "jeer" are all synonyms. They share the negative meaning of ridiculing or making fun of someone in a contemptuous manner. In contrast, the word "praise" has a positive meaning: to express warm approval or admiration. As its meaning is opposite to the other three words, "praise" is the odd one out in the group.

The first three options follow a consistent pattern. If the letters in each string are reordered according to the positional sequence 2-4-1-3-5, they form a consecutive alphabetical sequence.

• A. CADBE → A(pos 2), B(pos 4), C(pos 1), D(pos 3), E(pos 5) → ABCDE
• B. JHKIL → H(pos 2), I(pos 4), J(pos 1), K(pos 3), L(pos 5) → HIJKL
• C. XVYWZ → V(pos 2), W(pos 4), X(pos 1), Y(pos 3), Z(pos 5) → VWXYZ
  Option D, ONPMQ, breaks this pattern. Its reordered sequence is N-M-O-P-Q, which is not alphabetical.

The given expression is $\frac{\alpha^{n}+\beta^{n}}{\alpha^{-n}+\beta^{-n}}$. The denominator can be rewritten using the property $x^{-n} = \frac{1}{x^n}$.
So, $\alpha^{-n}+\beta^{-n} = \frac{1}{\alpha^n} + \frac{1}{\beta^n}$.
Finding a common denominator, this becomes $\frac{\beta^n + \alpha^n}{(\alpha\beta)^n}$.
Substituting this back into the original expression gives:
$\frac{\alpha^{n}+\beta^{n}}{\frac{\alpha^{n}+\beta^{n}}{(\alpha\beta)^n}}$
The term $(\alpha^{n}+\beta^{n})$ cancels out, leaving $(\alpha\beta)^n$.
Given that the product of the roots $\alpha\beta = 4$, the final value is $4^n$.

There are 150 total faculty members. Since 30 members use neither Facebook nor WhatsApp, the number of members using at least one of these services is $150 - 30 = 120$. This is the total number of members in the union of the Facebook and WhatsApp sets, $n(F \cup W) = 120$.
The number of members connected only through Facebook can be found by taking the total in the union and subtracting the number of members who use WhatsApp.
Number of members only on Facebook = $n(F \cup W) - n(W) = 120 - 85 = 35$.

The provided paragraph questions the impact of recent technological developments but does not explicitly state that computers are "not good," making statement (i) an invalid inference. The text mentions that "Many believe that the internet itself is an unintended consequence of the original invention," which directly contradicts statement (ii) that the internet was an intended invention. Since neither statement can be logically derived from the passage, the correct choice is that neither (i) nor (ii) is valid.

The premise "All hill-stations have a lake" means that if a place is a hill-station, it must have at least one lake. It does not set a maximum limit on the number of lakes.
(i) "Ooty is not a hill-station" is an invalid inference. Since Ooty has two lakes, it satisfies the condition of having at least one lake, so it can be a hill-station.
(ii) "No hill-station can have more than one lake" is also an invalid inference. The premise only establishes a minimum of one lake, not a maximum. Therefore, a hill-station could have multiple lakes.

A rectangle is formed by selecting two distinct horizontal lines and two distinct vertical lines from the grid. A 2x4 grid of cells is constructed from 3 horizontal lines and 5 vertical lines.
The number of ways to choose 2 horizontal lines from the 3 available is given by the combination formula $\binom{3}{2} = 3$.
The number of ways to choose 2 vertical lines from the 5 available is $\binom{5}{2} = \frac{5 \times 4}{2} = 10$.
The total number of possible rectangles is the product of these two values: $3 \times 10 = 30$.

The expression $P \wedge (P \Rightarrow Q)$ is logically equivalent to $P \wedge (\neg P \vee Q)$. Using the distributive law, this becomes $(P \wedge \neg P) \vee (P \wedge Q)$, which simplifies to $F \vee (P \wedge Q)$, or just $P \wedge Q$.

We now check which of the given expressions are logically implied by $P \wedge Q$:

1. $P \wedge Q \Rightarrow Q$ (True)
2. $P \wedge Q \Rightarrow \text{true}$ (True)
3. $P \wedge Q \Rightarrow P \vee Q$ (True)
4. $P \wedge Q \Rightarrow (\neg Q \vee P)$ (True, as this is equivalent to $P \wedge Q \Rightarrow (Q \Rightarrow P)$)

Thus, four expressions-(ii), (iii), (iv), and (v)-are logically implied.

Let the degree of the polynomial $f(x)$ be $n$. The expression $f(x) + f(-x)$ consists of only the even-powered terms of $f(x)$. Since the degree of $f(x) + f(-x)$ is given as 10, the degree of $f(x)$ must be $n=10$.

The derivative $g(x) = f'(x)$ will have a degree of $n-1 = 9$.

The expression $g(x) - g(-x)$ consists of only the odd-powered terms of $g(x)$. Since the highest power in $g(x)$ is 9 (an odd number), this term will not be cancelled out. Therefore, the degree of $g(x) - g(-x)$ is 9.

This question relates to the Four Color Theorem, a fundamental concept in graph theory. The theorem states that any planar graph-a graph that can be drawn on a plane without any edges crossing-can be vertex-colored with at most four colors. This ensures that no two adjacent vertices share the same color. Therefore, four colors are always sufficient for vertex-coloring any planar graph.

Let's analyze each statement:
I. "If $m < n$, then all such systems have a solution" is false. A system can be inconsistent. For example, $x+y+z=1$ and $x+y+z=2$ has no solution, with $m=2, n=3$.

II. "If $m > n$, then none of these systems has a solution" is false. A system can have redundant equations and be consistent. For example, $x+y=2$ and $2x+2y=4$ and $x-y=0$ has a solution $x=1, y=1$, with $m=3, n=2$.

III. "If $m = n$, then there exists a system which has a solution" is true. We can easily construct such a system, for example, $x=1, y=2$ is a system with $m=n=2$ that has a solution.

The determinant of a matrix is the product of its eigenvalues.
Given the eigenvalues of matrix A are 1, 2, and 4.
So, the determinant of A is $\det(A) = 1 \times 2 \times 4 = 8$.

We use two properties of determinants:

1. $\det(A^{-1}) = \frac{1}{\det(A)}$
2. $\det(M^T) = \det(M)$

Therefore, $\det((A^{-1})^T) = \det(A^{-1}) = \frac{1}{\det(A)} = \frac{1}{8} = 0.125$.

The longest latency in a ripple-carry adder occurs when a carry signal must propagate through the maximum number of full-adder stages. We are given A = 1, which is 00000001 in 8-bit 2's complement. To force a carry to ripple through all 8 stages, we need to choose B such that each bit position i generates a carry-out. This happens if B is 11111111, which is the 2's complement representation of -1. The addition 00000001 + 11111111 causes a carry to be generated and propagated from the least significant bit to the most significant bit.

The given equation is $x_{1} \oplus x_{2} \oplus x_{3} \oplus x_{4}=0$. The XOR operation is associative and commutative. We can manipulate the equation using the property that $a \oplus a = 0$. By XORing both sides of the original equation with $(x_{2} \oplus x_{4})$, we get:
$(x_{1} \oplus x_{2} \oplus x_{3} \oplus x_{4}) \oplus (x_{2} \oplus x_{4}) = 0 \oplus (x_{2} \oplus x_{4})$
Rearranging the terms:
$x_{1} \oplus x_{3} \oplus (x_{2} \oplus x_{2}) \oplus (x_{4} \oplus x_{4}) = x_{2} \oplus x_{4}$
This simplifies to $x_{1} \oplus x_{3} = x_{2} \oplus x_{4}$.

For a 16-bit number, there are $2^{16}$ possible bit patterns.
In 2's complement representation (X), every bit pattern maps to a unique integer. Therefore, the number of distinct integers is X = $2^{16}$.
In sign-magnitude representation (Y), there are two representations for zero: +0 (a sign bit of 0 followed by all 0s) and -0 (a sign bit of 1 followed by all 0s). Since both represent the same value, the number of distinct integers is one less than the total number of patterns. Thus, Y = $2^{16} - 1$.
The difference is X - Y = $2^{16} - (2^{16} - 1) = 1$.

The total instruction word size is 32 bits.
To represent 40 distinct instructions, the opcode field requires $\lceil \log_2 40 \rceil = 6$ bits, since $2^5 < 40 < 2^6$.
To address one of 24 general-purpose registers, each register operand field requires $\lceil \log_2 24 \rceil = 5$ bits, since $2^4 < 24 < 2^5$.
Since there are two register operands, they consume a total of $2 \times 5 = 10$ bits.
The total bits used by the opcode and register fields are $6 + 10 = 16$ bits.
The remaining bits available for the immediate operand are $32 - 16 = 16$ bits.

Breadth-First Search (BFS) visits nodes level by level. A vertex at a distance of 4 from the root is at level 4 (assuming the root is at level 0). To maximize the traversal order n for a vertex at this level, we need to maximize the number of nodes visited before it. This occurs when the binary tree is a complete binary tree up to level 4, and the vertex t is the last node visited at that level.
The total number of nodes in a complete binary tree up to level k is $\sum_{i=0}^{k} 2^i = 2^{k+1}-1$.
For level 4, the total number of nodes is $2^{4+1}-1 = 31$.

In the main function, f(&i, j) is called. The variable i is passed by reference (its address is sent), while j is passed by value (a copy of its value is sent). Inside function f, the local variable m is assigned j's value (10) and then incremented to 15. This change does not affect j in main. The pointer p points to i, so *p = *p + m; updates i's value to 5 + 15 = 20. The final printf statement prints the sum i + j, which is 20 + 10 = 30.

Let the degree of the polynomial $f(x)$ be $n$. The expression $f(x) + f(-x)$ cancels all terms with odd powers. Since the degree of $f(x) + f(-x)$ is given as 10 (an even number), the degree of the original polynomial $f(x)$ must be $n=10$.

The derivative, $g(x) = f'(x)$, will have a degree of $n-1 = 9$. The expression $g(x) - g(-x)$ cancels all terms with even powers from $g(x)$. Since the highest power in $g(x)$ is 9 (an odd number), this term will not be cancelled. Therefore, the degree of $g(x) - g(-x)$ is 9.

Let's analyze the time complexity for each algorithm on an already sorted input sequence.
I. Quicksort: When the input is sorted, Quicksort consistently picks the worst pivot, leading to highly unbalanced partitions. This is the worst-case scenario for Quicksort, resulting in a $\Theta(n^2)$ runtime. Thus, statement I is TRUE.
III. Merge Sort: Merge sort's performance is independent of the initial order of the input. It always divides the array and merges, resulting in a $\Theta(n \log n)$ runtime. The statement says $\Theta(n)$, so it is FALSE.
IV. Insertion Sort: When the input is already sorted, Insertion sort performs only one comparison per element, which is its best-case scenario. This results in a $\Theta(n)$ runtime. Thus, statement IV is TRUE.
Based on this, statements I and IV are true.

The Floyd-Warshall algorithm is a classic example of the dynamic programming paradigm. It solves the all-pairs shortest path problem by building up a solution iteratively. It computes the shortest paths by considering all possible intermediate vertices for each pair of source and destination vertices. The solution for a problem with $k$ intermediate vertices is built upon the solution for $k-1$ vertices, which is the fundamental characteristic of dynamic programming.

The total time complexity is the sum of the time taken for all operations.

1. $\Theta(N)$ delete operations: A pointer to the node is given, so each deletion is $\Theta(1)$. Total time: $\Theta(N) \times \Theta(1) = \Theta(N)$.
2. $O(\log N)$ insert operations: To maintain a sorted list, finding the insertion point takes $O(N)$. Total time: $O(\log N) \times O(N) = O(N \log N)$.
3. $O(\log N)$ find operations: Searching a linked list requires a linear scan, taking $O(N)$. Total time: $O(\log N) \times O(N) = O(N \log N)$.
4. $\Theta(N)$ decrease-key operations: After decreasing the key (at a given pointer), the node must be re-inserted in the correct sorted position, which takes $O(N)$. Total time: $\Theta(N) \times O(N) = \Theta(N^2)$.
   The overall complexity is dominated by the most expensive set of operations, which is the decrease-key operations. Thus, the total time complexity is $O(N^2)$.

The regular expression is $(0+1)*(0+1)(0+1)*$. The component $(0+1)^*$ represents any string of 0s and 1s (including the empty string), while $(0+1)$ represents a single character. The combination requires at least one character, effectively defining the language of all non-empty strings over the alphabet $\{0, 1\}$. A minimal DFA for this language requires two states: a non-accepting start state (to handle the empty string, which is not in the language) and a single accepting state for all strings of length one or more.

The grammar for L1, $S_{1}\rightarrow aS_{1}b|\varepsilon$, generates the language $\{a^n b^n | n \ge 0\}$. This is a classic context-free language that is not regular because it requires a memory (like a stack) to ensure the number of 'a's equals the number of 'b's. Therefore, statement P is false. The grammar for L2, $S_{2}\rightarrow abS_{2}|\varepsilon$, generates the language $\{(ab)^n | n \ge 0\}$, which can be described by the regular expression $(ab)^*$. Since it has a regular expression, L2 is a regular language. Therefore, statement Q is true.

This question tests closure properties of language classes.
I. $L_3$ is Recursive (REC), so its complement $\bar{L}_{3}$ is also REC. $L_4$ is Recursively Enumerable (RE). The union of a REC language and an RE language is RE. So, $\bar{L}_{3}\cup L_{4}$ is RE. Statement I is true.
II. $L_2$ is Context-Free (CFL), which is a subset of REC. REC languages are closed under complement, so $\bar{L}_{2}$ is REC. The union of two REC languages ($\bar{L}_{2}$ and $L_3$) is REC. Statement II is true.
III. $L_1$ is Regular, so its Kleene star $L_{1}^{*}$ is also Regular. $L_2$ is CFL. The union of a Regular language and a CFL is a CFL. Statement III is true.

This question matches concepts from compiler design phases with their corresponding techniques or artifacts.
(P) Lexical analysis involves scanning the input text and grouping characters into tokens. This process is modeled using regular expressions.
(Q) Top-down parsing, such as LL parsing, constructs a parse tree from the root down, which corresponds to a leftmost derivation of the string.
(R) Semantic analysis checks for meaning-related errors, a key part of which is type checking to ensure operators are applied to compatible operands.
(S) Runtime environments manage the program's execution state, using activation records (stack frames) for function calls.
This corresponds to P-iii, Q-i, R-ii, S-iv.

The phenomenon where increasing the number of allocated memory frames leads to an increase in the page fault rate is known as Belady's Anomaly. Among the standard page replacement algorithms, only the First-In, First-Out (FIFO) algorithm is susceptible to this issue. Other algorithms like LRU and OPT do not suffer from Belady's Anomaly, as their performance generally improves or stays the same with more frames.

A B+ tree is defined as a balanced tree because the path length from the root to every leaf node is identical. This structural property ensures that all leaf nodes reside at the same depth or level. Consequently, the time taken to access any record is uniform and predictable, as it avoids the performance degradation that can occur in unbalanced trees where some branches are much longer than others.

A schedule is conflict-serializable if its precedence graph, which shows dependencies between conflicting operations of transactions, is acyclic. If the graph is acyclic, a topological sort of its vertices (the transactions) can be performed. This topological ordering provides a valid serial schedule that is conflict-equivalent to the original concurrent schedule. Therefore, a topological order is guaranteed to yield a correct serial schedule.

Digital signatures rely on asymmetric cryptography. The sender, Anarkali, creates a signature by using her own private key. To verify the authenticity of this signature, the receiver, Salim, must use the sender's corresponding public key. This process confirms that the message was indeed signed by Anarkali and has not been altered in transit. Therefore, Salim requires Anarkali's public key for verification.

In an Ethernet network that uses CSMA/CD, collisions can occur when multiple stations transmit simultaneously. After a collision is detected, the involved stations use the exponential backoff algorithm. This mechanism requires each station to wait for a random amount of time before retransmitting. The range of possible wait times increases exponentially with each subsequent collision, which reduces the probability of another collision during retransmission.

When a host requests a webpage, it must first resolve the server's domain name (e.g., www.example.com) into an IP address. This is done via a DNS query. Once the IP address is obtained, a reliable connection must be established with the server using the TCP protocol, which starts with a TCP SYN packet (the first step of the three-way handshake). Only after the TCP connection is established can the browser send the HTTP GET request to fetch the webpage content.

A relation R is reflexive if for every element x, (x)R(x). For the given relation on $\mathbb{N}\times \mathbb{N}$, we check if (a,b)R(a,b). This condition is true if $a \leq a$ or $b \leq b$. Since $a \leq a$ is always true, the relation is reflexive. Thus, proposition P is true.

A relation is transitive if (a,b)R(c,d) and (c,d)R(e,f) implies (a,b)R(e,f). Consider the counterexample: (2,4)R(3,2) is true because $2 \leq 3$. Also, (3,2)R(1,3) is true because $2 \leq 3$. However, (2,4)R(1,3) is false because neither $2 \leq 1$ nor $4 \leq 3$ is true. Therefore, the relation is not transitive, and proposition Q is false.

The formula in option D, $\forall x (p(x)\vee q(x))\Rightarrow (\forall x p(x) \vee \forall x q(x))$, is not universally valid. The antecedent $\forall x (p(x)\vee q(x))$ states that for every x, at least one of p(x) or q(x) is true. The consequent $(\forall x p(x) \vee \forall x q(x))$ states that either p(x) is true for all x, or q(x) is true for all x.

Consider a counterexample where the domain is the set of integers. Let p(x) be "x is even" and q(x) be "x is odd". The antecedent is true, as every integer is either even or odd. However, the consequent is false because it's not true that all integers are even, nor is it true that all integers are odd. Since the antecedent can be true while the consequent is false, the implication is not valid.

This problem can be modeled using graph theory. Let the 23 compounds be vertices and a reaction between two compounds be an edge. The degree of a vertex is the number of compounds it reacts with. We are given that 9 vertices (compounds in set S) have a degree of 3, which is an odd number.

A fundamental theorem in graph theory states that the number of vertices with an odd degree in any graph must be even. Since we already have 9 vertices with an odd degree, there must be at least one more vertex with an odd degree among the remaining 14 vertices (in U \ S) to make the total count of odd-degree vertices even. Therefore, at least one compound in U \ S must react with an odd number of compounds. This makes statement II always true.

To evaluate $13^{99} \pmod{17}$, we can use Fermat's Little Theorem, which states that if p is a prime number, then for any integer a not divisible by p, we have $a^{p-1} \equiv 1 \pmod{p}$.

Here, p = 17 (a prime) and a = 13. The theorem applies, so $13^{17-1} \equiv 13^{16} \equiv 1 \pmod{17}$.

Now, we can rewrite the exponent 99 in terms of 16:
$99 = 16 \times 6 + 3$
So, $13^{99} = 13^{16 \times 6 + 3} = (13^{16})^6 \cdot 13^3$.

Taking the modulus:
$(13^{16})^6 \cdot 13^3 \pmod{17} \equiv (1)^6 \cdot 13^3 \pmod{17} \equiv 13^3 \pmod{17}$.

Finally, we calculate $13^3 = 2197$. Dividing 2197 by 17 gives a remainder of 4.
$2197 = 17 \times 129 + 4$.
Thus, $13^{99} \pmod{17} = 4$.

The computation $F(G(X_i))$ can be viewed as a two-stage pipeline. Stage 1 is the computation of G (3 ns) and Stage 2 is the computation of F (5 ns). We have two units for each function, which means we have two identical, parallel pipelines.

The 10 computations can be split between the two pipelines, with each pipeline handling 5 tasks. The total time will be the time taken by one pipeline to complete its 5 tasks.

For a single pipeline, the time to get the first result is the sum of stage delays: $3 + 5 = 8$ ns.
Subsequent results emerge at a rate determined by the slowest stage, which is 5 ns.
The total time for one pipeline to process 5 tasks is:
Time = (Time for 1st task) + (Number of remaining tasks) $\times$ (Slowest stage time)
Time = $8 \text{ ns} + (5-1) \times 5 \text{ ns} = 8 + 20 = 28$ ns.
Since both pipelines run in parallel, the total time is 28 ns.

To determine the memory consumed, we first find the size of a single instruction in bits.
The number of bits for the opcode field is $\lceil \log_2 12 \rceil = 4$ bits.
The number of bits for each register identifier is $\lceil \log_2 64 \rceil = 6$ bits.
The total bits per instruction are:
4 (opcode) + 6 (src reg 1) + 6 (src reg 2) + 6 (dest reg) + 12 (immediate) = 34 bits.
Due to byte-alignment, each instruction must occupy a whole number of bytes. 34 bits requires 5 bytes (40 bits).
For 100 instructions, the total memory is $100 \times 5 = 500$ bytes.

The physical address is composed of Tag, Set, and Offset bits. The total width is 40 bits.
The number of bits for the Set and Offset fields combined depends on the cache size, not the block size.
Total Cache Size = (Number of Sets) $\times$ (Associativity) $\times$ (Block Size)
In terms of bits:
$\log_2(\text{Cache Size}) = \log_2(\text{Num Sets}) + \log_2(\text{Associativity}) + \log_2(\text{Block Size})$
$19 = \text{Set bits} + 3 + \text{Offset bits}$
This gives: Set bits + Offset bits = $19 - 3 = 16$ bits.
The Tag bits are the remaining bits of the physical address:
Tag bits = Physical Address bits - (Set bits + Offset bits) = $40 - 16 = 24$ bits.

The initial processor frequency is 3 GHz, so the initial clock period $T_{old} = 1/3$ ns. The clock period is determined by the longest pipeline stage. Let the stage latencies be $\tau_1, \tau_2, \tau_3$. From the given relations $\tau_1 = 3\tau_2/4$ and $\tau_1 = 2\tau_3$, we can see that $\tau_2$ is the longest stage. Thus, $T_{old} = \tau_2$.

The longest stage, $\tau_2$, is split into two stages of equal latency, $\tau_2/2$. The new pipeline has four stages with latencies $\tau_1, \tau_2/2, \tau_2/2, \tau_3$. In terms of $\tau_2$, these are $3\tau_2/4, \tau_2/2, \tau_2/2, 3\tau_2/8$. The new longest stage is $\tau_1 = 3\tau_2/4$.
The new clock period is $T_{new} = 3\tau_2/4 = (3/4)T_{old}$.
The new frequency is $F_{new} = 1/T_{new} = (4/3)F_{old} = (4/3) \times 3 \text{ GHz} = 4 \text{ GHz}$.

In a min-heap, any node's value must be greater than or equal to its parent's value. The question asks for the maximum possible depth for the integer 9. The root is at depth 0.
To maximize the depth of the node containing 9, we must place the 8 smaller integers {1, 2, 3, 4, 5, 6, 7, 8} on the path from the root to that node.
This creates a path where each node is the parent of the next integer in the sequence:
1 (root, depth 0) $\rightarrow$ 2 (depth 1) $\rightarrow$ 3 (depth 2) $\rightarrow \dots \rightarrow$ 8 (depth 7).
The integer 9 can then be a child of 8, placing it at depth 8. This structure is valid as the min-heap property is maintained along this path.

The question asks for a loop invariant, which is a condition that holds true at the beginning of every loop iteration. Let's test the condition $X^Y = \text{res} \times a^b$.

1. Initialization: Before the loop, res = 1, a = X, b = Y. The condition is $X^Y = 1 \times X^Y$, which is true.
2. Maintenance (b is even): res is unchanged, a becomes $a^2$, b becomes $b/2$. The expression is $\text{res} \times (a^2)^{b/2} = \text{res} \times a^b$. The invariant is maintained.
3. Maintenance (b is odd): res becomes res*a, a is unchanged, b becomes b-1. The expression is $(\text{res} \times a) \times a^{b-1} = \text{res} \times a^b$. The invariant is maintained.
   Since the condition is true at the start and is preserved through each step, it is the correct loop invariant.

To find the New-order traversal, we first construct the expression tree from the given reverse polish (postfix) expression: 3 4 * 5 - 2 ^ 6 7 * 1 + -. The resulting tree has - as the root. Its left child corresponds to 3 4 * 5 - 2 ^ and its right child corresponds to 6 7 * 1 +.

The New-order traversal is defined as: (1) Visit Root, (2) Visit Right Subtree, (3) Visit Left Subtree.

Applying this to the expression tree:

1. Visit Root: -
2. Traverse Right Subtree (+ 1 * 7 6): +, then 1, then * 7 6.
3. Traverse Left Subtree (^ 2 - 5 * 4 3): ^, then 2, then - 5 * 4 3.

Combining these gives the sequence: - + 1 * 7 6 ^ 2 - 5 * 4 3.

The program calculates a value by recursively calling the function f(p, n). Let's trace the execution with the input array a = {3, 5, 2, 6, 4} and size n=5.

• f(a, 5) returns max(f(a+1, 4), a[0]-a[1]) = max(f(a+1, 4), 3-5=-2).
• f(a+1, 4) returns max(f(a+2, 3), a[1]-a[2]) = max(f(a+2, 3), 5-2=3).
• f(a+2, 3) returns max(f(a+3, 2), a[2]-a[3]) = max(f(a+3, 2), 2-6=-4).
• f(a+3, 2) returns max(f(a+4, 1), a[3]-a[4]) = max(f(a+4, 1), 6-4=2).
• f(a+4, 1) is the base case (n <= 1), so it returns 0.

Unwinding the recursion:

• The call f(a+3, 2) returns max(0, 2) = 2.
• The call f(a+2, 3) returns max(2, -4) = 2.
• The call f(a+1, 4) returns max(2, 3) = 3.
• Finally, the initial call f(a, 5) returns max(3, -2) = 3.
  The value printed is 3.

This is a matrix chain multiplication problem. We need to find the parenthesization that minimizes the number of scalar multiplications. The dimensions are $A_1: 10 \times 5$, $A_2: 5 \times 20$, $A_3: 20 \times 10$, $A_4: 10 \times 5$.

Let's evaluate the cost of the parenthesization $A_1((A_2A_3)A_4)$:

1. Cost of $(A_2A_3)$: Dimensions are $(5 \times 20)$ and $(20 \times 10)$. Multiplications = $5 \times 20 \times 10 = 1000$. The resulting matrix, let's call it $M_1$, has dimensions $5 \times 10$.
2. Cost of $(M_1A_4)$: Dimensions are $(5 \times 10)$ and $(10 \times 5)$. Multiplications = $5 \times 10 \times 5 = 250$. The resulting matrix, $M_2$, has dimensions $5 \times 5$.
3. Cost of $A_1(M_2)$: Dimensions are $(10 \times 5)$ and $(5 \times 5)$. Multiplications = $10 \times 5 \times 5 = 250$.

Total multiplications = $1000 + 250 + 250 = 1500$. This is the minimum possible cost among all parenthesizations.

The flowchart describes a recursive function A(n). In the worst-case scenario, the function makes five recursive calls to A(n/2) and performs a constant amount of work, which is O(1). This can be represented by the recurrence relation:
T(n) = 5T(n/2) + O(1)

We can solve this using the Master Theorem, T(n) = aT(n/b) + f(n). Here, a=5, b=2, and f(n) = O(1).

We compare f(n) with n^(log_b a).
n^(log_b a) = n^(log_2 5)
Since f(n) = O(1) is asymptotically smaller than n^(log_2 5), this corresponds to Case 1 of the Master Theorem. The complexity is T(n) = O(n^(log_2 5)).

The question states the complexity is $O(n^{\alpha})$, so $\alpha = \log_2 5 \approx 2.32$.

To efficiently set the twin pointers in an adjacency list, a Breadth-First Search (BFS) traversal of the graph can be used. BFS systematically explores the graph by visiting each vertex and all its adjacent edges. When traversing an edge (u, v), we can set the twin pointers for the corresponding entries in the adjacency lists of both u and v. The time complexity of a BFS algorithm on a graph represented by an adjacency list is a function of its vertices ($n$) and edges ($m$), which is $\Theta(n+m)$.

Statement I is false. If all states of an NFA are accepting, it does not guarantee that the language accepted is $\Sigma^*$. For example, if some states are unreachable from the start state, strings that would require reaching those states will not be accepted.

Statement II is true. We can choose a regular language A to be the empty language, $A = \emptyset$. For any language B, the intersection $A \cap B$ is $\emptyset \cap B = \emptyset$. The empty language is regular. Thus, there exists such a regular language A.

For language $L_1 = \{a^n b^m c^{n+m} \mid m, n \ge 1\}$, a pushdown automaton (PDA) can be constructed. The PDA can push a symbol onto the stack for each 'a', then push another symbol for each 'b'. Subsequently, for each 'c' it reads, it pops one symbol from the stack. The string is accepted if the stack is empty after all characters are read. Thus, $L_1$ is context-free.

For language $L_2 = \{a^n b^n c^{2n} \mid n \ge 1\}$, a PDA cannot be constructed. A PDA can verify one dependency (like $n$ 'a's followed by $n$ 'b's) but cannot simultaneously verify a second dependent count (that the number of 'c's is twice the number of 'a's). Therefore, $L_2$ is not context-free.

For L1 and L2, membership can be decided by a Turing Machine that always halts. We can simulate the machine M for a finite number of steps on a finite set of inputs to check if it runs for at least 2016 steps. This simulation is guaranteed to terminate, making L1 and L2 recursive languages.

L3 is the language of Turing Machines that accept the empty string, $\varepsilon$. This is a well-known undecidable problem, meaning it is not recursive. Although it is recursively enumerable, it is not recursive. Therefore, L1 and L2 are recursive, but L3 is not.

A grammar is free from left recursion if no non-terminal can derive a string that starts with itself.

• Grammar A has direct left recursion: $A \rightarrow Aa|b$.
• Grammar C has indirect left recursion: $S \Rightarrow Aa \Rightarrow Sca...$.
• Grammar D has indirect left recursion: $A \Rightarrow Bd \Rightarrow Aed...$.
• Grammar B has no productions where a non-terminal derives a string starting with itself, either directly or through a series of derivations. Therefore, it is free from left recursion.

Both grammars, G1 and G2, can correctly generate the specified C-like array declaration. For a declaration like int a[10][3];, both grammars can derive the string using their production rules.

Grammar G1 uses recursion on the right (E -> num] [E) to generate multiple dimensions.
Grammar G2 uses left recursion (E -> E[num]) to achieve the same result.

Since both grammars can produce valid multi-dimensional array declarations of at least one dimension, both are correct.

The problem is solved using the Preemptive Shortest Remaining Time First (SRTF) scheduling algorithm. The execution is as follows:

1. P1 runs from t=0 to t=3. (P1 remaining: 7)
2. P2 arrives and preempts P1. P2 runs from t=3 to t=7. (P2 remaining: 2)
3. P3 arrives and preempts P2. P3 runs from t=7 to t=8. (P3 finishes)
4. P2 resumes and runs from t=8 to t=10. (P2 finishes)
5. P4 runs from t=10 to t=13. (P4 finishes)
6. P1 runs from t=13 to t=20. (P1 finishes)

Turnaround Times (TAT = Completion Time - Arrival Time):
P1: 20-0=20, P2: 10-3=7, P3: 8-7=1, P4: 13-8=5.
Average TAT = (20+7+1+5)/4 = 33/4 = 8.25 ms.

This solution uses a turn variable for synchronization, which enforces strict alternation between Process 0 and Process 1.

1. Mutual Exclusion: Satisfied. If turn == 0, only Process 0 can enter its critical section.
2. Bounded Waiting: Satisfied. A process waits for at most one entry by the other process.
3. Progress: Violated. If Process 0 wants to enter its critical section but turn == 1, it must wait, even if Process 1 is in its remainder section and has no interest in entering its critical section. This dependency on a non-interested process violates the progress condition.

Let $S_{initial}$ be the initial value of the semaphore. There are 20 P operations (requests) and 12 V operations (signals). The total number of available signals throughout the execution is $S_{initial} + 12$.

For at least one P operation to remain blocked, the total number of requests must be greater than the total number of available signals.
$20 > S_{initial} + 12$
$S_{initial} < 20 - 12$
$S_{initial} < 8$
The largest integer value for $S_{initial}$ that satisfies this condition is 7.

The average read latency is calculated as:
Avg Latency = (Hit Rate × Cache Latency) + (Miss Rate × Disk Latency)

Given: Cache Latency = 1 ms, Disk Latency = 10 ms. We need Avg Latency < 6 ms.

Let's test the cache sizes from the graph:

• For 20 MB cache: Miss Rate ≈ 60% (0.6). Hit Rate = 40% (0.4).
  Avg Latency = (0.4 × 1) + (0.6 × 10) = 0.4 + 6 = 6.4 ms. (Too high)
• For 30 MB cache: Miss Rate ≈ 40% (0.4). Hit Rate = 60% (0.6).
  Avg Latency = (0.6 × 1) + (0.4 × 10) = 0.6 + 4 = 4.6 ms. (Less than 6 ms)

Therefore, 30 MB is the smallest cache size that meets the requirement.

A schedule is considered cascadeless if it avoids dirty reads, meaning no transaction is allowed to read data that has been written by another uncommitted transaction. In the given schedule S, we examine the read operations. Transaction $T_2$ reads X and Y, but $T_1$ has not written to them before these reads. Transaction $T_1$ reads Y, which was not written by $T_2$. Although $T_1$ writes to X, $T_2$ does not read X after this write. Since no transaction reads uncommitted data from another, the schedule is cascadeless.

The query first calculates the total capacity for each district using a common table expression (CTE) named total.

• Ajmeer: 20
• Bikaner: 10 + 10 + 20 = 40
• Churu: 10 + 20 = 30
• Dungargarh: 10
  Next, a second CTE total_avg computes the average of these summed capacities: $(20 + 40 + 30 + 10) / 4 = 25$.
  The final SELECT statement returns the names of districts where the total capacity is greater than or equal to the average capacity (25). The districts meeting this condition are Bikaner (40) and Churu (30). Thus, the query returns 2 tuples.

For CSMA/CD to function correctly, the minimum frame transmission time ($T_t$) must be at least twice the maximum signal propagation time ($T_p$). This ensures a station can detect a collision before it finishes transmitting the frame. The condition is $T_t \ge 2T_p$.
The minimum frame size (L) is calculated as $L = 2 \times T_p \times \text{Bandwidth}$.
Given:

• Bandwidth = $20 \times 10^6$ bits/second
• $T_p = 40 \mu s = 40 \times 10^{-6}$ seconds
  $L = 2 \times (40 \times 10^{-6}) \times (20 \times 10^6) = 1600$ bits.
  To convert this to bytes, we divide by 8: $1600 / 8 = 200$ bytes.

Let's analyze the statements regarding the IEEE 802.11 protocol:
I. In the commonly used 2.4 GHz band, channels 1, 6, and 11 are designed to be non-overlapping. Therefore, at least three non-overlapping channels are available. This statement is TRUE.
II. The RTS-CTS (Request to Send/Clear to Send) mechanism is part of the collision avoidance (CSMA/CA) strategy, not collision detection. Wireless devices typically cannot detect collisions while transmitting. This statement is FALSE.
III. To ensure reliable delivery, all unicast frames sent to a specific destination require an acknowledgment (ACK) from the receiver. This statement is TRUE.
Therefore, only statements I and III are true.

To achieve 100% utilization, the sender's window size (W) must be large enough to transmit continuously for one full round-trip time. The number of frames needed is $W \ge 1 + 2a$, where $a = T_p / T_t$.
First, calculate the transmission time ($T_t$):
$T_t = \frac{\text{Frame Size}}{\text{Bandwidth}} = \frac{1 \text{ KB} \times 8 \text{ bits/byte}}{128 \times 10^3 \text{ bps}} = \frac{8192 \text{ bits}}{128000 \text{ bps}} \approx 64$ ms.
Now, calculate $a$:
$a = \frac{T_p}{T_t} = \frac{150 \text{ ms}}{64 \text{ ms}} \approx 2.34$.
The required window size is $W = 1 + 2(2.34) = 5.68$. Since we must send whole frames, we need a window of at least $\lceil 5.68 \rceil = 6$.
For Selective Repeat, the window size (W) and the number of sequence bits (n) are related by $2W \le 2^n$.
$2 \times 6 \le 2^n \Rightarrow 12 \le 2^n$.
The smallest integer $n$ that satisfies this is 4, as $2^4 = 16$.