GATE CSE 2018

The sentence requires three different words to be grammatically correct. The first blank needs a subject and verb, which "They're" (a contraction of "they are") provides. The second blank describes possession of the "books," so the possessive pronoun "their" is appropriate. The third blank indicates a location from which the books are brought, requiring the adverb of place "there."

The sentence structure uses the word "but" to create a contrast. The phrase "organized ones are more successful" implies that the word in the blank should describe a type of investigation that is the opposite of organized. "Meandering" means proceeding in a winding or aimless way, which provides the necessary contrast to "organized."

Let the side of the square be $a$. The area of the square is $d = a^2$. The diagonal of the square is $\sqrt{a^2 + a^2} = a\sqrt{2}$. This diagonal is the diameter of the circle. Therefore, the radius of the circle is $r = \frac{a\sqrt{2}}{2}$. The area of the circle is $\pi r^2 = \pi \left(\frac{a\sqrt{2}}{2}\right)^2 = \pi \frac{2a^2}{4} = \frac{\pi a^2}{2}$. Since $d = a^2$, the circle's area is $\frac{\pi d}{2}$.

The problem requires finding a number $N$ of the form $N = \text{LCM}(20, 42, 76) + 7$. First, we find the Least Common Multiple (LCM) of the three numbers.
The prime factorizations are:
$20 = 2^2 \times 5$
$42 = 2 \times 3 \times 7$
$76 = 2^2 \times 19$
The LCM is $2^2 \times 3 \times 5 \times 7 \times 19 = 7980$.
The smallest such number is the LCM plus the remainder: $7980 + 7 = 7987$.

The pattern in the sequence involves multiplying each term by a decreasing integer to get the next term.
$2 \times 6 = 12$
$12 \times 5 = 60$
$60 \times 4 = 240$
$240 \times 3 = 720$
$720 \times 2 = 1440$
Following this pattern, the next term is $1440 \times 1 = 1440$. The final term is then $1440 \times 0 = 0$, which matches the given sequence.

Let $x$ be the number of eligible male senior citizens. Then, the number of eligible female senior citizens is $300 - x$.

The number of men who claimed the gift is $\frac{8}{9}x$, and the amount they received is $\frac{8}{9}x \times 750$.
The number of women who claimed the gift is $\frac{2}{3}(300-x)$, and the amount they received is $\frac{2}{3}(300-x) \times 1000$.

The total amount given away is the sum of these two amounts:
$\text{Total Amount} = \left(\frac{8}{9}x \times 750\right) + \left(\frac{2}{3}(300-x) \times 1000\right)$
$= \frac{6000}{9}x + \frac{2000}{3}(300-x)$
$= \frac{2000}{3}x + 200000 - \frac{2000}{3}x = 200,000$
The total amount given away was Rs. 2,00,000.

The given equations can be rewritten using the property $a^{-n} = 1/a^n$.
The first equation, $p^{-x} = 1/q$, is equivalent to $p^x = q$.
The second equation, $q^{-y} = 1/r$, is equivalent to $q^y = r$.
The third equation, $r^{-z} = 1/p$, is equivalent to $r^z = p$.

Now, we can use substitution. Start with $p = r^z$.
Substitute $r = q^y$ into this equation: $p = (q^y)^z = q^{yz}$.
Next, substitute $q = p^x$ into the result: $p = (p^x)^{yz} = p^{xyz}$.
Since $p^1 = p^{xyz}$, we can equate the exponents, which gives $xyz = 1$.

Let's assume there are 100 invited guests in total.
Based on the given percentages, the number of invited males is $0.60 \times 100 = 60$, and the number of invited females is $0.40 \times 100 = 40$.
The total number of guests who attended the party is $80\%$ of the invited guests, which is $0.80 \times 100 = 80$.
It is stated that all invited female guests attended, so there were 40 female attendees.
The number of male attendees is the total number of attendees minus the female attendees: $80 - 40 = 40$.
The ratio of males to females among the attendees is therefore 40:40, which simplifies to 1:1.

The solution is derived by considering the sum of angles in triangles and the quadrilateral in the figure.
The sum of angles in any triangle is $180^\circ$, and the sum of interior angles in the quadrilateral ABCD is $360^\circ$.
By establishing relationships between the angles of the triangles (e.g., $\triangle AEB$ and $\triangle FDC$ from the diagram) and the angles of the quadrilateral ABCD, a final expression can be derived.
The derivation shown in the solution booklet, despite some ambiguity in notation, combines these geometric facts to conclude that $\angle E + \angle F = \angle C - \angle A$.
This translates to $\angle DEC + \angle BFC = \angle BCD - \angle BAD$.

