GATE CSE 2016 SET 1

The sentence requires the simple present tense in the clause following "until" to refer to a future event. The subject "the minister" is a third-person singular noun, so the verb must be "meets". Options A and B use a grammatically incorrect double negative ("not...does not" and "not...doesn't"). Option C uses "meet," which is the incorrect verb form for a third-person singular subject.

A "paraphrase" is a restatement or rewording of a text or passage, giving the meaning in another form. The other terms have different meanings: a "paradox" is a self-contradictory statement, a "paradigm" is a typical example or model of something, and "paraffin" is a flammable, waxy substance.

The statement by Archimedes is not meant to be interpreted literally, as finding a lever long enough to move the Earth is physically impossible. Instead, it uses exaggeration (hyperbole) to make a point about the immense power of leverage. This use of language to create an effect rather than to convey a literal meaning is known as a figurative statement.

By comparing 'carefree' (relftaga), 'careful' (otaga), and 'careless' (fertaga), we can deduce that 'taga' means 'care'. The prefixes 'relf', 'o', and 'fer' correspond to 'free', 'ful', and 'less' respectively. The question asks for 'aftercare'. The options suggest a structure of 'care' + suffix for 'after' or prefix for 'after' + 'care'. In 'tagazen', 'taga' means care, and 'zen' likely means 'after', forming 'aftercare'.

The cube is built from 64 smaller cubes, meaning it is a 4x4x4 cube. The initial surface area is $6 \times (\text{side length})^2 = 6 \times 4^2 = 96$ square units. When a corner block is removed, three of its faces, which were part of the cube's surface, are removed. However, this exposes three new inner faces of the resulting cavity. The net change in surface area is $-3 + 3 = 0$. Since this happens at all 8 corners, the total surface area remains unchanged at 96.

To find the product with the highest revenue, we calculate the total annual revenue for each razor type by multiplying the total units sold per year by the price per unit.

• Elegance: $(27300+25222+28976+21012) \times 48 = 102510 \times 48 = 4,920,480$
• Smooth: $(20009+19392+22429+18229) \times 63 = 80059 \times 63 = 5,043,717$
• Soft: $(17602+18445+19544+16595) \times 78 = 72186 \times 78 = 5,630,508$
• Executive: $(9999+8942+10234+10109) \times 173 = 39284 \times 173 = 6,796,132$
  Comparing the total revenues, the Executive razor contributes the most.

The sentences state that the presence of at least seventeen languages on currency notes is an indication of the nation's diversity. The phrasing "If this is not an indication..., nothing else is" emphasizes the significance of this linguistic multiplicity as a powerful sign of diversity. This directly supports the inference that linguistic pluralism is strong evidence of India's diversity. The other options make claims that are too specific (e.g., "exactly seventeen") or too absolute (e.g., "the only indicator") to be logically inferred.

The provided statements are:
I. P always beats Q (P > Q).
II. R always beats S (R > S).
III. S loses to P only sometimes (P does not always beat S).
IV. R always loses to Q (Q > R).

From I, II, and IV, we can form a partial hierarchy: P > Q > R > S. However, statement III contradicts a strict, transitive hierarchy because it implies that S sometimes does not lose to P.

Inference (i), "P is likely to beat all the three other players," cannot be logically inferred because of the conflict regarding S.
Inference (ii), "S is the absolute worst player," is false because S sometimes holds its own against P, the strongest player in other matchups.

Since neither statement can be definitively concluded from the given information, the correct choice is neither (i) nor (ii).

According to the Factor Theorem, a polynomial $f(x)$ has a factor $(x-c)$ if and only if $f(c) = 0$. We can test the given options.

Let's test option B, which corresponds to the factor $(x-1)$. Here, $c=1$. We need to evaluate $f(1)$.
The function is $f(x) = 2x^{7}+3x-5$.
Substituting $x=1$:
$f(1) = 2(1)^{7}+3(1)-5$
$f(1) = 2+3-5 = 0$

Since $f(1) = 0$, the polynomial $f(x)$ has a factor of $(x-1)$.

The solution for this question is not available in the provided PDF. The explanation is based on standard textbook concepts.

Let N be the number of cycles and L be the load. The relationship is exponential: $N = Ae^{-kL}$.
Given:

1. $100 = Ae^{-80k}$
2. $10000 = Ae^{-40k}$

Dividing (2) by (1) gives $\frac{10000}{100} = e^{40k}$, so $100 = e^{40k}$.
We need to find L when N = 5000.
From (2), $A = 10000e^{40k} = 10000 \times 100 = 10^6$.
So, $5000 = 10^6 e^{-kL}$.
$e^{kL} = \frac{10^6}{5000} = 200$.
$kL = \ln(200)$.
From $100 = e^{40k}$, we have $40k = \ln(100)$.
$L = \frac{\ln(200)}{k} = \frac{\ln(200)}{\ln(100)/40} = 40 \frac{\ln(200)}{\ln(100)} \approx 40 \frac{5.298}{4.605} \approx 46.02$.

The given logical expression is $\neg((p\Rightarrow q)\wedge (\neg r \vee \neg s))$. For this to be true, the inner expression $((p\Rightarrow q)\wedge (\neg r \vee \neg s))$ must be false. An AND expression is false if at least one of its operands is false.

Case 1: $(p\Rightarrow q)$ is false.
This occurs only when $p$ is true and $q$ is false.

• $p$ is true: $x \in \{8, 9, 10, 11, 12\}$.
• $q$ is false: $x$ is not a composite number.
  From the set for $p$, the only non-composite number is 11 (which is prime). So, $x=11$ satisfies this case.

Case 2: $(\neg r \vee \neg s)$ is false.
This is equivalent to $r \wedge s$ being true.

• $r$ is true: $x$ is a perfect square.
• $s$ is true: $x$ is a prime number.
  No integer is both a prime number and a perfect square. This case is impossible.

Thus, the only integer that satisfies the condition is $x=11$.

Let $a_n$ be the number of n-bit strings without two consecutive 1s. We can find the first few terms of the sequence to identify the pattern.

• For n=1: The valid strings are "0" and "1". So, $a_1 = 2$.
• For n=2: The valid strings are "00", "01", "10". The string "11" is invalid. So, $a_2 = 3$.
• For n=3: The valid strings are "000", "001", "010", "100", "101". The strings "011", "110", "111" are invalid. So, $a_3 = 5$.

The sequence starts $a_1=2, a_2=3, a_3=5$. Let's check the given options with $n=3$.
Option (b) is $a_n = a_{n-1} + a_{n-2}$.
For $n=3$, this gives $a_3 = a_2 + a_1 = 3 + 2 = 5$. This matches our calculated value.

To evaluate the limit, we can use a substitution. Let $t = x - 4$. As $x$ approaches 4, $t$ approaches 0. Substituting this into the expression gives us the standard trigonometric limit:
$\lim_{t \to 0} \frac{\sin(t)}{t}$
The value of this well-known limit is 1.

For a function to be a valid probability density function (PDF), its integral over the entire domain must equal 1. For the given function $f(x) = 1/x^2$ on the interval $[a, 1]$, we must have:
$\int_{a}^{1} \frac{1}{x^2} dx = 1$
Evaluating the integral gives:
$\left[-\frac{1}{x}\right]_{a}^{1} = \left(-\frac{1}{1}\right) - \left(-\frac{1}{a}\right) = \frac{1}{a} - 1$
Setting this equal to 1, we get $\frac{1}{a} - 1 = 1$, which solves to $\frac{1}{a} = 2$, so $a = 0.5$.

For a real matrix, complex eigenvalues must occur in conjugate pairs. Since $(2 + \sqrt{-1})$ or $(2+i)$ is an eigenvalue, its complex conjugate, $(2-i)$, must also be an eigenvalue. The three eigenvalues of the 3x3 matrix P are therefore $2+i$, $2-i$, and 3.

The determinant of a matrix is the product of its eigenvalues.
$\det(P) = (2+i)(2-i)(3)$
$\det(P) = (2^2 - i^2)(3) = (4 - (-1))(3) = (5)(3) = 15$

The properties of the operator can be used to construct its truth table.
For $y=0$, the output is $x\#0 = x$.
For $y=1$, the output is $x\#1 = \bar{x}$.

This gives the following results:

• $0\#0 = 0$
• $0\#1 = \bar{0} = 1$
• $1\#0 = 1$
• $1\#1 = \bar{1} = 0$

