GATE CSE 2019

The phrasal verb "breaks down" means to divide a total amount into its constituent parts. In this context, the total project expenditure is being itemized into categories like equipment, salaries, and contingency. The subject "expenditure" is singular, so the correct verb form is "breaks down".

The word "fulcrum" signifies a central or pivotal point. The verb "revolves" means to be centered or focused on something. In the given sentence, the business model is centered on the "fulcrum of trust." Therefore, "revolves" is the most fitting word to describe this relationship, indicating that trust is the central element of the business model.

Since both cars are moving in the same direction, their relative speed is the difference between their individual speeds, which is $60 - 50 = 10$ km/h. To find the time it takes for the distance between them to become 20 km, we use the formula Time = Distance / Speed. This gives Time = $\frac{20 \text{ km}}{10 \text{ km/h}} = 2$ hours.

Let the original share for each of the 10 friends be $x$. The total cost of the gift is $10x$. When two friends do not contribute, the remaining 8 friends each pay $x + 150$. The total cost can also be expressed as $8(x + 150)$. By equating the two expressions for the total cost, we get $10x = 8(x + 150)$. Solving this equation gives $2x = 1200$, so $x = 600$. The total cost of the gift is $10 \times 600 = 6000$ Rs.

The question presents an analogy based on a person and their primary workplace. A "judge" works in a "court". Following this relationship, we need to identify the primary workplace for a "teacher". Among the given options, a "school" is the place where a teacher works.

We test the scenario where only one statement is true and only one person is the criminal. Let's assume S's statement is the only true one.