First, we find the probabilities for each outcome on a single roll. The die has 4 green faces and 2 red faces.
The probability of rolling a green face is $P(G) = \frac{4}{6} = \frac{2}{3}$.
The probability of rolling a red face is $P(R) = \frac{2}{6} = \frac{1}{3}$.
For 7 rolls, the expected number of green faces is $E(G) = n \times P(G) = 7 \times \frac{2}{3} = \frac{14}{3} \approx 4.67$.
The expected number of red faces is $E(R) = n \times P(R) = 7 \times \frac{1}{3} = \frac{7}{3} \approx 2.33$.
The most likely outcome is the integer combination of outcomes that is closest to these expected values. The combination of 5 green faces and 2 red faces is the closest to the expected values of 4.67 and 2.33.

The generating function for a sequence $\{a_n\}$ is given by $G(x) = \sum_{n=0}^{\infty } a_n x^n$.
For $a_n = 2n+3$, the function is $G(x) = \sum_{n=0}^{\infty } (2n+3)x^n$.
This can be split into two parts:
$G(x) = 2\sum_{n=0}^{\infty } nx^n + 3\sum_{n=0}^{\infty } x^n$
Using the standard closed-form expressions for these series:
$\sum_{n=0}^{\infty } x^n = \frac{1}{1-x}$ and $\sum_{n=0}^{\infty } nx^n = \frac{x}{(1-x)^2}$
Substituting these back gives:
$G(x) = 2\left(\frac{x}{(1-x)^2}\right) + 3\left(\frac{1}{1-x}\right) = \frac{2x + 3(1-x)}{(1-x)^2} = \frac{3-x}{(1-x)^2}$

In the structure initialization, p.z is assigned 'a' + 2. In ASCII, this operation results in the character 'c'. The structure p in memory will contain the bytes '1', '0', 'c' contiguously.
The pointer q points to the base address of p. The printf statement casts q to a character pointer, (char*)q.

• *((char*)q + 1): This expression accesses the second byte of the structure, which is the member y, holding the value '0'.
• *((char*)q + 2): This expression accesses the third byte, which is the member z, holding the value 'c'.
  Thus, the program prints the characters '0' and 'c'.

The enqueue operation is implemented by inserting a new node at the head of the singly linked list. This involves creating a new node, setting its next pointer to the current head, and then updating the head pointer to the new node. These are all constant-time operations, so the complexity is $\Theta(1)$.

The dequeue operation is implemented by deleting a node from the tail. In a singly linked list, to remove the tail node, one must update the next pointer of the second-to-last node to NULL. Finding this predecessor node requires traversing the entire list from the head, which takes time proportional to the number of nodes, $n$. Therefore, the complexity is $\Theta(n)$.

Let's analyze the expression in option D: $(P \bigoplus \overline{P})\bigoplus Q=(P\bigodot\overline{P})\bigodot \overline{Q}$.

First, evaluate the Left Hand Side (LHS):
The expression $P \bigoplus \overline{P}$ is always true, evaluating to 1.
So, the LHS becomes $1 \bigoplus Q$. By the definition of XOR, $1 \bigoplus Q = (1 \cdot \overline{Q}) + (\overline{1} \cdot Q) = \overline{Q}$.

Next, evaluate the Right Hand Side (RHS):
The expression $P \bigodot \overline{P}$ is always false, evaluating to 0.
So, the RHS becomes $0 \bigodot \overline{Q}$. By the definition of XNOR, $0 \bigodot \overline{Q} = (0 \cdot \overline{Q}) + (\overline{0} \cdot \overline{\overline{Q}}) = 1 \cdot Q = Q$.

The statement thus simplifies to $\overline{Q} = Q$, which is not a valid Boolean identity. Therefore, this statement is not correct.

The design of a RISC (Reduced Instruction Set Computer) processor is based on several key characteristics aimed at simplifying hardware and enabling high performance through pipelining.
I. Register-to-register arithmetic operations only: This is a core concept of the load/store architecture used by RISC. Data must be loaded from memory into registers before arithmetic operations can be performed, and results are stored back to memory.
II. Fixed-length instruction format: This simplifies the instruction decoding process, allowing for faster and simpler control logic.
III. Hardwired control unit: RISC processors use a hardwired control unit, which is faster than the microprogrammed control units typically found in CISC processors.
All three listed characteristics are fundamental design principles of RISC processors.

An NFA with $n$ states can be converted to an equivalent DFA using the subset construction method. In this method, each state of the DFA corresponds to a subset of the states of the NFA. Since a set with $n$ elements has $2^n$ possible subsets, the maximum number of states in the equivalent DFA is $2^n$. Therefore, the number of states, $k$, in the minimal DFA must be less than or equal to this upper bound, i.e., $k \le 2^n$.

Recursively enumerable (RE) languages are closed under operations like union and intersection. However, they are not closed under complementation. The set of recursive languages is a proper subset of the set of RE languages. Furthermore, the set of all RE languages is countably infinite because they can be enumerated by Turing machines, and the set of all Turing machines is countable.