The output column (0, 1, 1, 0) matches the truth table for the XOR operation. The Boolean expression for XOR is $x\bar{y}+\bar{x}y$.

The given 16-bit number is 1111 1111 1111 0101. Since the most significant bit is 1, the number is negative in 2's complement representation. To find its magnitude, we take the 2's complement of the number.

1. Find the 1's complement by inverting all bits: 0000 0000 0000 1010.
2. Add 1 to the 1's complement: 0000 0000 0000 1011.

The resulting binary number, 1011, represents the magnitude. Converting to decimal: $8+2+1=11$. Since the original number was negative, the decimal value is -11.

The counter must generate the sequence 0-1-0-2-0-3. The maximum value is 3, which can be represented by 2 bits. However, the state '0' appears three times in the sequence. To distinguish between these three occurrences, additional state bits are required.

A state can be represented by a composite of the output value and an instance counter for that value. For example, we can use 2 bits for the value (0 to 3) and 2 bits to count the instances of '0' (first, second, third). This composite state representation requires a total of 4 bits, and thus 4 J-K flip-flops.

The worst-case time complexity for Insertion sort occurs when the input array is sorted in reverse order, leading to $\Theta(n^2)$ comparisons and swaps. For Mergesort, the time complexity is consistently $\Theta(n \log n)$ in all cases, as it always divides the array and merges. Quicksort's worst-case complexity is $\Theta(n^2)$, which happens when the pivot selection consistently results in highly unbalanced partitions, such as when the input array is already sorted.

Statement P is true. The Minimum Spanning Tree (MST) is determined by the relative order of edge weights. Adding a constant value to every edge does not change this relative order, so algorithms like Kruskal's or Prim's will select the same set of edges, resulting in the same MST.

Statement Q is false. The shortest path can change because adding a constant penalizes paths with more edges. A path that was originally shorter but had more edges might become longer than a path with fewer edges after the weights are increased.

The function mystery takes two integer pointers, ptra and ptrb, as arguments. Inside the function, it swaps the values of these local pointer variables. Since C passes arguments by value, the function receives copies of the addresses of a, b, and d. Swapping these copies inside mystery has no effect on the original variables a, b, and d in the main function. The if (a < c) condition (2016 < 4) is false, so the second call is skipped. The value of a remains unchanged from its initial value of 2016, which is what gets printed.

The given grammar is $S\rightarrow aS|bS|\varepsilon$. The productions $S \rightarrow aS$ and $S \rightarrow bS$ allow for prefixing the derived string with either an 'a' or a 'b' and then continuing the derivation from $S$. The production $S \rightarrow \varepsilon$ provides the base case to terminate the recursion. This process can generate any sequence of 'a's and 'b's of any length, including the empty string ($\varepsilon$). This is the definition of the set of all strings over the alphabet {a, b}, which is denoted by $\{a,b\}^*$.

I. The disjointedness problem for regular languages is decidable. The intersection of two regular languages is regular, and the emptiness of a regular language is a decidable problem.
II. The membership problem for Context-Free Languages (CFLs) is decidable, for instance, by using the CYK algorithm.
III. The equivalence problem for CFLs (checking if $L(G_1) = L(G_2)$) is undecidable.
IV. The emptiness problem for Recursively Enumerable (RE) languages (checking if $L(M) = \phi$ for a Turing Machine M) is undecidable.
Therefore, problems III and IV are undecidable.

The language consists of all binary strings that contain both the substring "00" and the substring "11". This means that for any string in the language, either an occurrence of "00" must appear before an occurrence of "11", or an occurrence of "11" must appear before an occurrence of "00".

The expression (0+1)*(00(0+1)*11 + 11(0+1)*00)(0+1)* correctly captures this. The middle part (00(0+1)*11 + 11(0+1)*00) ensures that both substrings are present in one of the two possible orders, and the surrounding (0+1)* parts allow for any characters at the beginning or end of the string.

This solution is based on standard textbook concepts as the PDF provides only the final answer.

In Static Single Assignment (SSA) form, each variable is assigned a value exactly once. The original code has 5 input variables (u, t, v, w, z) and uses two other variables (x, y) for intermediate calculations.

