GATE CSE 2015 SET 1

The word "any" is typically used in questions and negative sentences to refer to an indefinite quantity of something. In this interrogative sentence, "any paper" is the most grammatically and idiomatically correct choice to ask if the person bought an unspecified amount of paper.

The word "immensely" means to a very great extent or extremely. The sentence indicates she had a very good time. Among the options, "terrific" means extremely good or excellent, which is the closest synonym for having an immensely enjoyable experience. The other options, "terrible," "horrible," and "terrifying," all have negative connotations.

The total number of possible pairs is the product of the number of elements in each set, which is $4 \times 5 = 20$. To get a sum of 16, the favorable pairs are (2, 14), (3, 13), (4, 12), and (5, 11). There are 4 such pairs. The probability is the ratio of favorable outcomes to the total number of outcomes, which is $\frac{4}{20} = 0.2$.

The question asks for the number of steps required to cover a vertical distance. The total vertical distance is given as 9 feet. Statement I provides the height of each step (3/4 foot). With this, the number of steps can be calculated as $\frac{9}{3/4} = 12$. Statement II, which gives the width of each step, is irrelevant for calculating the number of steps needed to cover a certain height. Therefore, statement I alone is sufficient.

The task is to find the incorrect word-meaning pair.
A. Acquiescence is the reluctant acceptance of something, akin to submission.
C. Flippancy is a lack of seriousness, which can be described as lightness.
D. Profligate means recklessly extravagant.
B. To wheedle is to use flattery to persuade someone. This is not synonymous with "roundabout," which means indirect. Therefore, this combination is incorrect.

To find the average marks, we first need the total marks obtained and the total number of students.
The total number of students is the sum of those who answered correctly, wrongly, or not at all for any question. For Q1, this is $21 + 17 + 6 = 44$ students.
The total marks scored by the class is the sum of marks for all correct answers:
Total Marks = $(2 \times 21) + (3 \times 15) + (1 \times 11) + (2 \times 23) + (5 \times 31) = 42 + 45 + 11 + 46 + 155 = 299$.
Average Marks = $\frac{\text{Total Marks}}{\text{Total Students}} = \frac{299}{44} \approx 6.795$.

The phrase "took to their heels" is an English idiom. It means to run away swiftly, especially to escape from danger or trouble. In the given sentence, the chain snatchers ran away when the police arrived. The alternative "took to flight" accurately captures this meaning of fleeing or escaping quickly.

The statement indicates a water shortage. A logical response involves both managing the current supply and reducing demand.
Course of action I, imposing a partial cut, is a direct and practical step to manage the limited water supply.
Course of action II, appealing to residents for minimal use, addresses the demand side by encouraging conservation.
Course of action III, banning supply to certain areas, is an extreme and inequitable measure.
Therefore, actions I and II are the most appropriate and logical courses of action to follow.

The solution requires data from the pie chart, which is not provided. However, the method to solve it is as follows:

1. In Electrical Engineering, there are 40 males. Given the male-to-female ratio of 5:4, the number of females is $(40/5) \times 4 = 32$. The total students in Electrical is $40+32=72$.
2. From the pie chart, find the percentages for the Electrical, Civil, and Mechanical departments.
3. Calculate the total students in Civil and Mechanical based on their percentages relative to Electrical's percentage.
4. Calculate the number of female students in each department using the 4/9 female proportion.
5. Find the difference between the number of females in the Mechanical and Civil departments.

Let M, P, C be the events of passing in the respective subjects. We are given:

1. $P(\text{at least one}) = P(M \cup P \cup C) = 0.75$
2. $P(\text{at least two}) = P(M \cap P) + P(P \cap C) + P(C \cap M) - 2P(M \cap P \cap C) = 0.50$
3. $P(\text{exactly two}) = P(M \cap P) + P(P \cap C) + P(C \cap M) - 3P(M \cap P \cap C) = 0.40$

Subtracting (3) from (2) gives $P(M \cap P \cap C) = 0.10 = 1/10$. Assuming independence, $mpc = 1/10$. Thus, relation III is true.
From (3), $\sum P(M \cap P) = 0.40 + 3(0.10) = 0.70$.
Using the inclusion-exclusion principle for (1):
$P(M \cup P \cup C) = \sum P(M) - \sum P(M \cap P) + P(M \cap P \cap C)$
$0.75 = (m+p+c) - 0.70 + 0.10$
$m+p+c = 0.75 + 0.60 = 1.35 = 27/20$. Thus, relation I is true.

