GATE CSE 2015 SET 3

The relationship between the letters in "ROAD" and "URDG" follows a simple pattern. Each letter in the original word is shifted forward by three positions in the alphabet to get the corresponding letter in the coded word. For example, R is the 18th letter, and U is the 21st (18+3). Applying this +3 shift to "SWAN" gives: S(19)+3 -> V(22), W(23)+3 -> Z(26), A(1)+3 -> D(4), and N(14)+3 -> Q(17). Thus, the coded word is "VZDQ".

The definite article "the" is used because a specific version of the film is mentioned ("The Tamil version"). The verb "was" agrees with the singular subject "version". The past tense "found" is appropriate for the distributor's action. The preposition "on" is correctly used to specify a day of the week for the release ("on this Friday").

The sentence describes how students focus so intensely on the syllabus that they ignore other things. The word "extraneous" means irrelevant or unrelated to the subject being dealt with. This fits the context perfectly, as it implies that students close their minds to anything that is not directly part of the exam requirements. The other options do not convey this meaning of being outside the necessary scope.

The original pair shows a specific group of people (Children) and the medical specialist who treats them (Pediatrician). The best analogy is "Females : Gynaecologist," as it also links a specific demographic group to their corresponding medical specialist. The other options relate a body part (Kidney, Skin) or a very broad group (Adult) to a specialist, making them less precise analogies.

A linear function has the form $f(x) = mx + c$. We are given two points: $f(-2) = 29$ and $f(3) = 39$. The slope $m$ can be calculated as the change in $f(x)$ divided by the change in $x$: $m = \frac{39 - 29}{3 - (-2)} = \frac{10}{5} = 2$. Using the point-slope form with the point $(3, 39)$, we get $f(x) - 39 = 2(x - 3)$, which simplifies to $f(x) = 2x + 33$. To find the value at $x=5$, we calculate $f(5) = 2(5) + 33 = 10 + 33 = 43$.

The statement "Alexander turned his attention towards India, since he had conquered Persia" uses the word "since" to indicate a reason. This establishes a conditional relationship: conquering Persia was a necessary condition for turning his attention to India. This can be written as "If Alexander turned to India, it is because he had conquered Persia." The logically equivalent contrapositive is "If he had not conquered Persia, he would not have turned his attention to India," which matches option A.

We can validate the portfolio distribution by checking each option against the given conditions.

1. U gets no portfolio if S does.
2. R wants Home, Finance, or nothing.
3. If S gets Power or Telecom, Q must get the other.
4. If P gets a portfolio, T must too.

Let's check option B: R-Home, S-Power, P-Defense, Q-Telecom, T-Finance.

• S has Power, so Q must have Telecom. (Condition 3 is met).
• P has a portfolio (Defense), and T also has one (Finance). (Condition 4 is met).
• R has Home. (Condition 2 is met).
• S has a portfolio, and U is the one left out with no portfolio. (Condition 1 is met).
  All conditions are satisfied.

The equation can be analyzed by considering two cases for the value of $y$.
Case 1: $y \ge 0$. In this case, $|y| = y$. The equation becomes $x = -(y - y) = 0$. This represents the non-negative y-axis.
Case 2: $y < 0$. In this case, $|y| = -y$. The equation becomes $x = -(y - (-y)) = -(y+y) = -2y$. Since $y$ is negative, $x$ is positive. This represents a straight line in the fourth quadrant passing through the origin.
The plot described by this equation consists of the non-negative y-axis and a line in the fourth quadrant.

Let's evaluate the inferences based on the passage.
(i) The passage states that success "will continue to elude him," which implies he is not yet successful at the highest level. So, (i) is false.
(ii) The passage identifies a "lack of requisite temperament" as the main issue. This implies he needs to improve it to succeed. So, (ii) is true.
(iii) The passage mentions he was "guilty of throwing away his wicket several time after working hard to lay a strong foundation," which means he failed to convert good starts. So, (iii) is true.
(iv) The passage says he already possesses the necessary technical skills. So, (iv) is false.
Thus, the only valid inferences are (ii) and (iii).

To solve this problem, one would need the data from the bar chart, which is not provided. The method would be as follows:

1. For each year from 2000 to 2007, calculate the total trade, $T_y = \text{Exports}_y + \text{Imports}_y$.
2. For each year from 2001 to 2007, calculate the percentage increase in total trade from the previous year using the formula:
   $\text{Percentage Increase}_y = \frac{T_y - T_{y-1}}{T_{y-1}} \times 100\%$
3. Compare the calculated percentage increases for all years to find the year in which the value is highest.

The character array s1 is initialized to "1234". The pointer p is made to point to the third element of s1 (the character '3') by the statement p = s1 + 2;. The next statement, *p = '0';, dereferences the pointer p and changes the value at that memory location to '0'. This modifies the original string s1 to "1204". Finally, printf("%s", s1); prints the entire modified string.