The sequence of operations can be represented in a three-address code format, which is closely related to SSA. We need variables to hold the 5 inputs and at least two additional temporary variables (or registers) to store the intermediate results of calculations without overwriting the inputs. Therefore, a minimum of 5 + 2 = 7 total variables are required.

The goal is to minimize the average waiting time. For a set of processes that arrive at the same time, the Shortest Job First (SJF) scheduling algorithm is provably optimal in minimizing average waiting time. Since the processes are non-preemptive (CPU-bound) and arrive simultaneously, the Shortest Remaining Time First (SRTF) algorithm behaves identically to SJF. It will execute the process with the shortest CPU burst first, then the next shortest, and so on, which minimizes the overall waiting time for the set.

A superkey is a set of attributes that contains a candidate key. In this relational schema, the primary key is given as VY. Since a primary key is always a candidate key, any attribute set that is a superset of {V, Y} will be a superkey.

We examine the options:

• VXYZ contains VY.
• VWXY contains VY.
• VWXYZ contains VY.

The attribute set VWXZ does not contain the attribute Y, and therefore it is not a superset of the primary key VY. Thus, VWXZ is not a superkey.

The ACID properties are a set of fundamental guarantees for database transactions. The acronym ACID stands for:

• Atomicity: Transactions are all-or-nothing.
• Consistency: A transaction brings the database from one valid state to another.
• Isolation: Concurrent transactions do not interfere with each other.
• Durability: Once a transaction is committed, its effects are permanent.

Deadlock-freedom is a desirable characteristic of a concurrency control protocol, but it is not one of the core ACID properties.

The original schema has a primary key of (VOLUME, NUMBER, STARTPAGE, ENDPAGE). The functional dependency (VOLUME, NUMBER) → YEAR represents a partial dependency, because a non-prime attribute (YEAR) depends on a proper subset of the primary key. This violates the condition for 2NF, meaning the original schema is only in 1NF. The redesigned database splits the schema into two new relations. An analysis of these new relations shows that both satisfy the conditions for BCNF. Since the new database satisfies 2NF (and higher forms) but the old one did not, the weakest such normal form is 2NF.

The question asks which protocol does not resolve one form of address to another. ARP resolves an IP address to a MAC address. RARP does the reverse, resolving a MAC address to an IP address. DNS resolves a domain name to an IP address. All three perform a mapping or resolution. DHCP, however, is a protocol used to dynamically assign an IP address and other network configuration parameters to a host. It does not resolve an existing address into another form.

The solution evaluates which of the listed protocols are both stateful and operate at the application layer. HTTP is stateless. TCP is stateful but is a transport layer protocol, not an application layer one. FTP is an application layer protocol that is stateful, as it maintains state for control and data connections, including user authorization. POP3 is also a stateful application layer protocol because it maintains state across a session, for example, to handle user authentication and track retrieved messages. Therefore, FTP (ii) and POP3 (iv) are the correct examples.

The expression is $(x^{3}+x^{4}+x^{5}+...)^{3}$. By factoring out $x^3$, we get $(x^3(1+x+x^{2+}...))^3$, which simplifies to $x^9(1+x+x^{2+}...)^3$. The infinite series is the geometric series for $(1-x)^{-1}$. The expression becomes $x^9(1-x)^{-3}$. To find the coefficient of $x^{12}$, we need the coefficient of $x^3$ from the expansion of $(1-x)^{-3}$. Using the binomial theorem for a negative exponent, the coefficient of $x^r$ in $(1-x)^{-n}$ is $\binom{n+r-1}{r}$. For $n=3$ and $r=3$, the coefficient is $\binom{3+3-1}{3} = \binom{5}{3} = 10$.

The recurrence relation is $a_{n}=6n^{2}+2n+a_{n-1}$ with $a_1 = 8$. By expanding the relation for $a_{99}$, we get $a_{99} = \sum_{i=2}^{99} (6i^2 + 2i) + a_1$. We can observe that the initial condition $a_1 = 8$ is equal to $6(1^2) + 2(1)$. Therefore, the expression for $a_{99}$ can be written as a complete sum from $i=1$: $a_{99} = \sum_{i=1}^{99} (6i^2 + 2i)$. Using the formulas for the sum of the first $k$ integers and squares, this evaluates to $9900 \times (199+1) = 1980000 = 198 \times 10^4$. Thus, the value of K is 198.