First, we evaluate the composite functions.
To find $g(h(x))$, we substitute $h(x)$ into $g(x)$:
$g(h(x)) = 1 - h(x) = 1 - \frac{x}{x-1} = \frac{(x-1) - x}{x-1} = \frac{-1}{x-1}$

To find $h(g(x))$, we substitute $g(x)$ into $h(x)$:
$h(g(x)) = \frac{g(x)}{g(x)-1} = \frac{1-x}{(1-x)-1} = \frac{1-x}{-x}$

Now, we compute the required ratio:
$\frac{g(h(x))}{h(g(x))} = \frac{-1/(x-1)}{(1-x)/(-x)} = \frac{-1}{x-1} \cdot \frac{-x}{1-x} = \frac{x}{(x-1)(1-x)}$

This expression is equivalent to $\frac{h(x)}{g(x)} = \frac{x/(x-1)}{1-x} = \frac{x}{(x-1)(1-x)}$.

This limit is of the indeterminate form $\infty ^0$. To solve it, let $y = x^{1/x}$.
Taking the natural logarithm of both sides gives $\ln(y) = \ln(x^{1/x}) = \frac{\ln(x)}{x}$.
Now, we find the limit of $\ln(y)$ as $x \to \infty$:
$\lim_{x\to \infty } \ln(y) = \lim_{x\to \infty } \frac{\ln(x)}{x}$
This is of the form $\frac{\infty }{\infty }$, so we can apply L'Hôpital's Rule:
$\lim_{x\to \infty } \frac{(\ln(x))'}{(x)'} = \lim_{x\to \infty } \frac{1/x}{1} = 0$.
Since $\lim_{x\to \infty } \ln(y) = 0$, the original limit is $\lim_{x\to \infty } y = e^0 = 1$.

The matching is based on the design paradigm of each algorithm:
(P) Prim's algorithm for minimum spanning tree uses a greedy approach. At each step, it adds the cheapest edge that connects a vertex in the spanning tree to a vertex outside the tree.
(Q) Floyd-Warshall algorithm for all-pairs shortest paths is a classic example of dynamic programming, where it builds the solution iteratively.
(R) Mergesort is a quintessential divide and conquer algorithm. It recursively divides the array, sorts the subarrays, and then merges them.
(S) The Hamiltonian circuit problem is NP-complete and is often solved using backtracking to explore all possible paths.
Thus, the correct matching is P-ii, Q-iii, R-iv, S-i.

The worst-case time complexity for Quicksort occurs when the pivot selection consistently results in the most unbalanced partition. This happens if the pivot is always the smallest or largest element in the subarray. In such a case, an array of size $n$ is partitioned into one subarray of size $n-1$ and another of size 0. The cost of the partition step is $cn$. This leads to the recurrence relation $T(n) = T(n-1) + T(0) + cn$. Since $T(0)$ and $T(1)$ are constant time operations, this is represented as $T(n) = T(n-1) + T(1) + cn$.

The number of nodes in a binary tree of height $h$ depends on its structure.
The maximum number of nodes occurs in a perfect binary tree, where every level is completely filled. The formula for the number of nodes is $2^{h+1} - 1$. For a height of 5, this is $2^{5+1} - 1 = 2^6 - 1 = 63$.
The minimum number of nodes occurs in a skewed binary tree, where each node has at most one child. The number of nodes is simply $h+1$. For a height of 5, this is $5+1 = 6$.

A key property of a Binary Search Tree (BST) is that an inorder traversal of its nodes results in a sequence sorted in non-decreasing order. We must check which of the given sequences are sorted.

• Sequence I: 3, 5, 7, 8, 15, 19, 25. This is sorted.
• Sequence II: 5, 8, 9, 12, 10, ... This is not sorted (12 > 10).
• Sequence III: 2, 7, 10, 8, ... This is not sorted (10 > 8).
• Sequence IV: 4, 6, 7, 9, 18, 20, 25. This is sorted.

Therefore, only sequences I and IV can be valid inorder traversals of a BST.

In shift-reduce parsing, the stack holds a sequence of grammar symbols. The prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser are called "viable prefixes". By definition, at any point during the parsing process, the contents of the stack form a viable prefix. Therefore, the stack contains only a set of viable prefixes.

The biconditional expression $p \leftrightarrow q$ is logically equivalent to $(p \rightarrow q) \wedge (q \rightarrow p)$. This can be rewritten using the definition of implication $(A \rightarrow B \equiv \neg A \vee B)$ as $(\neg p \vee q) \wedge (\neg q \vee p)$. This form matches options A and B.

Expanding this expression gives $(\neg p \wedge \neg q) \vee (p \wedge q)$, which matches option D.