Let's analyze the options for the set S = {1, 2, 3, 4, 5, 6}.
A is false: If X = {1, 2}, then |X|=2. Its complement X' = {3, 4, 5, 6} has |X'|=4. So $|X| \neq |X'|$.
B is false: Any two subsets of size 5 from a set of 6 elements must have at least 4 elements in common. Their intersection cannot be empty.
C is false: If X = {1, 2} and Y = {3, 4, 5}, then X\Y = {1, 2}, which is not the empty set.
D is true: The expression X \ Y represents elements in X but not in Y, which is $X \cap Y'$. The expression Y' \ X' represents elements in Y' but not in X', which is $Y' \cap (X')' = Y' \cap X$. Both expressions are equivalent.

A functional dependency (FD) X $\rightarrow$ Y is defined as trivial if the set of attributes Y is a subset of the set of attributes X (i.e., $Y \subseteq X$). We can check the given options against this definition:
A. {P,R} $\rightarrow$ {S,T}: Not trivial as {S,T} is not a subset of {P,R}.
B. {P,R} $\rightarrow$ {R,T}: Not trivial as {R,T} is not a subset of {P,R}.
C. {P,S} $\rightarrow$ {S}: Trivial because {S} is a subset of {P,S}.
D. {P,S,U} $\rightarrow$ {Q}: Not trivial as {Q} is not a subset of {P,S,U}.

The number of CPUs in a system determines the maximum number of processes that can be in the Running state simultaneously. The Ready state, however, contains processes that are loaded in memory and are waiting for CPU time. The size of the ready queue is not constrained by the number of CPUs but rather by the amount of available system memory and operating system limits. A single-CPU system can have many processes in its ready queue. Therefore, the maximum number of processes in the Ready state is independent of n.

The hierarchy of LR parsers in terms of power is Canonical LR > LALR > SLR. In terms of implementation complexity and table size, the order is reversed: SLR < LALR < Canonical LR.
SLR (Simple LR) is the easiest to implement because it has the smallest parsing tables and uses a simpler algorithm.
Canonical LR (or LR(1)) is the most powerful as it can recognize all deterministic context-free languages, the largest set among the three.
Therefore, the pair that identifies the easiest to implement and the most powerful, in that order, is SLR and canonical LR.

The binary operator is defined as $X\#Y = X' + Y'$.
Statement S2 claims commutativity: $Q\#R = R\#Q$.
$Q\#R = Q' + R'$.
$R\#Q = R' + Q'$.
Since the Boolean OR operation is commutative, $Q' + R' = R' + Q'$, so S2 is true.

Statement S1 claims associativity: $(P\#Q)\#R = P\#(Q\#R)$.
Let's use a counterexample: $P=1, Q=1, R=0$.
LHS: $(1\#1)\#0 = (1'+1')\#0 = (0+0)\#0 = 0\#0 = 0'+0' = 1+1 = 1$.
RHS: $1\#(1\#0) = 1\#(1'+0') = 1\#(0+1) = 1\#1 = 1'+1' = 0+0 = 0$.
Since LHS $\neq$ RHS, S1 is false.

The Function Point (FP) is calculated as $FP = UFP \times VAF$.
First, calculate the Unadjusted Function Points (UFP) by summing the products of counts and weights:
$UFP = (30 \times 4) + (60 \times 5) + (23 \times 4) + (8 \times 10) + (2 \times 7) = 120 + 300 + 92 + 80 + 14 = 606$.

Next, calculate the Total Degree of Influence (TDI). Out of 14 factors, 4 are not applicable (value 0), 4 have value 3, and the remaining 6 have value 4.
$TDI = (4 \times 0) + (4 \times 3) + (6 \times 4) = 0 + 12 + 24 = 36$.

Then, find the Value Adjustment Factor (VAF):
$VAF = 0.65 + (0.01 \times TDI) = 0.65 + (0.01 \times 36) = 0.65 + 0.36 = 1.01$.

Finally, $FP = 606 \times 1.01 = 612.06$.

When an HTML page is saved and opened locally, its relative links resolve based on the local file system path, not the original server's URL. This causes the links to break. The <base> tag is designed to solve this problem by specifying a base URL for all relative paths in the document. By inserting <base href="http://www.yourname.com/"> into the <head> section of the local file W1, any relative link like "var.html" will be correctly interpreted by the browser as http://www.yourname.com/var.html.

I. TCP is full-duplex, meaning data can be sent and received simultaneously between two connected endpoints. This statement is correct.
II. Modern TCP implementations support the Selective Acknowledgment (SACK) option, which allows a receiver to inform the sender about all segments that have been successfully received. Therefore, the statement that TCP has no option for selective acknowledgement is false.
III. TCP provides a byte-stream service, not a message-stream service. It ensures that bytes are delivered in order but does not preserve the boundaries of the data chunks written by the sender. This statement is false.

The sum of the first $n$ cubes is given by the closed-form formula:
$\sum_{i=0}^{n}i^{3} = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n+1)^2}{4}$
Expanding this expression results in a polynomial whose highest-order term is $\frac{n^4}{4}$. Therefore, the sum $X$ has a tight asymptotic bound of $\Theta(n^4)$.

Let's evaluate the given choices:
I. $X = \Theta(n^4)$: This is true.
II. $X = \Theta(n^5)$: This is false.
III. $X = O(n^5)$: This is true, as $\Theta(n^4)$ is a subset of $O(n^5)$.
IV. $X = \Omega(n^3)$: This is true, as $\Theta(n^4)$ is a subset of $\Omega(n^3)$.
Thus, statements I, III, and IV are all correct.

For any non-empty binary tree, there is a property relating the number of leaf nodes (nodes with zero children) to the number of nodes with exactly two children. If $L$ is the number of leaf nodes and $N_2$ is the number of nodes with two children, then the relationship is $N_2 = L - 1$. Given that the tree has 200 leaf nodes ($L=200$), the number of nodes with exactly two children is $200 - 1 = 199$.

The load factor, $\alpha$, of a hash table is a measure of how full the table is. It is defined as the ratio of the number of elements stored in the table to the number of available slots.
Given the number of elements is 2000 and the number of slots is 25, the load factor is calculated as:
$\alpha = \frac{\text{Number of elements}}{\text{Number of slots}} = \frac{2000}{25} = 80$

To find the eigenvectors $X$ corresponding to an eigenvalue $\lambda$, we solve the equation $(A - \lambda I)X = 0$. Given the eigenvalue $\lambda = 1$, we have:
$(A - I)X = \begin{bmatrix} 1-1 & -1 & 2 \\ 0 & 1-1 & 0 \\ 1 & 2 & 1-1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$
This gives the system of equations: $-x_2 + 2x_3 = 0$ and $x_1 + 2x_2 = 0$. From the first equation, $x_2 = 2x_3$. Substituting this into the second equation gives $x_1 = -2x_2 = -4x_3$. The eigenvector is of the form $\alpha(-4, 2, 1)$ for any non-zero scalar $\alpha \in \mathbb{R}$.

The limit is of the indeterminate form $\infty ^0$. Let $L = \lim_{x\rightarrow \infty }(1+x^{2})^{e^{-x}}$. We can evaluate this by first taking the natural logarithm:
$\ln(L) = \lim_{x\rightarrow \infty } \ln((1+x^{2})^{e^{-x}}) = \lim_{x\rightarrow \infty } \frac{\ln(1+x^2)}{e^x}$
This is now of the form $\frac{\infty }{\infty }$, so we can apply L'Hôpital's Rule.
$\ln(L) = \lim_{x\rightarrow \infty } \frac{2x/(1+x^2)}{e^x} = \lim_{x\rightarrow \infty } \frac{2x}{(1+x^2)e^x} = 0$
Since $\ln(L) = 0$, we have $L = e^0 = 1$.

This problem is equivalent to finding the number of ways to choose 4 digits from the set {1, 2, 3} with repetition allowed. Since the digits must be in non-decreasing order, the selection of any 4 digits uniquely determines the number. This is a combination with repetition problem. Using the stars and bars formula, $\binom{n+k-1}{k}$, where $n$ is the number of items to choose from (3) and $k$ is the number of choices (4).
$\binom{3+4-1}{4} = \binom{6}{4} = \frac{6!}{4!2!} = \frac{6 \times 5}{2} = 15$

The statement is "The result of the toss is head if and only if I am telling the truth." Let's analyze the two possible cases for the person.

Case 1: The person is a Type 1 (truth-teller).
Their statement must be true. Since "I am telling the truth" is true, the other part of the biconditional, "The result of the toss is head," must also be true.

Case 2: The person is a Type 2 (liar).
Their statement must be false. For a biconditional to be false, the two parts must have different truth values. Since "I am telling the truth" is false, "The result of the toss is head" must be true.

In both scenarios, the result of the coin toss must be a head.

To find the element at the lowest level, we construct the Binary Search Tree (BST) by inserting the elements in the given order: 71, 65, 84, 69, 67, 83.

1. Insert 71 (root).
2. Insert 65 (left of 71).
3. Insert 84 (right of 71).
4. Insert 69 (right of 65).
5. Insert 67 (left of 69).
6. Insert 83 (left of 84).
   The resulting tree structure places 67 at level 3 (assuming the root is at level 0), which is the lowest level in the tree.

The postfix expression is evaluated using a stack. We scan the expression from left to right.

1. Push 10, Push 5. Stack: [10, 5]
2. Operator +: Pop 5, 10. Compute 10 + 5 = 15. Push 15. Stack: [15]
3. Push 60, Push 6. Stack: [15, 60, 6]
4. Operator /: Pop 6, 60. Compute 60 / 6 = 10. Push 10. Stack: [15, 10]
5. Operator *: Pop 10, 15. Compute 15 * 10 = 150. Push 150. Stack: [150]
6. Push 8. Stack: [150, 8]
7. Operator -: Pop 8, 150. Compute 150 - 8 = 142. Push 142. Stack: [142]
   The final result on the stack is 142.

The goal is to select addresses of theaters whose capacity is the maximum of all capacities. The subquery (select P2.capacity from Cinema P2) returns a list of all capacity values from the Cinema table. The ALL keyword is used to compare a value to every value in a list. The condition P1.capacity >= ALL (...) will only be true if P1.capacity is greater than or equal to every single capacity value returned by the subquery. This is logically equivalent to finding the rows where the capacity is the maximum.

To convert the given array into a max-heap, we need to ensure that every parent node is greater than its children. The initial array represented as a tree violates this property. The PDF solution identifies a sequence of 3 swaps to fix this. The element 100 is the largest but is initially a leaf node.

1. Swap 100 with its parent, 15.
2. Swap 100 with its new parent, 50.
3. Swap 100 with its new parent, 89.
   This process moves the largest element, 100, to the root position, satisfying the heap property for the nodes in its path. This requires a minimum of 3 interchanges.

The provided code implements a synchronization construct. If both processes X and Y execute their first line (varP = true; and varQ = true;) before either checks the while loop condition, both shared variables will be true. Consequently, process X will find varQ to be true and enter its critical section, and process Y will find varP to be true and also enter its critical section. Since both can be in the critical section simultaneously, mutual exclusion is not guaranteed. However, because both processes can proceed without waiting indefinitely for each other, there is no deadlock.

The language L consists of all strings containing the substring "0011". A minimal Deterministic Finite Automaton (DFA) that recognizes a language defined by a specific substring of length m requires m+1 states. For the substring "0011", m=4, so the DFA for L needs 5 states. The complement language, $\bar{L}$, contains all strings that do not have "0011" as a substring. A DFA for the complement language can be constructed from the DFA for L by swapping its final and non-final states. This operation does not change the total number of states. Therefore, the minimum number of states for the DFA recognizing $\bar{L}$ is also 5.

This problem can be solved using the capture-recapture estimation method. The ratio of detected seeded faults to the total number of seeded faults is assumed to be equal to the ratio of detected real faults to the total number of real faults.
Number of real faults detected = Total detected - Seeded detected = $159 - 75 = 84$.
Let R be the total number of real faults.
$\frac{\text{Detected Real}}{\text{Total Real}} = \frac{\text{Detected Seeded}}{\text{Total Seeded}} \implies \frac{84}{R} = \frac{75}{100}$
Solving for R gives $R = \frac{84 \times 100}{75} = 112$.
The number of undetected real faults is Total Real - Detected Real = $112 - 84 = 28$.

The main memory size is $2^{20}$ bytes, so physical addresses are 20 bits long. The block size is 16 bytes ($2^4$), which means the block offset requires the 4 least significant bits. The cache has $2^{12}$ lines, so in a direct-mapped cache, the cache line index requires 12 bits. The remaining most significant bits form the tag: $20 - 12 - 4 = 4$ bits.
The address $(E201F)_{16}$ in binary is 1110 0010 0000 0001 1111.
Partitioning the address:
Tag (4 bits): 1110 = $(E)_{16}$
Cache Line (12 bits): 0010 0000 0001 = $(201)_{16}$
Offset (4 bits): 1111
Thus, the tag is E and the cache line address is 201.

In a CSMA/CD network, the minimum frame transmission time ($T_t$) must be at least twice the maximum one-way propagation delay ($T_p$) to ensure collision detection. For the minimum frame size, we use the equality $T_t = 2T_p$.
$T_t = \frac{\text{Frame Size}}{\text{Bandwidth}} = \frac{1250 \text{ bytes} \times 8 \text{ bits/byte}}{100 \times 10^6 \text{ bps}} = \frac{10000}{10^8}$ s.
$T_p = \frac{\text{Distance}}{\text{Signal Speed}} = \frac{1 \text{ km}}{\text{Signal Speed}}$.
Setting $T_t = 2T_p$:
$\frac{10000}{10^8} = \frac{2 \times 1 \text{ km}}{\text{Signal Speed}}$
Signal Speed = $\frac{2 \times 10^8}{10000}$ km/s = $20000$ km/s.

Simpson's 1/3rd rule is a numerical method for approximating the value of a definite integral. The distance covered is the integral of the velocity function over the time interval [0, 20]. The rule approximates this integral using the formula:
$\int_{a}^{b} f(x) dx \approx \frac{h}{3} [y_0 + 4(y_1+y_3+...) + 2(y_2+y_4+...) + y_n]$
Here, the time interval $h=2$ minutes. Applying this formula to the provided table of velocity values results in an approximate distance of 309.33 kilometers.

The time complexity of mergesort is $O(n \log n)$. Therefore, the execution time $T$ is proportional to $n \log n$, so $T = c \cdot n \log_2 n$ for some constant $c$.
Given $T=30$s for $n=64$:
$30 = c \cdot 64 \log_2 64 = c \cdot 64 \cdot 6 \implies c = \frac{30}{384} = \frac{5}{64}$.
Now, we need to find the maximum input size $n$ that can be solved in 6 minutes (360 seconds):
$360 = \frac{5}{64} \cdot n \log_2 n$
$n \log_2 n = \frac{360 \cdot 64}{5} = 72 \cdot 64 = 4608$.
By testing the options, for $n=512$, we get $512 \log_2 512 = 512 \cdot 9 = 4608$.

The number of invocations can be found by tracing the recursive calls. Let $C(n)$ be the number of calls for get(n). The total number of calls is 1 (for the initial call) plus the calls made by its children.
$C(n) = 1 + C(n-1) + C(n-3)$ for $n \ge 1$. $C(n)=1$ for $n<1$.
$C(6) = 1 + C(5) + C(3)$
$C(5) = 1 + C(4) + C(2)$
$C(4) = 1 + C(3) + C(1)$
$C(3) = 1 + C(2) + C(0) = 1 + 3 + 1 = 5$
$C(2) = 1 + C(1) + C(-1) = 1 + 1 + 1 = 3$
$C(1) = 1 + C(0) + C(-2) = 1 + 1 + 1 = 3$
Tracing and summing all calls as shown in the PDF's call tree results in a total of 25 invocations.

In a B+ tree, a non-leaf node with $k$ keys contains $k+1$ block pointers. The total size of the keys and pointers must not exceed the block size.
Given: key size = 12 bytes, block pointer size = 8 bytes, block size = 1024 bytes.
The inequality is:
$k \times (\text{key size}) + (k+1) \times (\text{block pointer size}) \le \text{block size}$
$12k + 8(k+1) \le 1024$
$12k + 8k + 8 \le 1024$
$20k \le 1016$
$k \le 50.8$
Since the number of keys must be an integer, the maximum number of keys is 50.

The Boolean function is F = P' + QR. To find its canonical forms, we can create a truth table or use a Karnaugh map. The minterms are the input combinations for which F=1.
F is true if P=0, or if Q=1 and R=1.
The minterms are:
PQR=000 (m0), 001 (m1), 010 (m2), 011 (m3), and 111 (m7).
So, F = $\Sigma m(0, 1, 2, 3, 7)$. This makes statement (S2) true and (S1) false.
The maxterms are the remaining combinations: {4, 5, 6}.
So, F = $\Pi M(4, 5, 6)$. This makes statement (S3) true and (S4) false.

Polynomial time reducibility is a transitive relation. We are given that $L_1$ is reducible to $L_2$, $L_3$ is reducible to $L_2$, and $L_2$ is reducible to $L_4$.

I. If $L_4 \in P$ and $L_2$ is reducible to $L_4$, it implies that $L_2 \in P$. So, statement I is true.
IV. Since $L_4 \in P$ implies $L_2 \in P$, and both $L_1$ and $L_3$ are reducible to $L_2$, it follows that both $L_1 \in P$ and $L_3 \in P$. So, statement IV is also true.

Statements II and III are not necessarily true as the complexity of one language does not determine the complexity of another it reduces to.

The program evaluates the expression x += f1() + f2() + f3() + f2(), where the main function's x is initialized to 1.

1. f1() returns 26. It uses a local variable x.
2. The first call to f2() returns 51. It uses a static variable x, so its value is preserved across calls.
3. f3() uses the global x (initially 10), calculates 10 * 10 = 100, and returns 100.
4. The second call to f2() increments its static x from 51 to 52 and returns 52.
   The final value of x in main is 1 + 26 + 51 + 100 + 52 = 230.

The pointer ptr is initialized to point to the beginning of the array of pointers p. The statement ptr++ increments ptr to point to the second element of p, which is a+3.

1. ptr-p: This calculates the offset of ptr from the beginning of p. Since ptr was incremented once, the result is 1.
2. **ptr: This dereferences ptr twice.
   • *ptr evaluates to the value at the new ptr position, which is the address a+3.
   • **ptr evaluates to the value at the address a+3, which is the fourth element of array a, i.e., 40.
     The program prints 1 and 40.

A language is context-free if it can be recognized by a pushdown automaton (PDA).

• For $L_3 = \{a^m b^n | m=2n+1\}$, a PDA can be constructed. For each 'a' read, it can push two symbols onto the stack, and for each 'b' read, it can pop one symbol. An initial 'a' can handle the "+1".
• For $L_1 = \{a^m b^n a^n b^m | m,n \ge 1\}$, a PDA can be constructed to recognize it. It can push the initial $a^m b^n$ string and then pop symbols to match the subsequent $a^n b^m$ part.
• $L_2$ is not context-free as it requires matching two independent counts, which cannot be done with a single stack.

Deadlock can be prevented by breaking one of the four necessary conditions: mutual exclusion, hold and wait, no preemption, or circular wait.

• Policy I prevents the "hold and wait" condition by forcing a process to acquire all resources at once or release any it holds.
• Policies II, III, and IV all prevent the "circular wait" condition. By enforcing a strict ordering (either increasing or decreasing) on resource requests, a cycle of processes waiting on each other cannot form.
  Since all four policies effectively break at least one of the necessary conditions, any of them can be used to prevent deadlock.

The given network is 200.10.11.144/27. The /27 suffix indicates that the first 27 bits are the network portion, leaving $32 - 27 = 5$ bits for the host portion.

The last octet, 144, is 10010000 in binary. The network mask for /27 in the last octet is 11100000 (224). The network address is 144 AND 224, which is 128. So, the network is 200.10.11.128/27.

The broadcast address is found by setting all 5 host bits to 1. The network part is 100. So, the last octet is 10011111, which is 159. The last usable host address is one less than the broadcast address, which is 158.

First, calculate the one-way propagation delay ($T_p$) and the transmission delay ($T_t$).
$T_p = \frac{\text{Distance}}{\text{Speed}} = \frac{8000 \times 10^3 \text{ m}}{4 \times 10^6 \text{ m/s}} = 2$ seconds.
$T_t = \frac{\text{Packet Size}}{\text{Bandwidth}} = \frac{10^7 \text{ bits}}{500 \times 10^6 \text{ bps}} = 0.02$ seconds.

To achieve full capacity, the sender must be able to transmit continuously for one full Round Trip Time (RTT), which is $2 \times T_p = 4$ seconds. The number of packets that can be sent in this time is the required window size (W):
$W = \frac{\text{RTT}}{T_t} = \frac{4}{0.02} = 200$ packets.

For the Go-Back-N protocol, the number of sequence numbers ($2^m$) must be greater than the window size. We need at least $W+1 = 201$ sequence numbers. To represent 201 sequence numbers, we need $m$ bits such that $2^m \ge 201$.
$2^7 = 128$ (insufficient)
$2^8 = 256$ (sufficient)
Thus, a minimum of 8 bits are required for the sequence number field.

To find the Minimum Average Latency (MAL), we first identify the forbidden latencies from the reservation table. A forbidden latency is the difference in time units between any two uses of the same stage.

• Stage S1 is used at times 1 and 4. The difference is $4-1=3$.
• Stage S2 is used at times 2 and 5. The difference is $5-2=3$.
• Stage S3 is used only at time 3.

The set of forbidden latencies is {3}. The analysis then proceeds by finding latency cycles in the state diagram. The PDF's analysis identifies a simple cycle with a latency of 3. A simple cycle represents a repeating pattern of initiations. The average latency for this simple cycle is 3. The PDF also considers another cycle (1, 5) whose average latency is $(1+5)/2 = 3$. The minimum of these is 3.

An anti-dependency (Write-After-Read, WAR) occurs when an instruction writes to a location that was read by a preceding instruction.

• S1: I2 writes to R7 and I5 also writes to R7. This is a Write-After-Write (output) dependency, not an anti-dependency. So, S1 is false.
• S2: I2 reads register R3. The later instruction I4 writes to register R3. This creates a WAR hazard, so there is an anti-dependency between I2 and I4. So, S2 is true.
• S3: Anti-dependencies do not always cause stalls. Techniques like register renaming, used in modern processors, can eliminate WAR hazards by assigning a new physical register to the write operation, thus allowing instructions to execute out of order without stalling. So, S3 is false.

Therefore, only statement S2 is correct.

• S1: In segment 1, Y[i] is assigned X[0][i]. Since X[i][j] = i+j, X[0][i] = 0+i = i. So, Y[i] becomes i. In segment 2, Y[i] is assigned X[i][0], which is i+0 = i. So, Y[i] also becomes i. The final contents of Y are identical in both cases. S1 is correct.
• S2: C stores 2D arrays in row-major order. Segment 1 accesses X[0][0], X[0][1], X[0][2], .... These are adjacent elements within the first row and are therefore contiguous in memory. S2 is correct.
• S3: Segment 2 accesses X[0][0], X[1][0], X[2][0], .... This is a column-wise access. In row-major layout, these elements are separated by the length of a full row in memory and are not contiguous. S3 is incorrect.

Thus, only statements S1 and S2 are correct.

In the given schedule, transaction T2 reads data item 'A' which was written by transaction T1. Subsequently, T2 commits at time instance 8, before T1 has committed. If T1 fails at time instance 9, the value of 'A' that T2 read and used for its commit is now invalid (a dirty read). Since T2 has already committed, its effects cannot be rolled back, leading to an inconsistent database state. This type of schedule is known as non-recoverable and cannot guarantee transaction atomicity.

The given system of linear equations is a homogeneous system. For such a system to have a non-trivial solution, the determinant of the coefficient matrix must be zero.
The coefficient matrix is:
$A = \begin{pmatrix} p & q & r \\ q & r & p \\ r & p & q \end{pmatrix}$
Setting its determinant to zero: $|A| = p(rq - p^2) - q(q^2 - rp) + r(qp - r^2) = 0$.
This simplifies to $3pqr - p^3 - q^3 - r^3 = 0$, which factors into $-(p+q+r)(p^{2+}q^{2+}r^{2-}pq-qr-rp) = 0$.
This condition is true if either $p+q+r=0$ or $p=q=r$.

First, we evaluate the initial values of j and k.
j = 2 * 3 / 4 + 2.0 / 5 + 8 / 5 evaluates to 6 / 4 + 0.4 + 1, which is 1 + 0.4 + 1 = 2.4. As j is an integer, it is assigned the value 2.
Next, k -= --j; first decrements j to 1 (pre-decrement), then k becomes 0 - 1 = -1.
The for loop runs for i from 0 to 4. The switch statement lacks breaks, causing fall-through.

• i=0, i+k=-1: default (1 printf)
• i=1, i+k=0: default (1 printf)
• i=2, i+k=1: case 1, case 3, default (3 printfs)
• i=3, i+k=2: case 2, case 3, default (3 printfs)
• i=4, i+k=3: case 3, default (2 printfs)
  Total executions: 1 + 1 + 3 + 3 + 2 = 10.

The given functional equation is $af(x)+bf\left ( \frac{1}{x} \right )=\frac{1}{x}-25$.
To solve for $f(x)$, we can create a system of two equations. Replace $x$ with $1/x$ in the original equation to get the second equation: $af\left ( \frac{1}{x} \right )+bf(x)=x-25$.
Now, solve this system for $f(x)$. Multiplying the first equation by $a$ and the second by $b$ and then subtracting gives:
$(a^{2-}b^2)f(x) = a(\frac{1}{x}-25) - b(x-25)$.
$f(x) = \frac{1}{a^{2-}b^2} [ \frac{a}{x} - bx - 25a + 25b ]$.
Integrating from 1 to 2:
\int_{1}^{2}f(x)dx = \frac{1}{a^{2-}b^2} \[a\ln x - \frac{bx^2}{2} - (25a-25b)x]_1^2 = \frac{1}{a^{2-}b^2}[a(\ln2-25)+\frac{47b}{2}]$.

A minimum spanning tree (MST) of a connected graph with $V$ vertices always contains exactly $V-1$ edges. For a graph with 100 vertices, its MST will have $100 - 1 = 99$ edges.
When the weight of every edge in the graph is increased by 5, the set of edges forming the MST remains the same, but the weight of each of these 99 edges increases by 5.
The total increase in the weight of the MST is the number of edges multiplied by the weight increase per edge: $99 \times 5 = 495$.
The new weight of the MST is the original weight plus this total increase: $500 + 495 = 995$.

The total data to be sent is 10000 bits, with a packet size of 5000 bits, meaning two packets (P1, P2) are transmitted. The switch is store-and-forward.

1. Transmission Time ($T_t$) for one packet:
   $T_t = \frac{\text{Packet Size}}{\text{Bandwidth}} = \frac{5000 \text{ bits}}{10^7 \text{ bps}} = 500 \mu s$.
2. Propagation Delay ($T_p$) per link is given as $20 \mu s$.
3. Switching Delay ($T_s$) is $35 \mu s$.

The time for the last bit of the last packet (P2) to arrive at the destination is calculated by tracing its journey:

• P2 transmission starts at $500 \mu s$ (after P1).
• Last bit of P2 leaves the source at $1000 \mu s$.
• Last bit of P2 arrives at the switch at $1000 + 20 = 1020 \mu s$.
• Switch forwards P2 after receiving it and waiting $35 \mu s$, starting at $1020 + 35 = 1055 \mu s$.
• Last bit of P2 leaves the switch at $1055 + 500 = 1555 \mu s$.
• Last bit of P2 arrives at the destination at $1555 + 20 = 1575 \mu s$.

Turnaround Time (TAT) is the difference between completion time and arrival time. We need to find the scheduling algorithm with the lowest average TAT.

1. First Come First Serve (FCFS): Avg TAT = 7.25
2. Non-preemptive Shortest Job First (SJF): Avg TAT = 6.75
3. Shortest Remaining Time (SRT): This is the preemptive version of SJF.
   • t=0: A starts.
   • t=1: B arrives (BT=6). A has 2 left. A continues.
   • t=3: A finishes. C (BT=4) is shorter than B (BT=6), so C starts.
   • t=4: D arrives (BT=2). D is shorter than C (rem=3), so D preempts C.
   • t=6: D finishes. C (rem=3) is shorter than B (BT=6), so C resumes.
   • t=9: C finishes. B starts.
   • t=15: B finishes.
   • TATs: A(3), B(14), C(5), D(0). Avg TAT = (3+14+5+0)/4 = 5.5.
4. Round Robin (q=2): Avg TAT = 8.25

Comparing the average TATs, Shortest Remaining Time (SRT) provides the lowest value.

McCabe's Cyclomatic Complexity (M) is calculated using the formula $M = E - N + 2P$, where E is the number of edges, N is the number of nodes, and P is the number of connected components in the control flow graph (CFG). For a single program, P=1.

• Program-X: The PDF calculates its complexity as 4. Using the formula with the provided counts: $E=11, N=9, P=1 \implies M = 11 - 9 + 2(1) = 4$.
• Program-Y: The CFG is given. By counting, there are $N=8$ nodes and $E=10$ edges.
  $M = 10 - 8 + 2(1) = 4$.
• Program-Z: The CFG is given. By counting, there are $N=17$ nodes and $E=22$ edges.
  $M = 22 - 17 + 2(1) = 7$.

The respective complexities are 4, 4, and 7.

The given equation is $(43)_x = (y3)_8$. To solve for the number of possible integer solutions for x and y, we first convert both sides to base 10.
$4 \cdot x^1 + 3 \cdot x^0 = y \cdot 8^1 + 3 \cdot 8^0$
$4x + 3 = 8y + 3$
$4x = 8y \implies x = 2y$

Next, we consider the constraints on the bases and digits:

1. For $(43)_x$, the base $x$ must be greater than any digit, so $x > 4$.
2. For $(y3)_8$, the digit $y$ must be less than the base 8. Since it's a leading digit, $y \neq 0$. So, $1 \le y \le 7$.

Combining $x=2y$ with the constraints:

• Since $1 \le y \le 7$, the possible values for $y$ are $\{1, 2, 3, 4, 5, 6, 7\}$.
• The corresponding values for $x$ are $\{2, 4, 6, 8, 10, 12, 14\}$.
• Applying the constraint $x > 4$, the valid values for $x$ are $\{6, 8, 10, 12, 14\}$.
  This gives 5 possible solutions.

The relation R on ordered pairs of positive integers is defined as $((p,q),(r,s)) \in R$ if and only if $p-s = q-r$. This can be rearranged to $p+r = q+s$.

Reflexivity: We check if $((p,q),(p,q)) \in R$ for any pair $(p,q)$. The condition becomes $p-q = q-p$, which simplifies to $2p = 2q$, or $p=q$. Since this does not hold for all pairs (e.g., $(1,2)$), the relation is not reflexive.

Symmetry: We check if $((p,q),(r,s)) \in R$ implies $((r,s),(p,q)) \in R$.

• Given: $p-s = q-r$.
• To check: $r-q = s-p$.
  Multiplying the given equation by -1 gives $-(p-s) = -(q-r)$, which is $s-p = r-q$. This is the condition we need to check. Therefore, the relation is symmetric.

The relation is not reflexive but is symmetric.

The question asks for the conditional probability $Pr[Y=0|X_{3}=0]$. Given the condition $X_3=0$, the expression for Y simplifies to $Y = X_1 X_2 \oplus 0$. For $Y$ to be 0, the term $X_1 X_2$ must also be 0. This occurs when at least one of $X_1$ or $X_2$ is 0. The possible pairs for $(X_1, X_2)$ that satisfy this are (0,0), (0,1), and (1,0). Since $X_1$ and $X_2$ are independent and $Pr[X_i=0]=Pr[X_i=1]=0.5$, each pair has a probability of $0.5 \times 0.5 = 0.25$. The total probability is the sum for these three cases: $3 \times 0.25 = 0.75$.

A prime implicant is a product term that cannot be further simplified by combining with other terms in a Karnaugh map. For the function $f(w,x,y,z)= \Sigma (0,2,4,5,6,10)$, we can identify the prime implicants by grouping the 1s.

1. A group of four 1s for minterms (0, 2, 4, 6), which corresponds to the term $w'z'$.
2. A group of two 1s for minterms (4, 5), which corresponds to the term $w'xy'$.
3. A group of two 1s for minterms (2, 10), which corresponds to the term $x'yz'$.
   These three groups cover all the 1s and cannot be expanded further. Thus, there are 3 prime implicants.