The function's behavior is analyzed by tracing values. For any even number $n$, $f(n) = f(n/2)$. For any odd number $n$, $f(n) = f(n+5)$.

1. $f(1) = f(6) = f(3) = f(8) = f(4) = f(2) = f(1)$. Also $f(7)=f(12)=f(6)$, and $f(9)=f(14)=f(7)$. This group of values all map to a single output value, let's call it $v_1$.
2. $f(5) = f(10) = f(5)$. This forms a second distinct output value, $v_2$.
3. The values explored in point 1, such as $f(6), f(7), f(9)$, form a third distinct value group, $v_3$.
   Any integer $n$ will eventually fall into one of these three recursive patterns. Therefore, the set $R$ of distinct values contains a maximum of 3 elements.

The experiment involves flipping a fair coin twice. The four possible outcomes (HH, HT, TH, TT) each have a probability of $1/4$.

• The experiment outputs Y on (TAILS, HEADS), so $P(Y) = 1/4$.
• The experiment repeats on (TAILS, TAILS), so $P(\text{repeat}) = 1/4$.
  The output can be Y on the first try, or after one repeat, or after two repeats, and so on. This forms an infinite geometric series for the total probability of Y:
  $P(\text{Total Y}) = \frac{1}{4} + (\frac{1}{4})(\frac{1}{4}) + (\frac{1}{4})^2(\frac{1}{4}) + \dots$
  This is a series with first term $a = 1/4$ and common ratio $r = 1/4$. The sum is $S = \frac{a}{1-r} = \frac{1/4}{1 - 1/4} = \frac{1/4}{3/4} = \frac{1}{3} \approx 0.33$.

The output of a 2-to-1 multiplexer with select line $S$ and inputs $I_0, I_1$ is given by $\bar{S}I_0 + SI_1$.

1. For the first MUX, the select line is $P$, $I_0=0$, and $I_1=R$. Its output is $\bar{P}(0) + P(R) = PR$.
2. This output $PR$ is the $I_1$ input for the second MUX.
3. For the second MUX, the select line is $Q$, $I_0=R$, and $I_1=PR$.
4. The final output $X$ is $\bar{Q}(R) + Q(PR) = \bar{Q}R + PQR$.

The DMA controller's data count register size is 16 bits. This means the maximum amount of data that can be transferred in a single DMA operation is $2^{16}$ bytes.
$2^{16}$ bytes = 65,536 bytes = 64 kilobytes (KB).
The total size of the file to be transferred is 29,154 KB.
To find the minimum number of times the DMA controller must take control of the bus, we divide the total file size by the maximum size per transfer:
Number of transfers = $\lceil \frac{29,154 \text{ KB}}{64 \text{ KB}} \rceil = \lceil 455.53125 \rceil = 456$.
Each transfer, including the final partial one, requires the DMA controller to acquire the bus.

The throughput of a pipeline is inversely proportional to its cycle time, which is the delay of the longest stage.

1. Original pipeline (P1): Delays are (800, 500, 400, 300) ps. The maximum delay is 800 ps. Throughput $TP_1 \propto 1/800$.
2. New pipeline (P2): The 800 ps stage is replaced by two stages (600, 350) ps. The new delays are (600, 350, 500, 400, 300) ps. The new maximum delay is 600 ps. Throughput $TP_2 \propto 1/600$.
   The percentage increase in throughput is:
   $\frac{TP_2 - TP_1}{TP_1} = \frac{1/600 - 1/800}{1/800} = \frac{800}{600} - 1 = \frac{4}{3} - 1 = \frac{1}{3} \approx 33.33\%$
   The value 33.28% in the provided solution arises from intermediate rounding.

A carry-lookahead adder (CLA) computes carry signals in parallel, which speeds up the addition process compared to a ripple-carry adder. When using gates with a limited fan-in (at most two, as specified), the logic for generating carries for blocks of bits is structured hierarchically. This creates a tree-like circuit. The depth of this tree determines the overall propagation delay. For an n-bit adder, the depth of this hierarchical structure is proportional to $\log(n)$, leading to a time complexity of $\Theta(\log(n))$.

