GATE CSE 2017 SET 1

The sentence describes a sequence of events that occurred in the past. Rajendra Chola first "returned" from his voyage, which is a past action. The subsequent action of his desire to visit the temple also happened in the past. The simple past tense "wished" correctly follows the past tense of the first clause, maintaining grammatical consistency.

The sentence intends to convey that people work for reasons in addition to money. The word "besides" is a preposition meaning "in addition to" or "apart from". The word "beside" means "next to" or "at the side of". Therefore, "besides" is the correct word to complete the meaning of the sentence.

Let's arrange the four people around a square table, facing the center.

1. Place Murali at the top side.
2. "Rahul is sitting to the left of Murali," so Rahul is on the left side.
3. "Srinivas is sitting to the right of Arul." For this to be true in the remaining two spots, Arul must be on the right side, which places Srinivas on the bottom side (to Arul's right).
   The final arrangement is: Murali (Top), Rahul (Left), Srinivas (Bottom), Arul (Right).
   The pairs sitting opposite each other are (Murali, Srinivas) and (Rahul, Arul).

To make a number a perfect cube, the exponents of its prime factors must all be multiples of 3. First, find the prime factorization of 162:
$162 = 2 \times 81 = 2^1 \times 3^4$.
We need to find the smallest integer $y$ such that $y \times (2^1 \times 3^4)$ is a perfect cube.
The exponent of 2 is 1; the next multiple of 3 is 3. We need to multiply by $2^{3-1} = 2^2$.
The exponent of 3 is 4; the next multiple of 3 is 6. We need to multiply by $3^{6-4} = 3^2$.
Thus, the smallest $y$ is $2^2 \times 3^2 = 4 \times 9 = 36$.

There are 10 possible digits (0 through 9). The problem states that the digits 0, 5, and 9 are not allowed. This leaves 7 allowed digits (1, 2, 3, 4, 6, 7, 8).
For a k-digit number, each of the $k$ positions is an independent event. The probability of a single digit not being 0, 5, or 9 is $\frac{7}{10}$.
Since there are $k$ digits, the probability that none of them are 0, 5, or 9 is the product of the individual probabilities:
$P = (\frac{7}{10})^k = 0.7^k$.

The author's statement implies that historical accounts of the colonial past are judged based on how well they fit a "nationalist" narrative. If an event or interpretation is not considered sufficiently "nationalist," it is dismissed and not accepted as part of history. This indicates that the lens of nationalism acts as a filter, determining what is and is not considered legitimate history.

There are at least two women, and none are right-handed, making them left-handed. Each woman has a left-handed person to her immediate right. Since there are at least three right-handed people, these must be men. If we assume there are two women, they must sit together for one to have a left-handed person (the other woman) to her right. The other woman would then need a left-handed person to her right. This can be a left-handed man. The remaining three seats are filled by right-handed men. This configuration with two women satisfies all conditions.

The solution can be found by considering two cases for the expression $|x-y|$.

Case 1: If $x \ge y$, then $|x-y| = x-y$. The expression becomes:
$\frac{(x+y) - (x-y)}{2} = \frac{2y}{2} = y$
In this case, $y$ is the minimum value.

Case 2: If $x < y$, then $|x-y| = -(x-y) = y-x$. The expression becomes:
$\frac{(x+y) - (y-x)}{2} = \frac{2x}{2} = x$
In this case, $x$ is the minimum value.

In both scenarios, the expression evaluates to the minimum of $x$ and $y$.

The problem asks for the number of ways four people can choose one shirt each from four different colored shirts, with two restrictions. We can solve this using the principle of inclusion-exclusion.

Total possible arrangements without any restrictions is $4! = 24$.

Let $C_A$ be the case where Arun gets the red shirt, and $C_S$ be the case where Shweta gets the white shirt. We need to find the number of invalid arrangements, which is $|C_A \cup C_S| = |C_A| + |C_S| - |C_A \cap C_S|$.

1. $|C_A|$: If Arun gets red, the other 3 people can be assigned the remaining 3 shirts in $3! = 6$ ways.
2. $|C_S|$: If Shweta gets white, the other 3 people can be assigned the remaining 3 shirts in $3! = 6$ ways.
3. $|C_A \cap C_S|$: If Arun gets red and Shweta gets white, the other 2 people can be assigned the remaining 2 shirts in $2! = 2$ ways.

Number of invalid ways = $6 + 6 - 2 = 10$.
Number of valid ways = Total ways - Invalid ways = $24 - 10 = 14$.

The contour plot shows lines at 25m intervals. The water level in the flood rises to 525m. Any village located at an elevation below 525m will be submerged.

• Village P is between the 500m and 550m contours.
• Village Q is above the 550m contour.
• Villages R, S, and T are all located within the area below the 500m contour line.
  Therefore, villages R, S, and T are at an elevation less than 500m and will be submerged by the 525m floodwater.

The statement $(\neg p)\Rightarrow (\neg q)$ is a conditional statement. According to the rule of contrapositive, a conditional statement is logically equivalent to its contrapositive. The contrapositive of $(\neg p)\Rightarrow (\neg q)$ is formed by swapping the hypothesis and conclusion and negating both, which results in $q \Rightarrow p$. This matches statement II.

Furthermore, any implication $A \Rightarrow B$ is logically equivalent to $(\neg A) \vee B$. Applying this to $q \Rightarrow p$, we get $(\neg q) \vee p$, which matches statement III.

The statement $F: \forall x(\exists yR(x,y))$ means "for every x, there exists some y such that R(x,y) is true".

Statement IV, $\neg \exists x(\forall y\neg R(x,y))$, is equivalent to F. By applying De Morgan's laws for quantifiers, we get $\forall x \neg (\forall y\neg R(x,y))$, which simplifies to $\forall x (\exists y R(x,y))$.

Statement I, $\exists y(\exists xR(x,y))$, is implied by F. Since for every x there is a corresponding y, the domain is non-empty, guaranteeing that there is at least one such (x,y) pair. Thus, there must exist a y and an x for which R(x,y) holds.

The condition $\sum_{i=1}^{n}c_{i}a_{i}=0$ with not all $c_i$ being zero is the definition of linear dependence for the column vectors $a_i$ of matrix A. A matrix with linearly dependent columns is singular, meaning its determinant is zero ($|A|=0$).

For a system of linear equations $Ax=b$, if the matrix A is singular, the system has either no solution or infinitely many solutions.

We are given that $b = \sum_{i=1}^{n}a_{i}$. This means that $b$ is a linear combination of the columns of A. A specific solution exists: if we take $x$ to be a vector of all ones, then $Ax = \sum a_i = b$.

Since a solution exists and the matrix A is singular, there must be infinitely many solutions.

To arrange the functions by increasing asymptotic complexity, we analyze their growth rates as $n \to \infty$.

1. $\frac{100}{n}$: Decreases towards 0.
2. $10$: A constant function.
3. $log_{2}n$: Logarithmic growth, which is slower than any polynomial.
4. $\sqrt{n} = n^{0.5}$: Polynomial growth.
5. $n = n^1$: Polynomial growth, faster than $\sqrt{n}$.

Comparing their growth rates, a decreasing function grows slowest, followed by a constant, then logarithmic, and finally polynomial functions in increasing order of their exponents. The correct order is $\frac{100}{n}, 10, log_{2}n, \sqrt{n}, n$.

The matching is based on the fundamental design strategy of each algorithm:

• P. Kruskal: This algorithm finds a Minimum Spanning Tree by iteratively adding the edge with the least weight that does not form a cycle. This is a classic example of a Greedy approach.
• Q. Quicksort: This sorting algorithm works by selecting a 'pivot' element and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This is the Divide and Conquer paradigm.
• R. Floyd-Warshall: This algorithm computes all-pairs shortest paths by considering all possible intermediate vertices for each pair of source and destination vertices. It builds the solution based on solutions to smaller subproblems, which is the essence of Dynamic Programming.

The minimum height of a binary search tree with N nodes occurs when the tree is as balanced as possible. The formula for the minimum height is $\lfloor \log_2 N \rfloor$. For N = 15 nodes, the minimum height is $\lfloor \log_2 15 \rfloor = 3$.

The maximum height occurs when the tree is completely skewed (either left-skewed or right-skewed), resembling a linked list. For N nodes, the maximum height is N-1. For N = 15 nodes, the maximum height is $15 - 1 = 14$.

The representation uses i bits for the integer part and f bits for the fractional part. Since the number is unsigned, the minimum value is 0, which occurs when all bits are 0.

The maximum value occurs when all n bits are 1. The i integer bits being all 1s represent the value $2^i - 1$. The f fractional bits being all 1s represent the value $\sum_{k=1}^{f} 2^{-k} = 1 - 2^{-f}$. The total maximum value is the sum of these two parts: $(2^i - 1) + (1 - 2^{-f}) = 2^i - 2^{-f}$. Thus, the range is from 0 to $(2^i - 2^{-f})$.

The join(m, n) function is designed to append the linked list m to the end of the linked list n.

The code first initializes a pointer p to the head of list n. The while loop then traverses list n until p points to the last node (i.e., the node whose next pointer is NULL). Finally, it sets the next pointer of this last node to m, linking the two lists.

However, there is a critical edge case. If the list n is empty, the input n will be NULL. In this scenario, p is initialized to NULL, and the subsequent attempt to access p->next will cause a null pointer dereference. Thus, the function either appends the list or causes this error.

In 2's complement addition, an overflow occurs if the sum of two positive numbers is negative, or the sum of two negative numbers is positive. A standard method for detecting this is to compare the carry-in and carry-out of the most significant bit (MSB). An overflow happens if they are different.

The expression $(A_{7}B_{7}\bar{S_{7}}+\bar{A_{7}}\bar{B_{7}}S_{7})$ correctly captures this logic. The first term, $A_{7}B_{7}\bar{S_{7}}$, is true when two negative numbers ($A_7=1, B_7=1$) produce a positive result ($S_7=0$). The second term, $\bar{A_{7}}\bar{B_{7}}S_{7}$, is true when two positive numbers ($A_7=0, B_7=0$) produce a negative result ($S_7=1$).

The grammar rules are S $\rightarrow$ abScT | abcT and T $\rightarrow$ bT | b.
First, the non-terminal T generates one or more 'b's, i.e., the language $L(T) = \{b^m | m \ge 1\}$.

The S productions build the string structure. The base case S -> abcT generates strings like abcb^{m_1}. The recursive rule S -> abScT prepends ab and appends cT around a string already generated by S. Applying the recursion n-1 times followed by the base case results in a structure of the form $(ab)^n cT (cT)...(cT)$, with n instances of cT. Since each T can independently generate a different sequence of bs ($b^{m_i}$), the final language is { $(ab)^{n}cb^{m_{1}}cb^{m_{2}}...cb^{m_{n}}|n,m_{1},...,m_{n}\geq 1$ }.

The student.grade field is located at a fixed offset from the base address of the student struct, which is stored in register R1. To access this field, the processor must calculate the memory address by adding this fixed offset to the value in R1. The index addressing mode, commonly represented as X(R1), is specifically designed for this operation. It computes the effective address by summing a constant displacement X (the offset) and the contents of a base register R1. This makes it the most efficient method for accessing struct fields.

Static Single Assignment (SSA) form is an intermediate representation property where every variable is assigned a value exactly once. In the given three-address code, variables p and q are reassigned. To convert to SSA, each new assignment must be to a new, uniquely named variable.
The correct transformation is:

1. p = a - b becomes p_3 = a - b.
2. q = p * c becomes q_4 = p_3 * c, using the new p_3.
3. p = u * v becomes p_4 = u * v.
4. q = p + q becomes q_5 = p_4 + q_4, using the new p_4 and the previous q_4.
   Option B correctly reflects this principle, assigning each result to a new variable.

The code suffers from a memory leak. Initially, the pointer x is assigned a memory address by the first malloc call. The program then enters the if block, where x is reassigned to a new memory address from a second malloc call. This reassignment overwrites the address of the first memory block. As there are no other pointers to this first block, it becomes inaccessible and cannot be deallocated. The final free(x) call only releases the second memory block, leaving the first one leaked.

The TCP connection closing sequence involves several state transitions. When the client application initiates a close, it sends a FIN segment to the server and transitions from ESTABLISHED to the FIN-WAIT-1 state. Upon receiving an ACK for its FIN from the server, the client's side of the connection is closed for sending, and it moves to the FIN-WAIT-2 state. In this state, the client waits to receive a FIN segment from the server, which indicates that the server has also finished sending its data.

A birthday attack on a digital signature involves finding two different messages, m and m', that have the same hash value. The sender (S), who possesses the private key, can exploit this. S can generate an innocent message m and a fraudulent one m', find a hash collision, and get the receiver (R) to agree to m. S then provides the signature for hash(m). Later, S can claim to have sent m', as the signature is also valid for it. A third party or the receiver cannot perform this attack because they lack the sender's private key to create a valid signature for any message.

The given set of functional dependencies is F = {V $\rightarrow$ W, VW $\rightarrow$ X, Y $\rightarrow$ VX, Y $\rightarrow$ Z}.
First, we decompose Y $\rightarrow$ VX into Y $\rightarrow$ V and Y $\rightarrow$ X.
The set becomes {V $\rightarrow$ W, VW $\rightarrow$ X, Y $\rightarrow$ V, Y $\rightarrow$ X, Y $\rightarrow$ Z}.
Since V $\rightarrow$ W, the attribute W in VW $\rightarrow$ X is extraneous. We can simplify VW $\rightarrow$ X to V $\rightarrow$ X.
The set is now {V $\rightarrow$ W, V $\rightarrow$ X, Y $\rightarrow$ V, Y $\rightarrow$ X, Y $\rightarrow$ Z}.
Now, we check for redundant dependencies. Since we have Y $\rightarrow$ V and V $\rightarrow$ X, by transitivity, Y $\rightarrow$ X holds. Therefore, Y $\rightarrow$ X is redundant and can be removed.
The final minimal cover is {V $\rightarrow$ W, V $\rightarrow$ X, Y $\rightarrow$ V, Y $\rightarrow$ Z}.

To find FOLLOW(Q), we look at the production P $\rightarrow$ xQRS. The FOLLOW set of a non-terminal is the set of terminals that can appear immediately to its right.
Here, FOLLOW(Q) includes everything in FIRST(RS).
First, we find FIRST(R). From R $\rightarrow$ w|$\varepsilon$, we get FIRST(R) = {w, $\varepsilon$}.
So, 'w' is in FOLLOW(Q).
Since R can derive $\varepsilon$ (the empty string), we must also consider what follows R, which is S. We add FIRST(S) to FOLLOW(Q).
From S $\rightarrow$ y, we get FIRST(S) = {y}.
Therefore, FOLLOW(Q) = {w, y}.

Threads within the same process operate in a shared memory space. This shared space includes the code segment, data segment (for global variables), and the heap (for dynamically allocated memory). Each thread, however, has its own separate stack for local variables and function calls, as well as its own set of registers, including the program counter. Therefore, threads of a process share both global variables and the heap.

X is a Gaussian random variable with a mean of 0. This implies its probability density function is symmetric about 0, so P(X $\le$ 0) = 0.5.
The variable Y is defined as Y = max(X, 0). This means:

• If X $\le$ 0, then Y = 0.
• If X > 0, then Y = X.
  Since P(X $\le$ 0) = 0.5, it follows that P(Y = 0) $\ge$ 0.5.
  The median is the value that separates the higher half from the lower half of a data sample. As at least 50% of the probability mass of Y is at the value 0, the median of Y must be 0.

For any tree with V vertices, the number of edges E is always V-1.
In this case, the tree T has V = 10 vertices, so it must have E = 10 - 1 = 9 edges.
The handshaking lemma states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges.
Sum of degrees = 2 * E
Substituting the number of edges, we get:
Sum of degrees = 2 * 9 = 18.

The Karnaugh map simplification is the first step. The PDF solution simplifies the function to $F(a,b,c,d) = \bar{a}c$. The question requires implementing this function using only 2-input NOR gates, and the complements of the inputs are available.

The expression $\bar{a}c$ can be rewritten for a NOR-gate implementation using De Morgan's laws:
$F = \bar{a}c = \overline{\overline{(\bar{a}c)}} = \overline{\overline{\bar{a}} + \bar{c}} = \overline{a + \bar{c}}$
Since the inputs $a$ and $\bar{c}$ are directly available, this expression can be implemented with a single 2-input NOR gate.

The regular expression is $(a+b)^*b(a+b)$. This language consists of all strings over the alphabet $\{a, b\}$ where the second-to-last symbol is 'b'. This is equivalent to the set of strings ending in 'ba' or 'bb'.

A minimal Deterministic Finite Automaton (DFA) for this language requires 4 states:

1. An initial state.
2. A state reached after reading a 'b'. This 'b' could potentially be the second-to-last symbol.
3. A final state for strings ending in 'ba'.
4. A final state for strings ending in 'bb'.

These states are necessary to keep track of the last two symbols seen to determine if the string should be accepted. The transitions ensure that the machine is in a final state only if the second-to-last symbol was 'b'.

The SQL query consists of an inner query and an outer query.

First, the inner query (SELECT DeptName, COUNT(EmpId) AS Num FROM EMP GROUP BY DeptName) calculates the number of employees in each department. Based on the provided table, the result is:

• AA: 4
• AB: 3
• AC: 3
• AD: 2
• AE: 1

The outer query SELECT AVG(EC.Num) FROM EC ... then calculates the average of the Num column from the result of this inner query (aliased as EC).

The average is calculated as the sum of the counts divided by the number of departments:
$\text{Average} = \frac{4 + 3 + 3 + 2 + 1}{5} = \frac{13}{5} = 2.6$

The Shortest Remaining Time First (SRTF) algorithm is a pre-emptive scheduling method. The execution proceeds as follows, tracked by a Gantt chart:

1. At t=0, P1 starts.
2. At t=3, P2 arrives with a burst time of 3, which is less than P1's remaining time of 4. P2 preempts P1 and runs to completion at t=6.
3. At t=6, P4 arrives with a burst time of 2, which is the shortest. P4 runs to completion at t=8.
4. At t=8, P1 (remaining time 4) resumes and finishes at t=12.
5. At t=12, P3 (burst time 5) runs and finishes at t=17.

Waiting times are: P1=5, P2=0, P3=7, P4=0.
The average waiting time is $\frac{5+0+7+0}{4} = \frac{12}{4} = 3$ ms.

An application has 1.4 memory accesses per instruction. For 1000 instructions, the total number of memory accesses is $1.4 \times 1000 = 1400$.

The L1 miss rate is 0.1. The number of L1 misses (which become accesses to L2) is $1400 \times 0.1 = 140$.

The L2 cache experiences 7 misses per 1000 instructions. The L2 miss rate is the ratio of L2 misses to L2 accesses.

L2 Miss Rate = $\frac{\text{Number of L2 misses}}{\text{Number of L2 accesses}} = \frac{7}{140} = \frac{1}{20} = 0.05$.

Statement (I) is true. A well-known property of graphs is that if all edge weights are distinct, the Minimum Spanning Tree (MST) is unique. This is because algorithms like Kruskal's or Prim's will have a unique choice for the next edge to add at every step.

Statement (II) is false. The shortest path between two vertices is not necessarily unique, even if all edge weights are distinct. The provided PDF solution gives a counterexample where two different paths, B-A-C and B-C, have the same total weight of 3, demonstrating that multiple shortest paths can exist.

A deadlock requires a circular wait condition, which involves multiple threads and multiple resources (locks).

• With only one thread (x=1), a deadlock cannot occur as there is no other thread to create a circular dependency with.
• With only one lock (y=1), a deadlock is also not possible. One thread will acquire the lock, and any other threads will simply wait for it to be released. No circular wait can be formed.
  The minimum condition for a deadlock is with two threads (x=2) and two locks (y=2). A deadlock occurs if Thread 1 acquires Lock 1 and waits for Lock 2, while Thread 2 acquires Lock 2 and waits for Lock 1.

Directly substituting $x=1$ into the expression gives the indeterminate form $\frac{1-2(1)+1}{1-3(1)+2} = \frac{0}{0}$.
To resolve this, we can apply L'Hôpital's Rule by taking the derivative of the numerator and the denominator with respect to $x$.
The derivative of the numerator is $7x^6 - 10x^4$.
The derivative of the denominator is $3x^2 - 6x$.
Now, we evaluate the limit of the new expression:
$\lim_{x\rightarrow 1}\frac{7x^{6}-10x^{4}}{3x^{2}-6x} = \frac{7(1)^{6}-10(1)^{4}}{3(1)^{2}-6(1)} = \frac{7-10}{3-6} = \frac{-3}{-3} = 1$

The expression $(p \rightarrow q) \rightarrow r$ is a contradiction, meaning it is always False. An implication $A \rightarrow B$ is False only when $A$ is True and $B$ is False.
Therefore, we must have:

1. $(p \rightarrow q)$ is True.
2. $r$ is False.

Now, we evaluate the expression $(r \rightarrow p) \rightarrow q$ under these conditions.
Since $r$ is False, the antecedent $(r \rightarrow p)$ is always True (as False implies anything).
The expression simplifies to $(T \rightarrow q)$, which is logically equivalent to $q$.
Thus, the value of the expression is the same as the value of $q$. This means the expression is always TRUE when q is TRUE.

A vector $w$ bisects the angle between two vectors $u$ and $v$ if it is in the same direction as the sum of their unit vectors. The unit vectors are $\hat{u} = \frac{u}{||u||}$ and $\hat{v} = \frac{v}{||v||}$.
So, $w$ must be proportional to $\hat{u} + \hat{v}$.
$w = k \left( \frac{u}{||u||} + \frac{v}{||v||} \right)$
We are given $w = u + \alpha v$. Equating the two expressions:
$u + \alpha v = \frac{k}{||u||}u + \frac{k}{||v||}v$
By comparing the coefficients of $u$, we get $1 = \frac{k}{||u||}$, so $k = ||u||$.
By comparing the coefficients of $v$, we get $\alpha = \frac{k}{||v||} = \frac{||u||}{||v||}$.
Given that $||u|| = 2||v||$, we can substitute this in:
$\alpha = \frac{2||v||}{||v||} = 2$

The sum of the squares of all elements of a real symmetric matrix A is equal to the sum of the squares of its eigenvalues, i.e., $\sum_{i,j} A_{ij}^2 = \sum_k \lambda_k^2$. We are given this sum is 50.

The rank of the matrix is 2, which means it has exactly two non-zero eigenvalues, say $\lambda_1$ and $\lambda_2$. All other $n-2$ eigenvalues are 0. Thus, $\lambda_1^2 + \lambda_2^2 = 50$.

(I) Since $n-2$ eigenvalues are 0 (assuming $n \ge 2$), and 0 is within the interval [-5, 5], at least one eigenvalue is in this range. So, statement (I) is true.

(II) Consider the case where $\lambda_1 = 5$ and $\lambda_2 = 5$. Then $\lambda_1^2 + \lambda_2^2 = 25 + 25 = 50$. The largest magnitude is 5, which is not strictly greater than 5. Therefore, statement (II) is not necessarily true.

The generator polynomial $x^{3+}x+1$ corresponds to the divisor bit string 1011. The degree of the polynomial is 3.

To find the check bits, we append 3 zeros to the message 01011011, resulting in 01011011000. We then perform binary division (using XOR for subtraction) of this appended message by the divisor 1011.

The long division process shown in the PDF yields a remainder of 101. These three bits are the check bits.

The final transmitted message is the original message with the check bits appended: 01011011101.

Let the T flip-flop output be $Q_1$ and the D flip-flop output be $Q_0$. The circuit connections give the next-state equations:
$Q_1(t+1) = Q_1(t) \oplus T_{\in} = Q_1(t) \oplus Q_0(t)$
$Q_0(t+1) = D_{\in} = Q_1(t)$

We trace the states for each clock cycle, starting from the initial state $Q_1Q_0 = 11$:

• Initial: $Q_1Q_0 = 11$
• After 1st cycle: $Q_1 = 1 \oplus 1 = 0$, $Q_0 = 1$. State: 01.
• After 2nd cycle: $Q_1 = 0 \oplus 1 = 1$, $Q_0 = 0$. State: 10.
• After 3rd cycle: $Q_1 = 1 \oplus 0 = 1$, $Q_0 = 1$. State: 11.
• After 4th cycle: $Q_1 = 1 \oplus 1 = 0$, $Q_0 = 1$. State: 01.

The outputs $Q_1Q_0$ after the 3rd cycle are 11, and after the 4th cycle are 01.

Let's analyze the production rules to understand the property of the language generated.

• $S \rightarrow aSb$ and $S \rightarrow bSa$ each add one 'a' and one 'b'.
• $S \rightarrow SaS$ adds two 'a's and zero 'b's.
• $S \rightarrow SS$ concatenates strings that follow the property.
• $S \rightarrow \epsilon$ is the base case.

Every production rule generates a string where the number of 'a's is greater than or equal to the number of 'b's, i.e., $n(a) \ge n(b)$.

Now, we check the options against this property:

• A. abab: $n(a)=2, n(b)=2$. Possible.
• B. aaab: $n(a)=3, n(b)=1$. Possible.
• C. abbaa: $n(a)=3, n(b)=2$. Possible.
• D. babba: $n(a)=2, n(b)=3$. Not possible, as $n(a) < n(b)$.

This problem requires tracing the execution of two mutually recursive functions. The call sequence starting with fun1(5) is as follows:

• fun1(5) prints 5, calls fun2(3).
• fun2(3) prints 3, calls fun1(4).
• fun1(4) prints 4, calls fun2(2).
• fun2(2) prints 2, calls fun1(3).
• fun1(3) prints 3, calls fun2(1).
• fun2(1) prints 1, calls fun1(2).
• fun1(2) prints 2, calls fun2(0) which returns, then prints 2 again.
  As the function calls return, the second printf statement in each function's body is executed. Tracing the entire sequence of prints gives the output 53423122233445.

The function foo(val) contains the recursive call foo(val--). The post-decrement operator means foo is called with the same value of val repeatedly, leading to infinite recursion. This will exhaust the call stack and cause an abnormal program termination (stack overflow).

The function bar(val) contains the recursive call bar(val-1). This recursion has a base case when val becomes 0. However, the recursive call is inside a while(val > 0) loop. The value of val is never modified within the loop's scope, so once the recursion returns, the while condition remains true, and the function enters an infinite loop.

First, let's determine the languages generated by the grammars.
The non-terminal T generates the language $L(T) = \{c^m | m \ge 0\}$, which is $c^*$.

For $G_1: S \rightarrow aSb | T$. This generates strings where a's are matched with b's, with a string from $L(T)$ in the middle. So, $L(G_1) = \{a^n c^m b^n | n, m \ge 0\}$.

For $G_2: S \rightarrow bSa | T$. This generates strings where b's are matched with a's. So, $L(G_2) = \{b^n c^m a^n | n, m \ge 0\}$.

The intersection $L(G_1) \cap L(G_2)$ contains strings that belong to both languages. A string must have the form $a^n c^m b^n$ and $b^p c^q a^p$. This is only possible if the number of a's and b's is zero ($n=p=0$). Thus, the intersection is the language $\{c^m | m \ge 0\}$. This language is represented by the regular expression $c^*$, which is infinite and regular.

I. $L_1 \cup L_2$: The union of two context-free languages is always context-free. We can construct a new grammar with a new start symbol $S'$ such that $S' \rightarrow S_1 | S_2$, where $S_1$ and $S_2$ are the start symbols for grammars generating $L_1$ and $L_2$. Thus, $L_1 \cup L_2$ is context-free. Statement I is true.

II. $L_1 \cap L_2$: The intersection of two CFLs is not guaranteed to be a CFL. Let's find the intersection. A string in the intersection must be of the form $a^n b^n c^m$ (from $L_1$) and also $a^p b^q c^q$ (from $L_2$). For a string to satisfy both forms, we must have $n=q$ and $m=q$. This implies $n=m=q$. The resulting language is $\{a^n b^n c^n | n \ge 0\}$, which is a classic example of a language that is not context-free. Statement II is false.

A function $f$ is computable if there is a Turing Machine (TM) that halts on every input $x$ and produces $f(x)$. A language $L$ is recursive if there is a TM (a decider) that halts on every input, accepting strings in $L$ and rejecting strings not in $L$.

1. If $f$ is computable, we can construct a decider for $L_f = \{x\#f(x)|x \in A^*\}$. Given an input $w$, the decider first checks if it has the form $x\#y$. If so, it computes $f(x)$ (which is guaranteed to halt) and compares the result with $y$. This process always halts, so $L_f$ is recursive.

2. If $L_f$ is recursive, we can construct a TM to compute $f(x)$. Given an input $x$, this TM can enumerate all possible strings $y \in B^*$ and for each, it uses the decider for $L_f$ to check if $x\#y \in L_f$. Since $f$ is a total function, this search is guaranteed to find the unique correct $y$ and halt. Thus, $f$ is computable.

Therefore, $f$ is computable if and only if $L_f$ is recursive.

S1: Random page replacement algorithm can suffer from Belady's anomaly. The random choice of a page to evict does not guarantee that an optimal or near-optimal choice is made. It is possible to construct a reference string where, with more frames, a series of "unlucky" random choices leads to more page faults than with fewer frames. Therefore, S1 is true.

S2: LRU (Least Recently Used) page replacement algorithm is a stack algorithm. A key property of stack algorithms is that the set of pages in memory with $k$ frames is always a subset of the set of pages in memory with $k+1$ frames. This property ensures that increasing the number of frames will never increase the number of page faults. Thus, LRU does not suffer from Belady's anomaly. Therefore, S2 is false.

A query in tuple relational calculus is considered "safe" if it is guaranteed to produce a finite set of tuples as its result. Unsafe queries can potentially generate infinite results, often due to negations over infinite domains or lack of sufficient constraints.

In this problem, all three queries are constrained by the tuples that exist within the EMP and DEPT relations. Since these base relations are finite, any result derived from them will also be finite. Therefore, all three queries are safe.

The given algorithm is a variant of the Wound-Wait deadlock prevention scheme. An older transaction (smaller timestamp) "wounds" (kills) a younger transaction that holds a required lock. A younger transaction waits for an older one.

1. Deadlock-Free: A circular wait condition $T_1 \rightarrow T_2 \rightarrow \dots \rightarrow T_1$ cannot occur. In this scheme, a transaction can only wait for an older transaction. A cycle would imply $TS(T_1) > TS(T_2) > \dots > TS(T_1)$, which is a contradiction. Thus, the system is deadlock-free.

2. Starvation-Free: When a transaction is killed, it is restarted with its original (old) timestamp. As it ages, it will eventually become the oldest transaction in any conflict and will no longer be killed. It will eventually acquire all necessary locks and complete, preventing starvation.

The grammar rule stmt → if expr then expr else expr defines a control structure with two distinct branches: the then path and the else path. Each if statement in the program effectively doubles the number of possible execution paths.

If a program contains $n$ independent if-then-else statements, the total number of control flow paths is $2^n$. For a program with ten if terminals, the total number of paths is:
$2^{10} = 1024$

To find the private key $d$ in the RSA algorithm, we follow these steps:

1. Calculate the modulus $n = p \times q$.
   $n = 13 \times 17 = 221$.
2. Calculate Euler's totient function $\phi(n) = (p-1)(q-1)$.
   $\phi(n) = (13-1)(17-1) = 12 \times 16 = 192$.
3. The private key $d$ is the modular multiplicative inverse of the public key $e=35$ modulo $\phi(n)$. We need to solve the congruence:
   $e \cdot d \equiv 1 \pmod{\phi(n)} \implies 35d \equiv 1 \pmod{192}$.
4. By testing the options, we check $d=11$:
   $35 \times 11 = 385$.
   $385 \pmod{192} = (2 \times 192 + 1) \pmod{192} = 1$.
   The congruence holds, so the private key is 11.

The efficiency of the Stop-and-Wait protocol is the ratio of the time spent transmitting the useful data frame to the total time for one cycle.

1. Transmission time of data frame ($T_x$):
   Frame size = 1980 (info) + 20 (overhead) = 2000 bytes.
   $T_x = \frac{2000 \text{ bytes} \times 8 \text{ bits/byte}}{1 \times 10^6 \text{ bps}} = 16 \text{ ms}$.

2. Transmission time of ACK frame ($T_{ack}$):
   $T_{ack} = \frac{20 \text{ bytes} \times 8 \text{ bits/byte}}{1 \times 10^6 \text{ bps}} = 0.16 \text{ ms}$.

3. Total cycle time: This includes data transmission, round-trip propagation, processing, and ACK transmission.
   Total time = $T_x + 2 \times T_p + T_{proc} + T_{ack}$
   Total time = $16 + 2(0.75) + 0.25 + 0.16 = 17.91 \text{ ms}$.

4. Efficiency ($\eta$):
   $\eta = \frac{T_x}{\text{Total time}} = \frac{16}{17.91} \approx 0.8933$.
   In percentage, the efficiency is 89.33%.