The statement that type checking is done before parsing is false. In the compilation process, parsing (syntax analysis) occurs before semantic analysis. Type checking is a key part of the semantic analysis phase. The other statements are true: context-free grammars can specify lexical rules (as regular languages are a subset of context-free languages), high-level programs can be translated into various intermediate forms, and the program stack is used for passing function arguments.

When a device interrupt occurs, the processor first completes the current instruction (Q). Then, it saves the context of the running process L by pushing its status onto the control stack (P). Next, the processor loads the program counter with the starting address of the interrupt service routine (ISR) from the interrupt vector table (T). The ISR is then executed (R). After the ISR completes, the saved process status is popped from the stack to resume process L (S). The correct sequence of events is QPTRS.

The effective memory access time, $X$, is a weighted average of access time with and without a page fault. Let $P$ be the page fault rate. The formula is $X = P \times D + (1-P) \times M$, where $D$ is the time for a page fault and $M$ is the normal memory access time. To find the page fault rate $P$, we can rearrange the equation:
$X = PD + M - PM$
$X - M = P(D - M)$
$P = \frac{X - M}{D - M}$

The relationship from entity set E1 to E2 is many-to-one. This implies that any entity in E1 can be associated with at most one entity in E2. Additionally, the problem states that E1 has total participation in the relationship R. This means every entity in E1 must be part of the relationship. Combining these two conditions, it follows that every entity in E1 must be associated with exactly one entity in E2.

A FULL OUTER JOIN returns all rows from both tables, including matched rows and unmatched rows from each table. An INNER JOIN returns only matched rows. A LEFT OUTER JOIN returns all rows from the left table and matched rows from the right. A RIGHT OUTER JOIN does the opposite. By definition, the result of a FULL OUTER JOIN contains all rows from the INNER, LEFT, and RIGHT joins. Therefore, its output is always a superset of the other three.

The standard lengths in bits for the given protocol header fields are as follows:

• Q. Ethernet MAC Address: 48 bits (I)
• S. TCP Header's Sequence Number: 32 bits (III)
• P. UDP Header's Port Number: 16 bits (IV)
• R. IPv6 Next Header: 8 bits (II)
  Therefore, the correct matching is P-IV, Q-I, R-II, S-III.

During the TCP slow start phase, the congestion window ($cwnd$) grows exponentially. For each successful acknowledgment received, the sender increases the $cwnd$ by one Maximum Segment Size (MSS). Since an entire window of segments is acknowledged within one Round Trip Time (RTT), this mechanism causes the $cwnd$ to approximately double every RTT. Thus, statement (iv) is the correct description of the window growth in this phase.

For a winner to be decided on the third trial, the first two trials must result in a tie, and the third trial must not be a tie. The total number of outcomes when rolling two dice is $6 \times 6 = 36$. A tie occurs if both people roll the same number, which can happen in 6 ways (1-1, 2-2, etc.).
The probability of a tie is $P(\text{tie}) = \frac{6}{36}$.
The probability of no tie is $P(\text{no tie}) = 1 - \frac{6}{36} = \frac{30}{36}$.
The probability of two ties followed by a non-tie is $P(\text{tie}) \times P(\text{tie}) \times P(\text{no tie}) = \frac{6}{36} \times \frac{6}{36} \times \frac{30}{36} \approx 0.023$.

To evaluate the integral, we use the substitution method. Let $t = x^2$. This implies that $dt = 2x\,dx$, or $x\,dx = \frac{dt}{2}$. We must also change the limits of integration. When $x=0$, $t=0$. When $x=\frac{\pi}{4}$, $t = (\frac{\pi}{4})^2 = \frac{\pi^2}{16}$.

The integral transforms to:
$I = \int_{0}^{\pi^2/16} \cos(t) \frac{dt}{2} = \frac{1}{2} [\sin(t)]_{0}^{\pi^2/16}$
$I = \frac{1}{2} \left( \sin\left(\frac{\pi^2}{16}\right) - \sin(0) \right)$
Using $\pi \approx 3.14$, we get $\frac{\pi^2}{16} \approx 0.616$.
$I \approx \frac{1}{2} \sin(0.616) \approx 0.29$

First, we compute the matrix $A$ from the given vectors $u$ and $v$.
$A = uv^T = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \begin{bmatrix} 1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 2 & 2 \end{bmatrix}$
The eigenvalues $\lambda$ are found using the characteristic equation $\lambda^2 - \text{trace}(A)\lambda + \det(A) = 0$.
The trace of A is the sum of the diagonal elements: $\text{trace}(A) = 1 + 2 = 3$.
The determinant of A is: $\det(A) = (1)(2) - (1)(2) = 0$.
Substituting these values into the characteristic equation gives:
$\lambda^2 - 3\lambda + 0 = 0$
$\lambda(\lambda - 3) = 0$
The eigenvalues are $\lambda = 0$ and $\lambda = 3$. The largest eigenvalue is 3.