• S's statement is true: "What Q said about me is false." This means S is not the criminal.
• P's statement is false: "Q committed the crime" is false, so Q is not the criminal.
• Q's statement is false: "S committed the crime" is false, which is consistent with S's true statement.
• R's statement is false: "I did not do it" is false, which means R committed the crime.
  This scenario results in a single criminal (R) and a single true statement (S's), satisfying all conditions.

From the Venn diagram, the number of administrators is the sum of all values within the rectangle: $10 + 20 + 20 = 50$. The total number of people is the sum of all distinct values in the diagram: $70 + 10 + 20 + 20 + 40 = 160$. The percentage of administrators is calculated as $(\frac{\text{Administrators}}{\text{Total People}}) \times 100 = (\frac{50}{160}) \times 100 = 31.25\%$. This percentage falls within the range of 31 to 45.

The passage explicitly states that begging should be regarded as a "symptom" and that the "underlying disease is the failure of the state to protect citizens who fall through the social security net." This directly supports the inference that the lack of a social safety net, or social welfare schemes, is the root cause of people begging.

The total number of students in at least one club is the sum of all disjoint regions in the Venn diagram: $60 + 80 + 30 + (40-2) + (12-2) + (7-2) + 2 = 225$. The problem states that 75% of students are not in any club, which means these 225 students constitute the remaining 25% of the college population. If 25% of the total students is 225, then the total number of students is $225 / 0.25 = 900$.

We must satisfy three requests:

1. Z wants the South-West wing.
2. X wants to avoid wings next to a garden (East and West wings).
3. Y wants to be as far from the washrooms (WR) as possible.
   Option (d) places Z in the South-West room. It places X in the South wing, which is not adjacent to a garden. It places Y in the South-East room, which is diagonally opposite a washroom, making it one of the farthest locations. All three requests are satisfied.

The main memory address is 32 bits long. The block size is 16 bytes, so the number of bits required for the word offset is $\log_2(16) = 4$ bits. In a fully associative cache, the entire cache is treated as a single set. This means there are no index bits needed to select a set (Index bits = 0). The remaining bits of the address are used for the tag. Therefore, the number of tag bits is $32 - (\text{index bits}) - (\text{offset bits}) = 32 - 0 - 4 = 28$ bits.

The chip select (CS) signal is generated by an AND gate with inputs $A_{15}, A_{14}, \overline{A_{13}}, \overline{A_{12}},$ and $A_{11}$. For the chip to be selected, CS must be high, which requires all inputs to the AND gate to be 1. This condition is met when $A_{15}=1, A_{14}=1, A_{13}=0, A_{12}=0,$ and $A_{11}=1$. The remaining 11 address lines ($A_{10}$ to $A_0$) can vary.
The starting address is when $A_{10}-A_0$ are all 0s: $1100100000000000_2 = \text{C800}_{16}$.
The ending address is when $A_{10}-A_0$ are all 1s: $1100111111111111_2 = \text{CFFF}_{16}$.

LR parsers are a class of bottom-up parsers. Bottom-up parsing constructs a parse tree for an input string beginning at the leaves (the input string) and working up towards the root (the start symbol). This process is equivalent to performing a rightmost derivation of the string in reverse.

To find the 16-bit 2's complement representation of -28, we first find the 16-bit binary representation of +28, which is 0000 0000 0001 1100. Next, we find the 1's complement by inverting all the bits, which gives 1111 1111 1110 0011. Finally, we add 1 to the 1's complement to get the 2's complement: 1111 1111 1110 0100.

The set A contains pairs (x, X) where X is a non-empty subset of U and x is an element of X. We can find the size of A by summing over all possible subset sizes, k. For a given k, there are $\binom{n}{k}$ subsets of size k. For each such subset, there are k choices for the element x. Thus, $|A| = \sum_{k=1}^{n} k \binom{n}{k}$, which validates statement II. By the combinatorial identity $\sum_{k=1}^{n} k \binom{n}{k} = n2^{n-1}$, statement I is also true. Therefore, both statements are correct.

We check the validity of each identity.
(a) $(xy + x'y')'$ is the negation of XNOR, which is XOR ($x \oplus y$). This is valid.
(c) The XOR operator is associative, so $(x \oplus y) \oplus z = x \oplus (y \oplus z)$ is a standard identity. This is valid.
(d) The minterm expansion of the left side, $(x+y) \oplus z$, is $\Sigma m(1,2,4,6)$. The minterm expansion of the right side, $x \oplus (y+z)$, is $\Sigma m(1,2,3,4)$. Since the minterm expansions are not equal, this identity is invalid.

Regular languages are closed under concatenation, reversal, prefix, and suffix operations. Therefore, the languages in options (a), (c), and (d) are guaranteed to be regular if L is regular. However, the language $\{ww^R | w \in L\}$ is not necessarily regular. For instance, if L is the regular language $(a+b)^*$, the resulting language $\{ww^R | w \in (a+b)^*\}$ is a classic example of a non-regular language. It requires unbounded memory to match $w$ with its reverse, which a finite automaton cannot provide.

In an n-bit sign-magnitude representation, the largest possible magnitude is $2^{n-1}-1$. The operation $Z = X - Y$ can result in a magnitude that is the sum of the magnitudes of X and Y. The maximum possible magnitude of Z is $(2^{n-1}-1) + (2^{n-1}-1) = 2^n - 2$. To represent such a large magnitude, more than $n-1$ bits may be needed. For example, if $n=4$, let $X=+6$ and $Y=-5$. Then $Z = X-Y = 11$. Representing magnitude 11 ($1011_2$) requires 4 bits, so Z requires a total of $1+4=5$ bits, which is $n+1$ bits.

According to a fundamental theorem in linear algebra, a square matrix X has a multiplicative inverse (i.e., is invertible) if and only if its determinant is non-zero. The two conditions are defining properties of each other. Therefore, the statement "X is invertible" and the statement "Determinant of X is non-zero" are logically equivalent.

For relation R1 (conjugacy, $a=g^{-1}bg$): It is reflexive ($a=e^{-1}ae$), symmetric (if $a=g^{-1}bg$, then $b=(g^{-1})^{-1}a(g^{-1})$), and transitive (if $a=g_1^{-1}bg_1$ and $b=g_2^{-1}cg_2$, then $a=(g_2g_1)^{-1}c(g_2g_1)$). Thus, R1 is an equivalence relation.
For relation R2 ($a=b^{-1}$): It is not reflexive, because $a=a^{-1}$ is not true for all elements in an arbitrary group. Since it is not reflexive, it cannot be an equivalence relation.

I. Strict Two-Phase Locking (2PL) ensures conflict serializability. By holding all exclusive locks until a transaction commits, it also prevents other transactions from reading uncommitted data, thus ensuring schedules are strict and recoverable. This statement is true.
II. The Timestamp-Ordering protocol with Thomas' Write Rule can ignore an obsolete write operation. This can lead to a schedule that is not conflict serializable but is still view serializable to an equivalent serial schedule. This statement is also true.

In a complete graph on $n$ vertices, we can form a Hamiltonian cycle by choosing a permutation of the vertices. There are $n!$ permutations. Since the starting vertex of a cycle is arbitrary, we divide by $n$, leaving $(n-1)!$ possibilities. Furthermore, since the direction of traversal does not create a distinct cycle (e.g., A-B-C-A is the same as A-C-B-A), we divide by 2. This gives the total number of distinct Hamiltonian cycles as $\frac{(n-1)!}{2}$.

Directly substituting $x=3$ into the expression $\frac{x^{4-}81}{2x^{2-}5x-3}$ results in the indeterminate form $\frac{0}{0}$. We can apply L'Hôpital's Rule by taking the derivative of the numerator and the denominator. The derivative of the numerator is $4x^3$, and the derivative of the denominator is $4x-5$. The limit is now $\lim_{x \to 3}\frac{4x^3}{4x-5}$. Evaluating this at $x=3$ gives $\frac{4(3^3)}{4(3)-5} = \frac{108}{7}$.

In a $B^+$ tree structure, pointers to actual data records are stored only in the leaf nodes. The non-leaf (internal) nodes contain only key values and pointers to other child nodes in the tree. These pointers in non-leaf nodes are used to navigate the tree structure to find the correct leaf node. Therefore, the statement that non-leaf nodes have pointers to data records is incorrect.

The language is $L = \{a^2, a^5, a^8, ...\} \cup \{b^{10}, b^{22}, b^{34}, ...\}$. According to the pumping lemma, for any string $w \in L$ with $|w| \ge p$ (the pumping length), $w$ can be pumped. The string $b^{10}$ is in L and has length 10. This string cannot be broken down into $xyz$ and pumped according to the lemma's rules. Therefore, the pumping length $p$ must be greater than 10. Any integer $p \ge 11$ can serve as a valid pumping length. From the given options, only 24 satisfies this condition.

The Simple Mail Transfer Protocol (SMTP) is the standard internet protocol for sending (pushing) electronic mail. The Post Office Protocol 3 (POP3) is a standard protocol used by email clients to retrieve (pull) email from a remote server. Therefore, to send and then retrieve e-mails, the correct protocol pair in that order is SMTP, POP3.

The fork() system call is executed within the loop when i is even, which occurs for i = 0, 2, 4, 6, 8. This means fork() is called 5 times. Each time fork() is executed, every existing process creates a new child process, effectively doubling the total number of processes. Starting with one initial process, after 5 fork operations, the total number of processes becomes $2^5 = 32$. The number of child processes is the total final count minus the one original parent process, which is $32 - 1 = 31$.

1. Initially in main, x = 2 and y = 5.
2. The first call is y = jumble(y, x), which is jumble(5, 2). The function calculates 2*5 + 2 = 12 and returns it. The value of y in main is updated to 12.
3. The second call is x = jumble(y, x), which is now jumble(12, 2). The function calculates 2*12 + 2 = 26 and returns it. The value of x in main is updated to 26.
4. Finally, printf prints the current value of x, which is 26.

To compute FOLLOW(B), we analyze the grammar.

1. From the production A -> BD, everything in FIRST(D) (excluding ε) is in FOLLOW(B). Since FIRST(D) = {d, ε}, we add d to FOLLOW(B).
2. Because D can derive ε, everything in FOLLOW(A) is also in FOLLOW(B).
3. From the production S -> Aa, the terminal a immediately follows A, so a is in FOLLOW(A).
4. Combining these results, FOLLOW(B) = {d, a}.
5. The given indices are a=3 and d=1. Arranging these indices in descending order gives 31.

In quicksort, the worst-case partitioning for the first round occurs if the chosen pivot is either the smallest or the largest element in the array. This results in one partition of size $n-1$ and one of size 0. For an array of 25 distinct elements, there are exactly two such elements (the minimum and the maximum). Since the pivot is chosen uniformly at random from the 25 elements, the probability of selecting one of these two specific elements is $\frac{2}{25} = 0.08$.

We need to compute $3^{51} \pmod{5}$. Since 5 is a prime number, we can apply Fermat's Little Theorem, which states $a^{p-1} \equiv 1 \pmod{p}$. For $a=3$ and $p=5$, we have $3^{4} \equiv 1 \pmod{5}$. We can rewrite the exponent 51 as $51 = 4 \times 12 + 3$.
Therefore, $3^{51} = (3^4)^{12} \cdot 3^3$.
Taking this modulo 5:
$3^{51} \pmod{5} \equiv (1)^{12} \cdot 3^3 \pmod{5} \equiv 1 \cdot 27 \pmod{5} \equiv 2$.

The set of numbers is {1, 2, ..., 13}. In 4-bit unsigned binary representation:

• Numbers from 1 to 7 have a Most Significant Bit (MSB) of 0. There are 7 such numbers.
• Numbers from 8 to 13 have an MSB of 1. There are 6 such numbers.
  The probability that two independently chosen numbers both have an MSB of 0 is $(\frac{7}{13}) \times (\frac{7}{13}) = \frac{49}{169}$.
  The probability that both have an MSB of 1 is $(\frac{6}{13}) \times (\frac{6}{13}) = \frac{36}{169}$.
  The total probability of having the same MSB is the sum of these probabilities: $\frac{49}{169} + \frac{36}{169} = \frac{85}{169} \approx 0.503$.

The initial value of D is 100. The operations are D+20, D-50, and D+10.
To find the maximum value (Y), we can have a sequence where additions complete before the subtraction begins. For example: P1 runs (D becomes 120), then P3 runs (D becomes 130). This gives Y=130.
To find the minimum value (X), we can have all processes read the initial value D=100, and have the subtraction process write its result last. P1 reads 100, P2 reads 100, P3 reads 100. Then P1 writes 120, P3 writes 110, and finally P2 writes 50. The final value is X=50.
The value of Y-X is $130 - 50 = 80$.

The pointer ip is initialized with arr + 4, making it point to the element at index 4 of the array arr. The value at arr[4] is 5. The expression ip[1] is equivalent to *(ip + 1). This accesses the element at the memory location immediately after ip, which corresponds to the element at index 5 of the array. The value at arr[5] is 6. Therefore, the program prints 6.

This is the maximum subarray sum problem. We can use Kadane's algorithm to find the solution. We iterate through the array, maintaining the maximum sum of a subarray ending at the current position.
The subarray with the maximum sum starts at index 2 (value 6) and ends at index 11 (value 12).
The subarray is [6, 3, -1, -2, 13, 4, -9, -1, 4, 12].
The sum of these elements is $6+3-1-2+13+4-9-1+4+12 = 29$.

When the function convert is called with a positive integer n, the else block is executed, which contains the recursive call convert(n/2). The base case for the recursion is n < 0. However, integer division of a positive number by 2 will always result in a non-negative number, eventually reaching 0. The call convert(0) will then recursively call convert(0) indefinitely, as 0 is not less than 0. This leads to infinite recursion and a stack overflow. Since the printf statement is after the recursive call, it is never reached. Thus, the function will not print anything and will not terminate.

The function r() uses a static integer num initialized to 7 and performs a post-decrement. The for loop for(r();r();r()) executes as follows:

1. Initialization: r() is called, returns 7. num becomes 6.
2. Condition 1: r() is called, returns 6 (true). num becomes 5.
3. Body 1: printf calls r(). It returns 5, so "5" is printed. num becomes 4.
4. Update 1: r() is called, returns 4. num becomes 3.
5. Condition 2: r() is called, returns 3 (true). num becomes 2.
6. Body 2: printf calls r(). It returns 2, so "2" is printed. num becomes 1.
7. Update 2: r() is called, returns 1. num becomes 0.
8. Condition 3: r() is called, returns 0 (false). The loop terminates.
   The final output is "52".

To determine if the machines are on the same subnet, we perform a bitwise AND between each IP address and the subnet mask (255.255.255.252). The result is the subnet ID.

• M (100.10.5.2) AND (255.255.255.252) = 100.10.5.0
• N (100.10.5.5) AND (255.255.255.252) = 100.10.5.4
• P (100.10.5.6) AND (255.255.255.252) = 100.10.5.4
  Machines N and P have the same subnet ID (100.10.5.4), while M has a different one. Therefore, only N and P belong to the same subnet.

To find the MAC address of a machine Y within the same local subnet, machine X utilizes the Address Resolution Protocol (ARP). X constructs an ARP request packet containing Y's IP address and broadcasts this packet to the entire local network. This is achieved by using the special broadcast MAC address (FF:FF:FF:FF:FF:FF) as the destination in the Ethernet frame. All devices on the subnet receive the broadcast, but only machine Y, upon recognizing its own IP address in the ARP request, will send an ARP reply directly back to X, providing its MAC address.

The output of the AND gate is the logical AND of functions $f_1$ and $f_2$. In terms of minterms, this corresponds to the intersection of their minterm sets: $f_1 \cdot f_2 = \Sigma(0,2,5,8,14) \cap \Sigma(2,3,6,8,14,15) = \Sigma(2,8,14)$. The final output $f$ is the XOR of this result with $f_3$. The XOR operation on minterm sets is equivalent to their symmetric difference. Thus, $f = \Sigma(2,8,14) \oplus \Sigma(2,7,11,14) = \Sigma(7,8,11)$.

The language $L = \{wa^nw^Rb^n|w \in \{a,b\}^*,n\geq 0\}$ is not context-free. A pushdown automaton (PDA) would need to verify two independent correlations: matching the substring $w$ with its reverse $w^R$, and matching the count of $a$'s with the count of $b$'s. A single stack cannot handle both tasks. For instance, after pushing $w$ and then the $a$'s onto the stack, the top of the stack would contain the $a$'s, making it impossible to first verify $w^R$. This requires more computational power than a PDA can provide.

The decomposition of schema X(PQRS) results in Y(PR) and Z(QRS).

1. For schema Z(QRS) with FDs {QR→S, S→Q}, the candidate keys are QR and RS. The dependency S→Q violates BCNF because S is not a superkey. Therefore, statement I, which claims both are in BCNF, is false.
2. The decomposition is lossless because the common attribute between Y and Z is R, and R is the candidate key of schema Y(PR). The decomposition is also dependency preserving as all original FDs {R→P}, {QR→S}, and {S→Q} are maintained within Y or Z. Therefore, statement II is true.

The page size is 8 kB ($2^{13}$ bytes) and the word size is 4 bytes ($2^2$ bytes). This means each page contains $2^{13} / 2^2 = 2^{11}$ words. The Translation Look-aside Buffer (TLB) has 128 entries, so it can store mappings for 128 different pages simultaneously. The maximum number of distinct virtual addresses that can be translated without a TLB miss is the total number of words in all the pages mapped by the TLB. This is calculated as (number of TLB entries) $\times$ (words per page) = $128 \times 2^{11} = 2^7 \times 2^{11} = 2^{18}$. This value is equivalent to $256 \times 2^{10}$.

S1 (recursively enumerable languages) and S2 (syntactically valid C programs) are both countably infinite. This is because the set of all Turing machines is countable, and both these sets can be put into a one-to-one correspondence with Turing machines.
S3 (all languages over {0, 1}) is the power set of $\Sigma^*$. Since $\Sigma^*$ is countably infinite, its power set is uncountable.
S4 (all non-regular languages) is also uncountable. This is because the set of all regular languages is countable, and subtracting a countable set from the uncountable set of all languages (S3) results in an uncountable set.

The logical formula states that for any prime number $x$ in a given set, there must exist another prime number $w$ in the same set such that $w > x$.

• For S1 ({1, 2, ..., 100}), the statement is false. If we take the prime number $x=97$, there is no larger prime number within the set S1.
• For S2 (set of all positive integers) and S3 (set of all integers), the statement is true. Euclid's theorem proves that there are infinitely many prime numbers. Therefore, for any prime $x$, there is always a larger prime $w$ in these sets.

The grammar describes type declarations where type information is an inherited attribute, flowing down the parse tree.

• In the production D → T L, the type determined by T must be passed to the list L. The corresponding semantic action is L.type = T.type. This implies $X_1=L$ and $X_2=T$.
• In the production L → L₁, id, the type of the list L must be passed down to the sublist L₁. The action is L₁.type = L.type. This implies $X_3=L_1$ and $X_4=L$.
  These assignments match the choices in option A.

The task is to compute the median of medians from $n$ arrays, each of size $n$.

1. First, we must find the median of each of the $n$ arrays. Since the arrays are unsorted, finding the median of a single array of size $n$ takes $O(n)$ time using a selection algorithm like Quickselect. Repeating this for all $n$ arrays gives a total time complexity of $n \times O(n) = O(n^2)$.
2. After the first step, we have a new array containing $n$ medians. Finding the median of this array takes $O(n)$ time.
   The overall worst-case time complexity is dominated by the first step, which is $O(n^2)$.

Both statements describe conditions for a unique Minimum Spanning Tree (MST).
I. This is a standard theorem in graph theory. If all edge weights in a connected, undirected graph are distinct, then the graph has exactly one MST. Algorithms like Kruskal's or Prim's will have no ties to break when choosing the next edge, leading to a unique result. This statement is true.
II. This statement is based on the cut property of MSTs. If for every possible cut (a partition of vertices into two disjoint sets), there is a unique edge with the minimum weight crossing that cut, then the MST must be unique. This statement is also true.

Processes $p$ and $q$ have a maximum additional need of 0 ($Y_p=Y_q=0$), so they can finish execution. Upon completion, they will release their currently held resources, $X_p$ and $X_q$. The total number of available resources in the system will then become $X_p + X_q$. For no other process $k$ to be able to complete, its maximum required additional resources, $Y_k$, must be greater than the available resources. This must hold for all other processes. Therefore, the condition is $X_p + X_q < \text{Min}\{Y_k | 1 \le k \le n, k \ne p, k \ne q\}$.

I. True. In a max-heap, a parent node is always greater than or equal to its children. This property implies that values generally decrease as one moves down the tree, so the smallest element must be at a leaf.
II. True. The largest element is at the root. The second-largest element must be a child of the root, because any other node would be smaller than its parent, which in turn is smaller than or equal to the root.
III. True. We can obtain the elements from the BST in an array in $O(n)$ time (e.g., via level-order traversal). Then, the standard linear-time build-heap algorithm can construct a max-heap from this array in $O(n)$ time.
IV. False. Constructing a BST from a max-heap requires sorting the elements, which takes $\Omega(n \log n)$ time using heapsort.

We are given that the average waiting time is 1 ms. We can trace the execution of the preemptive Shortest Remaining Time First (SRTF) algorithm and find the value of Z that satisfies this condition.

• At t=1, P2 (burst 1) preempts P1 (remaining 2). P2 finishes at t=2 (WT=0).
• P1 resumes and finishes at t=4 (WT=1).
• At t=4, P3 (burst 3) and P4 (burst Z) are ready. P4 must be chosen to run next, implying Z < 3.
• Let's test Z=2. P4 runs from t=4 to t=6 and finishes (WT=0).
• P3 runs from t=6 to t=9 and finishes (WT=3).
  The waiting times are P1:1, P2:0, P3:3, P4:0. The average is $(1+0+3+0)/4 = 1$ ms. This matches the given information, so Z must be 2.

The maximum file size is the sum of data addressable by all pointers in the inode.

• Direct pointers: 12 pointers $\times$ 4 kB/block = 48 kB.
• Single-indirect pointer: This points to a block of addresses. A 4 kB block can hold $4096 \text{ B} / 4 \text{ B/address} = 1024$ addresses. This level contributes $1024 \times 4 \text{ kB} = 4096$ kB.
• Double-indirect pointer: This adds another level of indirection, contributing $1024 \times 1024 \times 4 \text{ kB} = 4,194,304$ kB.
  The total size is approximately $48 + 4096 + 4,194,304 = 4,198,448$ kB.
  Converting to GB: $4,198,448 \text{ kB} / (1024^2 \text{ kB/GB}) \approx 4.004$ GB. Rounded to one decimal place, this is 4.0 GB.

We need to compute the set of items in $GOTO(I_0, \langle)$. The initial set is $I_0 = \text{CLOSURE}(\{[S' \rightarrow \cdot S]\})$. The item in $I_0$ with a dot before '$\langle$' is $[S \rightarrow \cdot \langle L \rangle]$.

1. Move the dot past '$\langle$' to form the kernel of the new state: $\{[S \rightarrow \langle \cdot L \rangle]\}$.
2. Compute the closure of this kernel. Since the dot is before the non-terminal L, we add all productions of L: $[L \rightarrow \cdot L, S]$ and $[L \rightarrow \cdot S]$.
3. These new items have dots before L and S, so we add their productions: $[S \rightarrow \cdot \langle L \rangle]$ and $[S \rightarrow \cdot id]$.
   The final set is $\{[S \rightarrow \langle \cdot L \rangle], [L \rightarrow \cdot L, S], [L \rightarrow \cdot S], [S \rightarrow \cdot \langle L \rangle], [S \rightarrow \cdot id]\}$. This set contains 5 items.

The product of the eigenvalues of a matrix is equal to its determinant. The given matrix is a Vandermonde matrix. We can compute its determinant by applying row operations to simplify the matrix. Subtracting the first row from each of the other rows ($R_i \leftarrow R_i - R_1$ for $i=2,3,4$) creates zeros in the first column below the first element. Expanding the determinant along the first column and repeating this process leads to the result. The determinant is $(3-2)(4-2)(5-2)(4-3)(5-3)(5-4) = 1 \cdot 2 \cdot 3 \cdot 1 \cdot 2 \cdot 1 = 12$.

To find the maximum bandwidth, we calculate the data transferred per cache miss and divide by the time taken.

• Data transferred: One cache block is 8 words, and each word is 4 bytes. So, $8 \times 4 = 32$ bytes are transferred.
• Time taken: The process takes $1$ (address) $+ 3$ (fetch) $+ 8$ (transmit) $= 12$ clock cycles.
• The clock frequency is 60 MHz, so the duration of one cycle is $1 / (60 \times 10^6)$ seconds.
• Total time for transfer = $12 \times (1 / (60 \times 10^6)) = 1 / (5 \times 10^6)$ seconds.
• Bandwidth = Data / Time = $32 \text{ bytes} / (1 / (5 \times 10^6) \text{ s}) = 160 \times 10^6$ bytes/sec.

A full binary tree with 8 leaves has $^8C_2 = 28$ unique pairs of leaves. The distance between any two leaves depends on the depth of their lowest common ancestor (LCA).

• Distance 2 (LCA is parent): 4 pairs.
• Distance 4 (LCA is grandparent): 8 pairs.
• Distance 6 (LCA is the root): 16 pairs.
  The expected distance is the weighted average of these distances:
  $E[X] = \frac{(2 \times 4) + (4 \times 8) + (6 \times 16)}{28} = \frac{8 + 32 + 96}{28} = \frac{136}{28} \approx 4.857$.
  Rounded to two decimal places, the expected value is 4.86.

A quadratic polynomial $ax^{2+}bx+c$ has only real roots if its discriminant $b^{2-}4ac \ge 0$. For the polynomial $3x^2 + (6Y)x + (3Y+6)$, the discriminant is $(6Y)^2 - 4(3)(3Y+6)$.
Setting this $\ge 0$ gives $36Y^2 - 36Y - 72 \ge 0$, which simplifies to $Y^2 - Y - 2 \ge 0$, or $(Y-2)(Y+1) \ge 0$.
This inequality holds for $Y \le -1$ or $Y \ge 2$.
Since Y is uniformly distributed in the interval (1, 6), the favorable range for Y is $[2, 6)$. The total length of the interval is $6-1=5$. The length of the favorable interval is $6-2=4$. The probability is the ratio of these lengths, $4/5 = 0.8$.

The language L consists of sequences of permutations on 5 elements whose composition results in the identity permutation. A Deterministic Finite Automaton (DFA) for this language must remember the result of the composition of the permutations read so far. Each state of the DFA will correspond to one of the possible permutations. The set of all permutations on 5 elements is the symmetric group $S_5$, which has $5! = 120$ elements. Therefore, the DFA needs 120 states. The start state corresponds to the identity permutation (for the empty string), and it is also the sole accepting state.

We need to connect 15 machines using 8-port switches.

• One switch has 8 ports, which is not enough for 15 machines.
• Two switches can be connected, using one port on each for the link. This leaves $7+7=14$ available ports for machines, which is still not enough.
• With three switches, we can connect one central switch to the other two. The central switch uses 2 ports for these links, leaving 6 ports for machines. The other two switches each use one port for a link, leaving 7 ports each. The total capacity is $6+7+7=20$ ports, which is sufficient for 15 machines.
  Therefore, the minimum number of switches required is 3.

The given function is $f = \Sigma (0, 2, 5, 7, 8, 10, 13, 15)$. A Karnaugh map shows this function simplifies to $f = B \odot D = BD + \bar{B}\bar{D}$. We need to implement this using 2-input NOR gates, assuming inputs and their complements are available.
The expression can be implemented with a two-level NOR-NOR structure.
Let Gate 1 be $\text{NOR}(\bar{B}, D) = B\bar{D}$.
Let Gate 2 be $\text{NOR}(B, \bar{D}) = \bar{B}D$.
Let Gate 3 be $\text{NOR}(\text{out}_1, \text{out}_2) = \overline{B\bar{D} + \bar{B}D} = \overline{B \oplus D} = B \odot D$.
This implementation requires 3 NOR gates.
Wait, NOR(B',D) is not B D'. It is (B')' . D' = B D'.
NOR(B,D') is not B'D. It is B' . (D')' = B'D.
NOR(out1, out2) = (out1)' . (out2)' = (BD')' . (B'D)' = (B'+D)(B+D') = B'B + B'D' + DB + DD' = B'D' + BD.
This is correct. It takes 3 NOR gates.

The SQL query lacks a join condition in the WHERE clause (e.g., S.Roll_no = P.Roll_no), resulting in a Cartesian product (cross join) between the Student and Performance tables. The query then groups the result by S.Student_name. Since there are 5 distinct student names in the Student table, the GROUP BY clause will create 5 groups. The WHERE P.Marks > 84 clause is applied, but since it's a cross product, each of the 5 students will be associated with all performance records meeting this criterion. As long as at least one performance record has marks > 84, every student group will be non-empty. Thus, the query will return one row for each of the 5 students.

The while loop executes as long as i/j > 0.0625. The initial values are i = 2.0 and j = 1.0. In each iteration, j is doubled and sum is updated, followed by a printf call.

• Iter 1: j=1, 2/1 > 0.0625. Prints. j becomes 2.
• Iter 2: j=2, 2/2 > 0.0625. Prints. j becomes 4.
• Iter 3: j=4, 2/4 > 0.0625. Prints. j becomes 8.
• Iter 4: j=8, 2/8 > 0.0625. Prints. j becomes 16.
• Iter 5: j=16, 2/16 = 0.125 > 0.0625. Prints. j becomes 32.
• Next check: j=32, 2/32 = 0.0625. The condition 0.0625 > 0.0625 is false. The loop terminates.
  The printf statement is executed 5 times.

The pointer b is initialized to a + 4, which points to the last element of array a (a[4], value 10). The for loop runs from i = 0 to 4. The expression added to sum in each iteration is (*b - i) - *(b - i).

• *b is always 10.
• *(b - i) is equivalent to a[4 - i].
  The values added to sum are:
• i=0: (10 - 0) - a[4] = 10 - 10 = 0
• i=1: (10 - 1) - a[3] = 9 - 8 = 1
• i=2: (10 - 2) - a[2] = 8 - 6 = 2
• i=3: (10 - 3) - a[1] = 7 - 4 = 3
• i=4: (10 - 4) - a[0] = 6 - 2 = 4
  The final sum is $0 + 1 + 2 + 3 + 4 = 10$.

In the RSA algorithm, we are given the modulus $n = pq = 3007$ and Euler's totient function $\phi(n) = (p-1)(q-1) = 2880$.
By expanding the totient function expression, we get $pq - p - q + 1 = 2880$.
Substituting $pq = 3007$, we have $3007 - (p+q) + 1 = 2880$.
Solving for the sum of the primes, we find $p+q = 3008 - 2880 = 128$.
We now need to find two prime numbers, $p$ and $q$, such that their sum is 128 and their product is 3007. By solving the quadratic equation $x^2 - 128x + 3007 = 0$ or by inspection, we find the factors to be 31 and 97. The prime factor that is greater than 50 is 97.

The query performs a set difference between the results of two subqueries.

1. First subquery: $\Pi_X(\sigma_{P.Y=R.Y \land R.V=V2}(P \times R))$. We join P and R on attribute Y, but only for tuples in R where V is 'V2'. The R tuples are (Y3, V2) and (Y2, V2). Only Y2 exists in P's Y column, corresponding to the tuple (X2, Y2, Z2). The projection on X gives the set {X2}.
2. Second subquery: $\Pi_X(\sigma_{Q.Y=R.Y \land Q.T>2}(Q \times R))$. We join Q and R on Y, for tuples in Q where T > 2. The Q tuples are (X1, Y2, 5) and (X1, Y1, 6). Both Y1 and Y2 exist in R. In both cases, the X value from Q is X1. The projection on X gives the set {X1}.
   The final result is the set difference: {X2} - {X1} = {X2}. This result contains one tuple.