Option C, $(\neg p \wedge q) \vee (p \wedge \neg q)$, represents the exclusive OR (XOR) operation, which is the negation of the biconditional and therefore not equivalent.

Given the set A = {5, {6}, {7}}, its power set $2^A$ contains all possible subsets of A.
$2^A = \{\phi, \{5\}, \{\{6\}\}, \{\{7\}\}, \{5, \{6\}\}, \{5, \{7\}\}, \{\{6\}, \{7\}\}, \{5, \{6\}, \{7\}\}\}$.

I. $\phi \in 2^A$: True. The empty set is an element of every power set.
II. $\phi \subseteq 2^A$: True. The empty set is a subset of every set.
III. $\{5, \{6\}\} \in 2^A$: True. This is an element of the power set as listed above.
IV. $\{5, \{6\}\} \subseteq 2^A$: False. This would require 5 and {6} to be elements of $2^A$, which they are not.
Thus, statements I, II, and III are true.

A Johnson counter is a shift register where the complement of the output of the last flip-flop is fed back to the input of the first. Starting with 0000:

1. 0000 (0) -> last bit is 0, complement is 1. Shift: 1000 (8)
2. 1000 (8) -> last bit is 0, complement is 1. Shift: 1100 (12)
3. 1100 (12) -> last bit is 0, complement is 1. Shift: 1110 (14)
4. 1110 (14) -> last bit is 0, complement is 1. Shift: 1111 (15)
5. 1111 (15) -> last bit is 1, complement is 0. Shift: 0111 (7)
6. 0111 (7) -> last bit is 1, complement is 0. Shift: 0011 (3)
7. 0011 (3) -> last bit is 1, complement is 0. Shift: 0001 (1)
8. 0001 (1) -> last bit is 1, complement is 0. Shift: 0000 (0)
   The sequence is 0, 8, 12, 14, 15, 7, 3, 1, 0.

In a three-address instruction format, each address field specifies the location of an operand. These operands can be located either in a processor register or in a memory location. Therefore, an address field can specify either a memory operand (S1) or a processor register (S2). An implied accumulator register (S3) is characteristic of one-address instruction formats, not three-address formats.

Statement I is false because TCP sequence numbers are byte-oriented. The sequence number of the next segment is the current sequence number plus the number of bytes in the current segment, not simply m+1. For example, if a segment starts at byte 1000 and contains 500 bytes, the next segment will start at byte 1500.

Statement III is false because the receiver's advertised window size can change during a connection. The receiver adjusts this value based on its available buffer space, which fluctuates as the application layer consumes data.

Statement II is false. XML is case-sensitive, meaning <Tag> and <tag> are considered different. In contrast, HTML is case-insensitive.

Statement IV is false. XML has a strict syntax that requires all tags to be properly closed (e.g., <p>...</p> or <br/>). In HTML, some tags (like <br> or <img>) do not require an explicit closing tag.

When a router forwards an IP packet, it modifies certain header fields. The Time to Live (TTL) is decremented at each hop to prevent indefinite packet looping. If the TTL changes, the header checksum must be recalculated. The length field might also change if the packet is fragmented. However, the Source IP Address, which identifies the original sender, must remain unchanged throughout the packet's journey to the destination.

HTTP can use multiple TCP connections, especially in its non-persistent mode, where a separate connection is established for each object (like an image or script) on a webpage. FTP inherently uses two parallel TCP connections: one for control commands (like user authentication) and another for the actual data transfer. Protocols like TELNET and SMTP typically maintain a single TCP connection for the duration of a session.

I. A context-free language ($L_1$) is a subset of recursive languages. Since recursive languages are closed under complementation, the complement $\bar{L_{1}}$ is also recursive. This statement is true.
IV. As established, $\bar{L_{1}}$ is recursive, which implies it is also recursively enumerable (RE). The language $L_2$ is given as RE. The set of RE languages is closed under the union operation. Therefore, $\bar{L_{1}} \cup L_{2}$ is necessarily recursively enumerable. This statement is also true.
Statements II and III are not necessarily true.

The total logical address space is $2^{32}$ bytes, as addresses are 32-bit. The page size is 4 kilobytes, which is $2^{12}$ bytes.
The number of pages in the logical address space is the total address space divided by the page size:
Number of pages = $\frac{2^{32}}{2^{12}} = 2^{20}$.
The page table must have one entry for each page, so there are $2^{20}$ entries. Each entry is 4 bytes.
Total page table size = (Number of entries) $\times$ (Size of an entry) = $2^{20} \times 4$ bytes = $2^{20} \times 2^2$ bytes = $2^{22}$ bytes.
Since 1 MB = $2^{20}$ bytes, the size is $4$ MB.