The chromatic number of a graph is the minimum number of colors needed to color its vertices so that no two adjacent vertices share the same color.

First, we observe that the vertices {b, c, d} form a triangle, which is a clique of size 3. Therefore, at least 3 colors are required, and the chromatic number $\chi(G) \ge 3$.

Next, we check if the graph can be colored with 3 colors. A possible 3-coloring is:

• Color 1 (e.g., Blue): {a, f}
• Color 2 (e.g., Green): {b, e}
• Color 3 (e.g., White): {c, d}
  Since a valid 3-coloring exists, $\chi(G) \le 3$.
  Combining both conditions, the chromatic number is exactly 3.

According to Lagrange's theorem, the order (number of elements) of any subgroup of a finite group must be a divisor of the order of the group. The order of the group G is 84.

The divisors of 84 are 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, and 84.

A "proper" subgroup is any subgroup of G except G itself. Therefore, the order of a proper subgroup must be a divisor of 84 that is strictly less than 84. The largest such divisor is 42.

To find the height of the tree, we first need to construct it from its inorder and postorder traversals.

• Postorder: 8, 9, 6, 7, 4, 5, 2, 3, 1
• Inorder: 8, 6, 9, 4, 7, 2, 5, 1, 3

The last element in the postorder traversal is the root, so the root is 1. In the inorder traversal, all elements to the left of 1 belong to the left subtree, and all elements to the right belong to the right subtree. This process is applied recursively to build the entire tree, as shown in the PDF.

The constructed tree has the root 1. The longest path from the root to a leaf is 1 → 2 → 4 → 6 → 8. The length of this path is the number of edges, which is 4. Therefore, the height of the tree is 4.

The C program calculates a value recursively and prints the final count of function calls. The global variable counter is incremented each time the calc function is entered.

The initial call is calc(4, 81). The function calls itself with b divided by 3 until b equals 3.

1. calc(4, 81): counter becomes 1. Calls calc(4, 27).
2. calc(4, 27): counter becomes 2. Calls calc(4, 9).
3. calc(4, 9): counter becomes 3. Calls calc(4, 3).
4. calc(4, 3): counter becomes 4. The base case b==3 is met, and the function returns.

The main function then prints the final value of counter, which is 4.

The state of the circuit is determined by the outputs of the two flip-flops, (Q1, Q0). The inputs to the flip-flops are D1 = in and D0 = Q1. The next state (Q1+, Q0+) is (D1, D0).

We can create a state transition table:

• When in = 0: The next state is (0, Q1).
  • From state (00), Q1=0, next state is (0,0). This is a self-loop.
  • From state (01), Q1=0, next state is (0,0).
• When in = 1: The next state is (1, Q1).
  • From state (10), Q1=1, next state is (1,1).
  • From state (11), Q1=1, next state is (1,1). This is a self-loop.

The states (00) and (11) have transitions back to themselves for inputs 0 and 1, respectively. Thus, there are 2 such states.

First, calculate the total time required to refresh all rows in a DRAM chip.
Number of rows = $2^{14}$.
Time to refresh one row = 50 ns.
Total refresh time = $2^{14} \times 50 \text{ ns} = 16384 \times 50 \times 10^{-9} \text{ s} = 0.8192 \text{ ms}$.

This entire refresh operation must be completed within the refresh period of 2 ms. The percentage of time spent on refreshing (overhead) is:
Refresh Overhead = $\frac{\text{Total refresh time}}{\text{Refresh period}} \times 100 = \frac{0.8192 \text{ ms}}{2 \text{ ms}} \times 100 = 40.96\%$.

The percentage of time available for read/write operations is the remaining time:
Available Time % = $100\% - 40.96\% = 59.04\%$.
Rounded to the closest integer, this is 59%.

To always avoid deadlock, a system must be in a safe state. A safe state is guaranteed if the sum of maximum resource needs of all processes is less than the sum of the total number of processes and total resources.
Let n be the number of processes (3), m be the number of resources (4), and K be the maximum need of each process.

The condition for avoiding deadlock is:
\sum_{i=1}^{n} \text{max_need}_i < n + m
$3 \times K < 3 + 4$
$3K < 7$
$K < \frac{7}{3} \approx 2.333$

Since K must be an integer, the largest value of K that satisfies this condition is 2.

The TCP sequence number is 32 bits, which means there are $2^{32}$ unique sequence numbers. Since TCP assigns a sequence number to each byte, this corresponds to $2^{32}$ bytes of data.