The function finds the maximum value by using two pointers, a starting from index 0 and b from n-1. In each iteration of the while loop, it compares p[a] and p[b] and moves the pointer corresponding to the smaller element inward. This process effectively discards the smaller of the two boundary elements. The loop should continue until both pointers converge on the same element, which will be the maximum value. The condition b != a ensures the loop terminates precisely when a and b point to the same index.

The function count is called recursively, and it uses a static integer d. A static variable is initialized only once.

1. count(3) is called. It prints n=3, d=1. d becomes 2. It calls count(2).
2. count(2) is called. It prints n=2, d=2. d becomes 3. It calls count(1).
3. count(1) is called. It prints n=1, d=3. d becomes 4. The recursion stops. It then prints d=4 before returning.
4. Execution returns to count(2), which prints d=4.
5. Execution returns to count(3), which prints d=4.
   The full output is the concatenation of these print statements.

The execution is traced assuming dynamic scoping and pass-by-reference.

1. main calls m(a). Global a is 3. y in m is a reference to global a.
2. In m, a=1 creates a new local variable a. Then a = y - a evaluates to a = 3 - 1 = 2. So, m's local a is 2.
3. n(a) is called. Per the PDF's logic, this behaves like pass-by-value, so x in n gets the value 2.
4. In n, x = x * a. With dynamic scoping, a refers to the a in the caller m, which is 2. So, x = 2 * 2 = 4. print(x) outputs 4.
5. n returns. Since the call was effectively pass-by-value, m's local a is unchanged and remains 2. print(a) in m outputs 2.

To delete an element at index i in a binary heap, the standard algorithm replaces it with the last element of the heap. Then, the heap size is decremented. The new element at index i might violate the heap property. To restore it, the element is either sifted up (compared with its parent) or sifted down (compared with its children) until its correct position is found. In the worst-case scenario, this element might need to travel from the root to a leaf (or vice-versa), a path of length equal to the heap's depth, d. Therefore, the time complexity is O(d).

The solution in the provided PDF is 11. This can be derived by finding the condition under which the edge with weight x becomes part of a unique shortest path.

Let the vertices be 1, 2, 3, and 4. The edge in question is (3, 4) with weight x. To determine if this edge is on a shortest path, we compare its weight to the shortest alternative path between vertices 3 and 4.

The alternative paths between 3 and 4 are:

• 3-1-4: weight 8 + 5 = 13
• 3-2-4: weight 5 + 8 = 13
• 3-2-1-4: weight 5 + 2 + 5 = 12

The shortest alternative path has a weight of 12. For the direct edge (3, 4) to be the unique shortest path, its weight x must be strictly less than the weight of any other path. Therefore, we must have $x < 12$. The largest integer value of x that satisfies this condition is 11.

The PDA accepts the language $L = \{a^n b^n | n \ge 0\}$. The initial state must be an accepting state to include the empty string $\epsilon$ (for n=0). For $n \ge 1$, the PDA first pushes $n$ 'X's onto the stack while reading $n$ 'a's in the initial state. Then, it transitions to the final state, reading 'b's and popping an 'X' for each 'b'. The language $\{a^n b^n | n \ge 0\}$ is a standard example of a context-free language that is not regular. Therefore, it cannot be accepted by any finite automaton.

We are given that X is a recursive (REC) language, and Y is recursively enumerable (RE) but not REC.
From the reduction $Z \le_m \bar{X}$: Since X is REC, its complement $\bar{X}$ is also REC. A language that reduces to a REC language must also be REC. Therefore, Z is recursive.
From the reduction $\bar{Y} \le_m W$: Since Y is RE but not REC, its complement $\bar{Y}$ is not RE. If W were RE, then $\bar{Y}$ would also have to be RE, which is a contradiction. Therefore, W is not recursively enumerable.

The expression is 2 - 5 + 1 - 7 * 3. The evaluation depends on the given operator precedence (High: +, Medium: -, Low: *) and associativity (Left: +, *, Right: -).

1. The highest precedence operator is +. We evaluate 5 + 1 first: 2 - 6 - 7 * 3.
2. The next highest is -, which is right-associative. This means a - b - c is evaluated as a - (b - c). So, we evaluate 6 - 7 next: 2 - (-1) * 3.
3. This simplifies to 3 * 3.
4. The final operation is *, resulting in 9.