The initial value of B is 2. The final value of B depends on the interleaving of the execution of P1 and P2.

1. P1 then P2: P1 calculates C=1, B=2. Then P2 calculates D=4, B=3. Final B is 3.
2. P2 then P1: P2 calculates D=4, B=3. Then P1 calculates C=2, B=4. Final B is 4.
3. Interleaved: P1 calculates C=1. Then P2 runs completely, calculating D=4 and setting B=3. Finally, P1's last step executes, setting B = 2*C = 2. Final B is 2.
   The possible distinct values for B are 2, 3, and 4. Thus, there are 3 distinct values.

The SELECT operation in SQL corresponds to the projection operation ($\pi$) in relational algebra, as both are used to select specific columns from a table. However, there is a key difference. The standard projection operation in relational algebra implicitly removes duplicate tuples from the result. In contrast, the SQL SELECT statement, by default, retains all duplicate rows. To achieve the duplicate-eliminating behavior of relational algebra's projection, one must use SELECT DISTINCT in SQL.

A clustered index is a special type of index that reorders the way records in the table are physically stored on disk. Because the data rows themselves are stored in a specific order, there can be only one clustered index per table. This is in contrast to a non-clustered index, which has a separate structure from the data rows that points back to them.

The LU decomposition is given by the equation $A = LU$. We are given

and the structure of L and U, where U has 1s on its diagonal.
$\begin{bmatrix} 2 & 2\\ 4&9 \end{bmatrix} = \begin{bmatrix} l_{11} & 0\\ l_{21}&l_{22} \end{bmatrix} \begin{bmatrix} 1 & u_{12}\\ 0&1 \end{bmatrix}$
By matrix multiplication:

1. $l_{11} \cdot 1 = 2 \implies l_{11} = 2$.
2. $l_{21} \cdot 1 = 4 \implies l_{21} = 4$.
3. $l_{11} \cdot u_{12} = 2 \implies 2 \cdot u_{12} = 2 \implies u_{12} = 1$.
4. $l_{21} \cdot u_{12} + l_{22} \cdot 1 = 9 \implies 4 \cdot 1 + l_{22} = 9 \implies l_{22} = 5$.

The function f1 uses pass-by-value, so the swap performed inside it does not affect the variables a and b in the main function. Their values remain a=4 and b=5.
The function f2 is called with the addresses of b and c, implementing a pass-by-reference. This successfully swaps the values of b and c in main. So, b becomes 6 and c becomes 5.
The final printf statement calculates c-a-b, which evaluates to $5 - 4 - 6 = -5$.

The time complexity for insertion and deletion operations in a Binary Search Tree (BST) is proportional to the height of the tree, denoted as $h$. In the worst-case scenario, the BST can become a skewed or degenerate tree, where each node has only one child. This structure resembles a linked list. For a tree with $n$ nodes, the height of such a skewed tree is $n-1$. Therefore, the worst-case time complexity for both insertion and deletion is $\Theta(n)$.

Let $T_t$ be the transmission time and $T_p$ be the propagation delay. The link utilization ($\eta$) for the stop-and-wait protocol is given by $\eta = \frac{T_t}{T_t + 2T_p}$.
To achieve a utilization of at least 50% ($\eta \ge 0.5$), we must have $\frac{T_t}{T_t + 2T_p} \ge 0.5$, which simplifies to $T_t \ge 2T_p$.
Given $T_p = 20$ ms, the round-trip time is $2T_p = 40$ ms.
The bit rate is 64 kbps. Let the frame size be $x$ bits.
$T_t = \frac{x}{64 \times 10^3}$ seconds.
So, $\frac{x}{64000} \ge 40 \times 10^{-3} \implies x \ge 2560$ bits.
In bytes, the minimum size is $\frac{2560}{8} = 320$ bytes.

To insert a new value into a max heap, the value is first added to the end of the array, which corresponds to the next available leaf position in the tree. The new value, 35, is then compared with its parent. If it is greater than its parent, they are swapped. This "bubble-up" process continues until the new value is less than or equal to its parent, or it becomes the root. In this case, 35 is first swapped with its parent 15, and then with its new parent 30. The process stops as 35 is less than its next parent, 40, thus restoring the max-heap property.

Cyclomatic complexity is a software metric used to indicate the complexity of a program. It is a quantitative measure of the number of linearly independent paths through a program's source code. For a single program, it can be calculated using the formula $M = E - N + 2$, where E is the number of edges and N is the number of nodes in the Control Flow Graph (CFG). For the given code segment, the CFG has 10 nodes and 13 edges. Therefore, the complexity is $M = 13 - 10 + 2 = 5$.