The bandwidth is 1 Gbps, which is $10^9$ bits per second. To find the rate in bytes per second, we divide by 8:
Bandwidth = $\frac{10^9}{8}$ bytes/second.

The time before the sequence number wraps around is the total number of bytes divided by the transmission rate:
Time = $\frac{2^{32} \text{ bytes}}{\frac{10^9}{8} \text{ bytes/s}} = \frac{2^{32} \times 8}{10^9} \text{ s} \approx 34.36 \text{ s}$.

Rounding to the closest integer, the minimum time is 34 seconds.

A matrix is diagonalizable if and only if it has a complete set of linearly independent eigenvectors. Since all eigenvectors of P are multiples of a single vector, P has only one linearly independent eigenvector. For a 2x2 matrix, this means it does not have a full set of two linearly independent eigenvectors, so it cannot be diagonalized (Statement III is true).

A matrix that is not diagonalizable must have at least one repeated eigenvalue (Statement II is true). Statement I is not necessarily true, as P could be invertible. For example, the matrix

has a repeated eigenvalue of 1 but is invertible.

Let's analyze the countability of each set:
P: The set of rational numbers ($\mathbb{Q}$) is countable. This can be demonstrated by creating a one-to-one correspondence with the natural numbers.
Q: The set of functions from $\{0, 1\}$ to $\mathbb{N}$. Each function is uniquely determined by the pair of values $(f(0), f(1))$. This set is equivalent to $\mathbb{N} \times \mathbb{N}$, which is the Cartesian product of two countable sets and is therefore countable.
R: The set of functions from $\mathbb{N}$ to $\{0, 1\}$. This set is equivalent to the set of all infinite binary sequences, which has the same cardinality as the power set of $\mathbb{N}$. By Cantor's theorem, this set is uncountable.
S: The set of all finite subsets of $\mathbb{N}$ is countable.
Thus, the countable sets are P, Q, and S.

The first-order logic sentence $\varphi$ asserts the existence of three elements $s, t, u$ for which a property holds for all elements in the universe. If a model with a universe of 7 elements satisfies this, it means such $s, t, u$ can be found within those 7 elements. We can then construct a new, smaller model whose universe consists only of these three specific elements $\{s, t, u\}$. In this universe of size 3, the sentence $\varphi$ remains true. Therefore, if a model of size 7 exists, a model of size less than or equal to 3 must also exist.

The function fun1 receives pointers by value. Swapping the local copies of the pointers s1 and s2 inside fun1 does not alter the original pointers str1 and str2 in the main function. Thus, the first printf outputs "Hi Bye". In contrast, fun2 receives pointers to pointers (pass-by-reference). Dereferencing them allows fun2 to swap the actual pointers str1 and str2 in main. After the call to fun2, str1 points to "Bye" and str2 points to "Hi". The second printf therefore outputs "Bye Hi".

Statement (I) is true. During a Depth First Search (DFS) on an undirected graph, any edge not part of the DFS tree must be a back edge, connecting a vertex to one of its ancestors. Cross edges, which connect vertices in different subtrees where neither is an ancestor of the other, do not occur in a DFS of an undirected graph. Statement (II) is false. A Breadth First Search (BFS) explores level by level. An edge can connect two vertices at the same depth, for which $|i-j|=0$. This violates the condition $|i-j|=1$.

This is a matrix chain multiplication problem. The goal is to find the parenthesization that minimizes the number of scalar multiplications. The dimensions are F1(2x25), F2(25x3), F3(3x16), F4(16x1), and F5(1x1000).

Let's analyze the parenthesization (F1(F2(F3F4)))F5:

1. Cost of (F3F4): Dimensions are (3x16) and (16x1). Cost = $3 \times 16 \times 1 = 48$. Result is a 3x1 matrix.
2. Cost of F2(F3F4): Dimensions are (25x3) and (3x1). Cost = $25 \times 3 \times 1 = 75$. Result is a 25x1 matrix.
3. Cost of F1(F2(F3F4)): Dimensions are (2x25) and (25x1). Cost = $2 \times 25 \times 1 = 50$. Result is a 2x1 matrix.
4. Cost of (F1(F2(F3F4)))F5: Dimensions are (2x1) and (1x1000). Cost = $2 \times 1 \times 1000 = 2000$.

Total cost = $48 + 75 + 50 + 2000 = 2173$. This is the optimal arrangement. An "explicitly computed pair" is defined as two original adjacent matrices being multiplied. In this optimal order, only F3 and F4 are multiplied directly.

The function fun is called with n = 2^40. Let's trace the execution.

The first for loop runs as long as i > 1, with i being halved in each iteration.

• i starts at $2^{40}$ and takes values $2^{40}, 2^{39}, \dots, 2^1$.
• The loop executes 40 times before i becomes 1 and the loop terminates.
• In each iteration, j is incremented. So, after this loop, j will be 40.