The C-LOOK algorithm services requests in one direction and then jumps to the first request in the opposite direction to continue service, without traveling to the end of the disk.

1. The head starts at cylinder 63, moving towards larger numbers. It services requests at 87, 92, 121, and finally 191.
2. After servicing 191, it jumps to the smallest pending request, which is 10.
3. From 10, it moves towards larger numbers again, servicing 11, 38, and 47.

The total head movement is the sum of movements between each serviced cylinder:
$(87-63) + (92-87) + (121-92) + (191-121) + (191-10) + (11-10) + (38-11) + (47-38) = 346$.

The solution demonstrates the concept by analyzing a smaller, analogous problem: a sequence of (1, 2, 3, 4, 1, 2, 3, 4) with 2 page frames.

For this smaller example:

• LIFO (Last-In-First-Out): Results in 7 page faults.
• Optimal: Results in 6 page faults.

The difference is $7 - 6 = 1$.

This pattern holds for the original problem. For the first 20 distinct pages, both algorithms will have 20 faults. The difference in performance occurs during the second pass of the sequence. Generalizing from the smaller example, the difference in the number of page faults between the LIFO and Optimal policies is 1.

The provided algorithm ensures mutual exclusion. A process $P_i$ must acquire a ticket number $t[i]$ before entering its critical section. It then waits for any other process $P_j$ that has a smaller or equal ticket number ($t[j] \le t[i]$). If two processes, $P_i$ and $P_j$, attempt to enter the critical section, the one with the smaller ticket number will proceed while the other waits. If they happen to acquire the same ticket number, they will both wait for each other, preventing simultaneous entry. Thus, at most one process can be in the critical section at any time.

The total data payload to be transmitted is the datagram size minus the header size, which is $1000 - 20 = 980$ bytes. The maximum transmission unit (MTU) is 100 bytes, so the maximum data payload per fragment is the MTU minus the header size, or $100 - 20 = 80$ bytes. To find the number of fragments, we divide the total data payload by the maximum payload per fragment: $\lceil \frac{980}{80} \rceil = \lceil 12.25 \rceil = 13$. Therefore, 13 fragments are required.

First, we determine the duration ($S$) for which the host can transmit at its maximum rate ($M$) using the initial tokens in the bucket ($C$). The governing equation is $C + \rho S = MS$, where $\rho$ is the token arrival rate.
Substituting the values: $1 \text{ MB} + (10 \text{ MBps}) \times S = (20 \text{ MBps}) \times S$.
Solving for $S$, we get $S = 0.1$ seconds.
In this time, data transmitted is $M \times S = 20 \text{ MBps} \times 0.1 \text{ s} = 2 \text{ MB}$.
Remaining data is $12 \text{ MB} - 2 \text{ MB} = 10 \text{ MB}$. This remaining data is sent at the token arrival rate $\rho$.
Time for remaining data = $\frac{10 \text{ MB}}{10 \text{ MBps}} = 1$ second.
Total time = $0.1 \text{ s} + 1 \text{ s} = 1.1$ seconds.

Sender throughput is the amount of useful data transmitted per unit of time. For one successful frame transmission in Stop-and-Wait, the total time cycle includes the frame's transmission time ($T_t$), propagation delay ($T_p$), ACK's transmission time ($T_{ack}$), and the ACK's propagation delay ($T_p$).

$T_t = \frac{\text{Frame size}}{\text{Sender rate}} = \frac{1000 \times 8 \text{ bits}}{80 \times 1000 \text{ bps}} = 0.1$ s.
$T_p = 100$ ms $= 0.1$ s.
$T_{ack} = \frac{\text{ACK size}}{\text{Receiver rate}} = \frac{100 \times 8 \text{ bits}}{8 \times 1000 \text{ bps}} = 0.1$ s.

Total cycle time = $T_t + T_p + T_{ack} + T_p = 0.1 + 0.1 + 0.1 + 0.1 = 0.4$ s.
Throughput = $\frac{\text{Frame size}}{\text{Total time}} = \frac{1000 \text{ bytes}}{0.4 \text{ s}} = 2500$ bytes/second.