For a frame to be sent without collision, exactly one of the four stations must transmit while the other three remain silent. The total probability is the sum of the probabilities of these four mutually exclusive events.
Let $P_i$ be the probability that station $S_i$ transmits. The probability of a successful transmission is:
$P(S_1 \text{ only}) + P(S_2 \text{ only}) + P(S_3 \text{ only}) + P(S_4 \text{ only})$
$= P_1(1-P_2)(1-P_3)(1-P_4) + (1-P_1)P_2(1-P_3)(1-P_4) + \dots$
Substituting the given values yields the final probability.

The truth table provided for the operator $\neq$ corresponds exactly to the logical XOR (exclusive OR) operation. The output is true (1) if and only if the inputs are different. The XOR operation is a fundamental binary operation in logic and computer science, and it is well-established that it is both commutative ($p \oplus q = q \oplus p$) and associative ($p \oplus (q \oplus r) = (p \oplus q) \oplus r$).

The general term of the series, $\frac{1}{x(x+1)}$, can be decomposed into partial fractions as $\frac{1}{x} - \frac{1}{x+1}$. When the summation is expanded, it becomes a telescoping series:
$\left(\frac{1}{1} - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \left(\frac{1}{3} - \frac{1}{4}\right) + \dots + \left(\frac{1}{99} - \frac{1}{100}\right)$
All the intermediate terms cancel out, leaving only the first term, $1$, and the last term, $-\frac{1}{100}$. The sum is therefore $1 - \frac{1}{100} = \frac{99}{100} = 0.99$.

The total number of ordered triplets $(x, y, z)$ from the set $L$ is $5^3 = 125$. The given equation, $x\vee (y \wedge z)=(x\vee y)\wedge (x\vee z)$, is the distributive property for a lattice.

The property does not hold for all triplets. For example, if we take $x=q, y=r, z=s$:

• $x \vee (y \wedge z) = q \vee (r \wedge s) = q \vee p = q$.
• $(x \vee y) \wedge (x \vee z) = (q \vee r) \wedge (q \vee s) = t \wedge t = t$.
  Since $q \neq t$, the property fails, meaning the probability $P_r$ is less than 1.

However, the property holds for some triplets. For instance, if $x=t$ (the maximum element), the equation becomes $t \vee (...) = (t \vee ...) \wedge (t \vee ...)$, which simplifies to $t = t \wedge t = t$. This is always true. There are $1 \times 5 \times 5 = 25$ such triplets. Thus, $P_r \ge \frac{25}{125} = \frac{1}{5}$. Since other combinations also satisfy the property, $P_r > \frac{1}{5}$.

Combining these, we get $\frac{1}{5} < P_r < 1$.

A set of Boolean functions is functionally complete if it does not belong to any of the five classes in Post's lattice: T0 (0-preserving), T1 (1-preserving), L (linear), M (monotone), and S (self-dual).

Let's analyze $g(X,Y,Z)$. If we set all inputs to 0, $g(0,0,0) = 0'00 + 0'00' + 00 = 0$. Since $g(0,0,0)=0$, the function g preserves zero (is in T0). Therefore, {g} is not functionally complete.

Now, let's analyze $f(X,Y,Z)$.

• For input (0,0,0): $f(0,0,0) = 0'00 + 00' + 0'0' = 1$. Since $f(0,0,0) \neq 0$, it does not preserve zero.
• For input (1,1,1): $f(1,1,1) = 1'11 + 11' + 1'1' = 0$. Since $f(1,1,1) \neq 1$, it does not preserve one.

The function f also does not satisfy the properties of linearity, monotonicity, or self-duality. Since it satisfies none of the five properties, {f} is functionally complete.

For a connected planar graph, Euler's formula states that $v - e + f = 2$, where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces.
We are given $v = 10$.

The problem also states that each face is bounded by 3 edges. Since every edge in a planar graph is shared by exactly two faces, we can establish a relationship between the number of edges and faces: $3f = 2e$, which implies $f = \frac{2e}{3}$.

Substituting these values into Euler's formula:
$10 - e + \frac{2e}{3} = 2$
$8 = e - \frac{2e}{3}$
$8 = \frac{e}{3}$
$e = 24$
Thus, the number of edges in G is 24.

Let $a_n$ be the number of bit strings of length $n$ that contain two consecutive 1s. We can derive a recurrence relation by considering how such a string can be formed. A valid string of length $n$ can end in 0 or 1.

1. The string ends in 0: The prefix of length $n-1$ must contain '11'. There are $a_{n-1}$ such strings.
2. The string ends in 1:
   • The string ends in '01': The prefix of length $n-2$ must contain '11'. There are $a_{n-2}$ such strings.
   • The string ends in '11': The '11' pattern is satisfied by the last two bits. The prefix of length $n-2$ can be any bit string. There are $2^{n-2}$ such strings.

Since these cases are mutually exclusive, we can sum them to get the total count:
$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$.

A variable is "live" at a statement if its current value may be used in a subsequent path before it is reassigned. We need to find the variables that are live at the start of both basic block 2 and basic block 3.

Live variables at the start of Block 2 (v=r+u):

• r and u are used in this block, so they are live.
• The value of r is also used later in block 4 (q=v+r), and there is a path from block 2 to 4 without r being redefined.

Live variables at the start of Block 3 (q=s*u):

• s and u are used in this block, so they are live.
• The value of r is used in block 4, and there is a path from block 3 to 4 without r being redefined. So, r is also live here.

The set of variables live at the start of block 2 is {r, u}. The set of variables live at the start of block 3 includes {r, s, u, v}. The intersection of these sets, representing variables live at both points, is {r, u}.

To create a three-address code in Static Single Assignment (SSA) form, each intermediate result must be stored in a new, unique temporary variable. The expression is q + r/3 + s - t*5 + u*v/w. We can break it down as follows:

1. t1 = r / 3
2. t2 = t * 5
3. t3 = u * v
4. t4 = t3 / w
5. t5 = q + t1
6. t6 = t5 + s
7. t7 = t6 - t2
8. t8 = t7 + t4

This sequence requires 8 distinct temporary variables (t1 through t8) to hold each intermediate result, satisfying the SSA requirement that each variable is assigned only once.

To convert the ER model to a relational model in 3NF, we follow standard mapping rules:

1. Each strong entity set gets its own relation. This gives us three relations:
   • E1(a11, a12) with a11 as the primary key.
   • E2(a21, a22) with a21 as the primary key.
   • E3(a31, a32) with a31 as the primary key.
2. The m:n relationship R12 requires a separate relation containing the primary keys of the participating entities:
   • R12(a11, a21)
3. For the 1:n relationship R13, the primary key of the entity on the '1' side (E1) is included as a foreign key in the relation for the 'n' side (E3). The E3 relation is modified to E3(a31, a32, a11).

This process results in a total of four relations: E1, E2, the modified E3, and R12.

First, let's determine the languages accepted by each DFA.

• DFA M accepts all strings that end with the symbol 'a'. Its language is $L(M) = \{w \in \{a,b\}^* \mid w \text{ ends with 'a'}\}$.
• DFA N accepts all strings that end with the symbol 'b'. Its language is $L(N) = \{w \in \{a,b\}^* \mid w \text{ ends with 'b'}\}$.

The question asks for a minimal DFA for the intersection of these languages, $L(M) \cap L(N)$. A string in the intersection must end with 'a' and also end with 'b', which is impossible. Therefore, the intersection is the empty language, $\emptyset$. The minimal DFA for the empty language consists of a single, non-accepting start state.

The problem involves scheduling three tasks (T1, T2, T3) based on their periods and execution times, using a preemptive, priority-based scheduler. The priority is the inverse of the period, so T1 (3ms period) has the highest priority, followed by T2 (7ms), and T3 (20ms) has the lowest.

The execution timeline is as follows:

• 0-1ms: T1 runs (1ms execution).
• 1-3ms: T2 runs (2ms execution).
• 3-4ms: A new instance of T1 arrives and runs.
• 4-6ms: T3 starts and runs for 2ms.
• 6-7ms: A new T1 arrives, preempts T3, and runs.
• 7-9ms: A new T2 arrives and runs.
• 9-10ms: A new T1 arrives and runs.
• 10-12ms: T3 resumes and completes its remaining 2ms of execution.

Thus, the first instance of T3 finishes at the end of 12 milliseconds.

Let's trace the state of the JK flip-flop's output, Q_JK, at each clock cycle. The D flip-flop's output is Q_D. Initially, Q_JK = 0 and Q_D = 1.

1. Clock 1: The input to the D flip-flop is the current Q_JK (0), so Q_D becomes 0. The inputs to the JK flip-flop are J=K=Q_D=1 (toggle mode). Since Q_JK was 0, it toggles to 1. The new state is Q_JK = 1.
2. Clock 2: The input to D is Q_JK (1), so Q_D becomes 1. The inputs to JK are J=K=Q_D=0 (hold mode). Q_JK was 1, so it remains 1. The new state is Q_JK = 1.
3. Clock 3: The input to D is Q_JK (1), so Q_D becomes 1. The inputs to JK are J=K=Q_D=1 (toggle mode). Q_JK was 1, so it toggles to 0. The new state is Q_JK = 0.

The sequence of Q_JK starting from the initial state is 0, 1, 1, 0, and this pattern repeats. Therefore, the generated bit sequence is 0110110...

The total time to read the file is the sum of the time for all sector accesses plus the total data transfer time.

1. Time for one rotation: $60 \text{ sec} / 10000 \text{ RPM} = 0.006 \text{ sec} = 6 \text{ ms}$.
2. Average rotational latency: Half of one rotation time, which is $6 \text{ ms} / 2 = 3 \text{ ms}$.
3. Time per sector access: This is the sum of seek time and rotational latency, as a seek is required for each sector. Time = $4 \text{ ms} + 3 \text{ ms} = 7 \text{ ms}$.
4. Total access time for 2000 sectors: $2000 \times 7 \text{ ms} = 14000 \text{ ms}$.
5. Data transfer rate: (Bytes per track) / (Rotation time) = $(600 \times 512 \text{ bytes}) / 6 \text{ ms} = 51200 \text{ B/ms}$.
6. Total transfer time: (Total file size) / (Transfer rate) = $(2000 \times 512 \text{ bytes}) / 51200 \text{ B/ms} = 20 \text{ ms}$.
7. Total time: $14000 \text{ ms} + 20 \text{ ms} = 14020 \text{ ms}$.

Speedup is the ratio of the execution time on the old (non-pipelined) processor to the new (pipelined) one.

1. Old Processor Execution Time:

   • Clock Rate = 2.5 GHz, so Cycle Time = $1 / (2.5 \times 10^9) \text{ s} = 0.4 \text{ ns}$.
   • Average CPI = 4.
   • Time per instruction = CPI $\times$ Cycle Time = $4 \times 0.4 \text{ ns} = 1.6 \text{ ns}$.

2. New Processor Execution Time:

   • Clock Rate = 2 GHz, so Cycle Time = $1 / (2 \times 10^9) \text{ s} = 0.5 \text{ ns}$.
   • For an ideal pipeline with no stalls, CPI = 1.
   • Time per instruction = CPI $\times$ Cycle Time = $1 \times 0.5 \text{ ns} = 0.5 \text{ ns}$.

3. Speedup:

   • Speedup = Old Time / New Time = $1.6 \text{ ns} / 0.5 \text{ ns} = 3.2$.

First, we calculate the total distance traversed by the R/W head for both algorithms, starting at track 50. The request queue is: 45, 20, 90, 10, 50, 60, 80, 25, 70.

1. SSTF (Shortest Seek Time First): The head moves to the nearest requested track.

   • Path: 50 → 45 → 60 → 70 → 80 → 90 → 25 → 20 → 10
   • Total distance = $5 + 15 + 10 + 10 + 10 + 65 + 5 + 10 = 130$ tracks.

2. SCAN (Elevator), moving towards 100: The head moves in one direction (towards 100), servicing requests, until it hits the end, then reverses.

   • Path: 50 → 60 → 70 → 80 → 90 → 100 (edge) → 45 → 25 → 20 → 10
   • Total distance = $(100 - 50) + (100 - 10) = 50 + 90 = 140$ tracks.

The PDF also considers the LOOK algorithm (a variant of SCAN where the head reverses at the last request, not the edge), which would travel $(90-50) + (90-10) = 120$ tracks. The question asks for the difference between SSTF and SCAN.

Additional distance = $|SSTF_{dist} - SCAN_{dist}| = |130 - 140| = 10$.

To determine which page replacement policy has more faults, we trace the execution for the given reference string with 5 page frames.

For the First-In-First-Out (FIFO) policy, a page fault occurs when a requested page is not in memory, and the page that has been in memory the longest is replaced. Tracing the sequence results in 9 page faults.

For the Least Recently Used (LRU) policy, a page fault leads to the replacement of the page that has not been used for the longest period. Tracing the sequence for LRU also results in 9 page faults.

Since both policies result in the same number of page faults, they incur the same cost.

This definite integral can be solved using the method of substitution. Let $u = 1/x$. The differential $du$ is then $du = -1/x^2 \, dx$, which means $1/x^2 \, dx = -du$.

We must also change the limits of integration. When $x = 1/\pi$, $u = \pi$. When $x = 2/\pi$, $u = \pi/2$.

The integral transforms to:
$\int_{\pi}^{\pi/2} \cos(u) (-du) = \int_{\pi/2}^{\pi} \cos(u) \, du$
$= [\sin(u)]_{\pi/2}^{\pi} = \sin(\pi) - \sin(\pi/2) = 0 - 1 = -1$

The provided pseudo code implements the algorithm for integer division. The variable r is initialized with the dividend x, and the variable q (the quotient) is initialized to 0.

The while loop repeatedly subtracts the divisor y from r as long as r is greater than or equal to y. For each successful subtraction, the quotient q is incremented.

The loop terminates when r < y, at which point r holds the remainder of the division. The relationship between these variables is defined by the division algorithm: $x = q \cdot y + r$, with the condition that the remainder r is less than the divisor y.

The eigenvalues $\lambda$ of a matrix A are the roots of its characteristic equation, $|A - \lambda I| = 0$. For the given matrix

, the equation is:
$(1-\lambda)(a-\lambda) - 4b = 0$
We are given two eigenvalues, $\lambda = -1$ and $\lambda = 7$. Substituting these values gives a system of two linear equations:

1. For $\lambda = -1$: $(1 - (-1))(a - (-1)) - 4b = 0 \implies 2(a+1) - 4b = 0 \implies 2b - a = 1$.
2. For $\lambda = 7$: $(1 - 7)(a - 7) - 4b = 0 \implies -6(a-7) - 4b = 0 \implies 2b + 3a = 21$.

Solving this system of equations yields $a = 5$ and $b = 3$.

The problem requires selecting the most suitable data structure based on the frequency of different operations to achieve the best total asymptotic complexity. The algorithm performs $N$ insertions, which is asymptotically a much larger number of operations compared to the $(\log N)^{1/2}$ find, delete, and decrease-key operations.

Because the number of insert operations dominates, the complexity of a single insertion is the most critical factor for the total time complexity. We compare the insertion costs:

• Unsorted array: $O(1)$
• Min-heap: $O(\log N)$
• Sorted array/list: $O(N)$

The unsorted array offers the lowest cost for the most frequent operation, making it the most suitable choice to optimize the overall performance.

The SQL query joins the Student and Performance tables on Roll_No. It then groups the results by Student_Name and calculates the sum of Marks for each student. In the Student table, there are two distinct student names: 'Raj' and 'Rohit'. The GROUP BY clause will create one output row for each of these distinct names, containing the student's name and their total marks. Therefore, the query will return exactly two rows.

The variable x is a 2D array int x[4][3] with a base address of 2000. An integer occupies 4 bytes.

1. x+3: x is a pointer to an array of 3 integers. The size of this array is $3 \times 4 = 12$ bytes. x+3 points to the 4th such array, so its address is $2000 + 3 \times 12 = 2036$.
2. *(x+3): This dereferences x+3, yielding the address of the 4th array itself, which is also 2036.
3. *(x+2)+3: *(x+2) is the address of the 3rd array, which is $2000 + 2 \times 12 = 2024$. Adding 3 to this pointer moves it forward by $3 \times 4 = 12$ bytes. The final address is $2024 + 12 = 2036$.
   All three expressions evaluate to 2036.

The total weight of the Minimum Spanning Tree (MST) is 36. The edges not in the MST are (A,B), (C,D), and (E,D). According to the cut property of MSTs, for any cycle, the weight of an edge not in the MST must be greater than the weight of any edge on the path in the MST that connects its endpoints.

• For edge (A,B), the path in the MST is A-C-B. The maximum edge weight on this path is 9. So, weight(A,B) > 9. The minimum integer weight is 10.
• For edge (C,D), the path is C-B-E-F-D. The max edge weight is 15. So, weight(C,D) > 15. Minimum is 16.
• For edge (E,D), the path is E-F-D. The max edge weight is 6. So, weight(E,D) > 6. Minimum is 7.
  The minimum sum of all 8 edges is the MST weight plus the minimum weights of the other edges: $36 + 10 + 16 + 7 = 69$.

The given pseudocode implements the division algorithm for positive integers x and y.

1. r is initialized to the dividend x.
2. q is initialized to 0 and acts as the quotient.
3. The while loop repeatedly subtracts the divisor y from the remainder r and increments the quotient q for each successful subtraction.
4. The loop terminates when r becomes less than y.
   At the end, r holds the remainder and q holds the quotient. The fundamental property of division is dividend = (quotient * divisor) + remainder, which translates to $x = qy + r$. The loop's termination condition is $r < y$.