The second for loop runs as long as j > 1, with j being halved.

• j starts at 40. The loop iterates for j values of 40, 20, 10, 5, and 2.
• When j is 2, j/2 becomes 1. The loop condition j > 1 fails for the next iteration.
• The loop body sum++ executes 5 times.
• Therefore, the final value of sum returned is 5.

The fixed-point representation has 3 bits for the fractional part. A decimal number can be represented exactly if its fractional part has a finite binary representation.
(i) 31.500: The fractional part $0.5$ is $1/2$, which is exactly $0.1_2$.
(ii) 0.875: The fractional part $0.875$ is $7/8$, which is exactly $0.111_2$.
(iii) 12.100: The fractional part $0.1$ has a non-terminating, repeating binary expansion ($0.000110011..._2$).
(iv) 3.001: The fractional part $0.001$ also has a non-terminating binary expansion.
Therefore, only numbers (iii) and (iv) cannot be represented exactly.

The size of the tag field is determined by subtracting the bits used for the set index and byte offset from the total physical address bits.

1. Physical Address (PA) bits: The physical address space is $2^P$ bytes, so the PA has $P$ bits.
2. Byte Offset bits: The block size is $2^M$ words, and word length is $2^W$ bytes. So, block size is $2^M \times 2^W = 2^{M+W}$ bytes. The number of bits for byte offset is $M+W$.
3. Set Index bits:
   • Cache capacity = $2^N$ bytes.
   • Number of blocks in cache = (Cache Capacity) / (Block Size) = $2^N / 2^{M+W} = 2^{N-M-W}$.
   • Number of sets = (Number of blocks) / K = $2^{N-M-W} / K$.
   • Set index bits = $\log_2(\text{Number of sets}) = \log_2(2^{N-M-W}/K) = N-M-W-\log_2 K$.
4. Tag bits:
   • Tag bits = PA bits - Set bits - Byte offset bits
   • Tag bits = $P - (N-M-W-\log_2 K) - (M+W)$
   • Tag bits = $P - N + M + W + \log_2 K - M - W = P - N + \log_2 K$.

I. $\{a^{m}b^{n}c^{p}d^{q}|m+p=n+q, \; m,n,p,q \geq 0 \}$: This language is context-free. The condition can be rewritten as $m-n = q-p$. A pushdown automaton (PDA) can be designed to recognize this. It can push for a's, pop for b's (or vice-versa, handling the difference on the stack), and then do the same for c's and d's to verify the equality of differences.

II. $\{a^{m}b^{n}c^{p}d^{q}|m=n \; and \; p=q, \; m,n,p,q\geq 0 \}$: This is context-free. It is the concatenation of two CFLs: $L_1 = \{a^m b^n | m=n\}$ and $L_2 = \{c^p d^q | p=q\}$. The concatenation of CFLs is a CFL. A grammar is $S \rightarrow AB$, $A \rightarrow aAb | \epsilon$, $B \rightarrow cBd | \epsilon$.

III. $\{a^{m}b^{n}c^{p}d^{q}|m=n=p \dots \}$: This is not context-free as it requires comparing three counts ($m, n, p$), which a PDA cannot do.

IV. $\{a^{m}b^{n}c^{p}d^{q}|mn=p+q \dots \}$: This is not context-free as multiplication (mn) is beyond the capabilities of a PDA.

The decidability of the given problems is as follows:
(I) The membership problem for an unrestricted grammar (which is equivalent to a Turing Machine) is undecidable.
(II) According to Rice's theorem, any non-trivial property of the language accepted by a Turing Machine is undecidable. Whether a language is regular is a non-trivial property, hence this problem is undecidable.
(III) The equivalence problem, which is determining if two grammars generate the same language ($L(G_1) = L(G_2)$), is undecidable for context-free grammars and higher.
(IV) The problem of equivalence between an NFA (accepting a regular language) and a DPDA (accepting a deterministic CFL) is decidable.
Thus, problems I, II, and III are undecidable.

The lexical analyzer uses the "longest possible prefix" rule on the input string bbaacabc.

1. The longest prefix of the string that matches any of the three patterns is bbaac. This string matches the pattern for token $T_3: c?(b|a)^*c$. Here, c? matches an empty string, (b|a)^* matches bbaa, and the final c matches c.
2. After this token is recognized, the remaining string is abc.
3. The longest prefix of the remaining string abc that matches a pattern is the entire string abc itself. This also matches the pattern for token $T_3$.
   Therefore, the sequence of tokens output by the analyzer is $T_3T_3$.

By examining the structure of the parse tree, we can determine the operator precedence and associativity.

1. The sub-expression b$c$d is evaluated before the operators # are considered, as it is located at a lower level in the tree. This indicates that $ has higher precedence than #.
2. Within the sub-tree for b$c$d, the grouping is (b$c)$d, meaning the $ operator associates to the left. Thus, $ is left-associative.
3. The operations involving # are evaluated from right to left. For instance, e#f is evaluated first, and its result is then used. This shows that # is right-associative.

To determine if the system is in a safe state, we use the Banker's algorithm. First, we calculate the Need matrix as Max - Allocation.
Need matrix: $P_0$: (3,3,0), $P_1$: (1,0,2), $P_2$: (0,3,0), $P_3$: (3,4,1).
The available resources are (3,3,0).
The safety algorithm checks if there is a sequence of processes that can complete. A safe sequence exists, for example, <$P_0, P_2, P_1, P_3$>.

1. $P_0$'s need (3,3,0) $\le$ Available (3,3,0). $P_0$ can execute. New Available = (3,3,0) + (1,0,1) = (4,3,1).
2. $P_2$'s need (0,3,0) $\le$ Available (4,3,1). $P_2$ can execute. New Available = (4,3,1) + (1,0,3) = (5,3,4).
   This process continues for $P_1$ and $P_3$. Since a safe sequence can be found, the system is in a safe state.

The problem uses non-standard definitions for the semaphores.

1. empty: "slots... for the consumer to read from," meaning the number of full slots. Its initial value is 0.
2. full: "slots... for the producer to write to," meaning the number of empty slots. Its initial value is N.
   Based on these definitions:

• The producer must wait for an empty slot (semaphore full) and signal a full slot (semaphore empty). Thus, P = full and Q = empty.
• The consumer must wait for a full slot (semaphore empty) and signal an empty slot (semaphore full). Thus, R = empty and S = full.
  This assignment is P: full, Q: empty, R: empty, S: full.

The original query, $Q:r \Join (\sigma _{B\lt 5}(s))$, first selects rows from table s where B is less than 5, and then performs a natural join with table r. This is an inner join, so any row in r whose B value is 5 or greater will be discarded because it won't find a match in the filtered s.

Now consider option C: $r \text{ LOJ}(\sigma _{B\lt 5}(s))$. This also filters s first. However, it then performs a left outer join. This means if a row in r has a B value $\ge 5$, it will still be included in the final result, with NULL values for the columns from s. Since this query preserves rows from r that the original query would discard, it is not equivalent.

Let's analyze Schema II: Registration(rollno, courseid, email) with FDs rollno, courseid → email and email → rollno.
The candidate keys are {rollno, courseid} and {email, courseid}.
The set of prime attributes (part of any candidate key) is {rollno, courseid, email}. There are no non-prime attributes.

A schema is in 3NF if for every FD $X \to Y$, either $X$ is a superkey or $Y$ is a prime attribute.

• For email → rollno, the right-hand side rollno is a prime attribute.
• For rollno, courseid → email, the determinant is a superkey.
  Thus, the schema is in 3NF.

A schema is in BCNF if for every FD $X \to Y$, $X$ must be a superkey.

• The FD email → rollno violates BCNF because its determinant, {email}, is not a superkey.

Therefore, Schema II is in 3NF but not in BCNF.

The degree of a vertex, y, is the number of neighbors it has. A neighbor is formed by swapping two adjacent numbers in the permutation. For a sequence of 100 numbers, there are $100 - 1 = 99$ adjacent pairs. Each adjacent swap results in a unique neighboring vertex. Therefore, the degree of any vertex is $y = 99$.

The set of all permutations can be generated from any single permutation through a series of adjacent swaps (this is the principle behind bubble sort). This means the graph is connected, so it has only one connected component. Thus, $z = 1$.

The required value is $y + 10z = 99 + 10(1) = 109$.

We need to find the probability $P(H_G | H_D)$, which is the probability that Guwahati has a high temperature given that Delhi has a high temperature. Using Bayes' theorem:
$P(H_G | H_D) = \frac{P(H_D | H_G) \cdot P(H_G)}{P(H_D)}$
The numerator is $P(H_D \cap H_G) = P(H_D | H_G) \cdot P(H_G) = 0.40 \times 0.2 = 0.08$.

The denominator $P(H_D)$ is found using the law of total probability:
$P(H_D) = P(H_D|H_G)P(H_G) + P(H_D|M_G)P(M_G) + P(H_D|L_G)P(L_G)$
Using the values from the problem description and the PDF's calculation:
$P(H_D) = (0.40 \times 0.2) + (0.1 \times 0.5) + (0.01 \times 0.3) = 0.08 + 0.05 + 0.003 = 0.133$.
(Note: The PDF calculation uses $P(H_D|M_G)=0.1$, which differs from the table.)

Finally, $P(H_G | H_D) = \frac{0.08}{0.133} \approx 0.60$.

The print("*") statement is executed only when y != 1 and x != 1.
Let's analyze the function call Count(1024, 1024).
The function will keep calling Count(x/2, y) as long as x is not 1. For a given y, the values of x will be $1024, 512, 256, ..., 2$. Since $1024 = 2^{10}$, this sequence has 10 terms ($2^{10}$ to $2^1$), so the print statement executes 10 times.

When x becomes 1, the else block is triggered. It decrements y to y-1 and then calls Count(1024, y-1), restarting the process. This outer loop on y continues as long as y != 1. It will run for y values from 1024 down to 2, which is a total of $1024 - 2 + 1 = 1023$ times.

For each of these 1023 iterations of y, the inner recursion on x prints 10 stars.
Total prints = $1023 \times 10 = 10230$.

The number of min-heaps that can be formed from N distinct elements can be calculated using a recurrence relation. A min-heap with 7 nodes has a root, a left subtree of 3 nodes, and a right subtree of 3 nodes.

1. The smallest element, 1, must be at the root.
2. From the remaining 6 elements {2,3,4,5,6,7}, we must choose 3 for the left subtree. This can be done in $\binom{6}{3}$ ways.
3. Let T(n) be the number of min-heaps with n nodes. The total number of heaps is given by:
   $T(7) = \binom{6}{3} \times T(3) \times T(3)$
4. For a 3-node heap, we choose 1 element for the left child from the 2 available elements: $T(3) = \binom{2}{1} \times T(1) \times T(1) = 2$.
5. Substituting back: $T(7) = 20 \times 2 \times 2 = 80$.

Thus, there are 80 possible min-heaps.

To find the number of Minimum Weight Spanning Trees (MWSTs), one can use an algorithm like Kruskal's. The number of MWSTs is maximized when there are multiple choices of edges with the same minimum weight at some step of constructing the tree. According to the provided solution, the number of MWSTs is maximized when the edge weight $x$ is set to 5. For this value, a total of 4 different MWSTs can be formed. For values of $x$ from 1 to 4, only 2 MWSTs are possible. Thus, the maximum number of MWSTs is 4.

The greedy approach for the 0/1 knapsack problem involves selecting items based on the highest value-to-weight ratio first.
The ratios are:

• Item 1: $60/10 = 6$
• Item 2: $28/7 = 4$
• Item 3: $20/4 = 5$
• Item 4: $24/2 = 12$
  The sorted order of items by ratio is 4, 1, 3, 2. With a knapsack capacity of 11 kg:

1. Pick Item 4 (weight 2, value 24). Remaining capacity: $11 - 2 = 9$ kg.
2. Skip Item 1 (weight 10 > 9).
3. Pick Item 3 (weight 4, value 20). Remaining capacity: $9 - 4 = 5$ kg.
4. Skip Item 2 (weight 7 > 5).
   The total value for the greedy approach is $V_{greedy} = 24 + 20 = 44$.
   The optimal solution is to pick only Item 1 (weight 10, value 60), which fits the capacity. So, $V_{opt} = 60$.
   The difference is $V_{opt} - V_{greedy} = 60 - 44 = 16$.

An essential prime implicant (EPI) is a prime implicant that covers at least one minterm that cannot be covered by any other prime implicant. To find the EPIs, we can use a Karnaugh map (K-map) for the given function $F(P,Q,R,S)=\sum m(0,2,5,7,9,11)+d(3,8,10,12,14)$.

By grouping the minterms and don't-cares on the K-map, we identify the prime implicants. Then, we check which of these are essential:

1. The group covering minterms (0, 2, 8, 10) is an EPI because minterm 0 is covered only by this group.
2. The group covering minterms (3, 7, 11) is an EPI because minterm 11 is covered only by this group.
3. The group covering minterms (5, 7, 9, 11) is an EPI because minterm 5 is covered only by this group.

Since there are three such groups, the number of essential prime implicants is 3.

The total number of clock cycles to execute instructions in a pipeline can be calculated as:
$\text{Total Cycles} = (k-1) + n + \text{Stall Cycles}$
where $k$ is the number of pipeline stages (5), and $n$ is the number of instructions (100).

Stall cycles are the extra cycles consumed beyond the ideal one cycle per stage. Here, stalls are caused by the multi-cycle Perform Operation (PO) stage.
Total cycles spent in the PO stage for all 100 instructions:
$(40 \text{ instr} \times 3 \text{ cycles}) + (35 \text{ instr} \times 2 \text{ cycles}) + (25 \text{ instr} \times 1 \text{ cycle}) = 120 + 70 + 25 = 215 \text{ cycles}$
Ideally, the PO stage would take 100 cycles for 100 instructions. The number of stall cycles is the excess:
$\text{Stall Cycles} = 215 - 100 = 115$
Total cycles = $(5-1) + 100 + 115 = 4 + 100 + 115 = 219$.