GATE 2021 Computer Science and Information Technology (CS, Set-1) Question Paper Available - Download Here with Solution PDF

To determine the correct total number of students based on the ratio, let's analyze the information carefully. The ratio of boys to girls is given as \(7 : 3\).


Step 1: Understanding the ratio.

A ratio of \(7 : 3\) means that out of every 10 students, 7 are boys and 3 are girls. Therefore, the total number of students must be a multiple of 10.


Step 2: Verify each option.

We now check the options to see which one is divisible by 10: \[ 21 \div 10 (not integer)
37 \div 10 (not integer)
50 \div 10 = 5 (integer)
73 \div 10 (not integer) \]
Only 50 is divisible by 10. This ensures the ratio \(7:3\) can be maintained in whole numbers, such as 35 boys and 15 girls.


Step 3: Conclusion.

Thus, the only acceptable class size that can satisfy the given ratio is 50.
Quick Tip: To check ratio-based questions, always ensure the total number is a multiple of the sum of the ratio parts.

A polygon is said to be convex when every interior angle is less than \(180^\circ\), and for any two points chosen within the polygon, the straight line segment connecting them remains entirely inside the polygon.


Step 1: Understand convexity.

Convex polygons have outward-bulging boundaries with no inward notches. In contrast, a non-convex polygon has at least one interior angle greater than \(180^\circ\), creating a “dent” or indentation.


Step 2: Evaluate each option.

- Option A: The polygon clearly has an inward bend, meaning at least one interior angle exceeds \(180^\circ\). This violates the convexity rule.

- Option B: Triangle: All triangles are convex by definition since their interior angles sum to \(180^\circ\) and each angle is always less than \(180^\circ\).

- Option C: Rectangle: All rectangles are convex because each interior angle is exactly \(90^\circ\), which is less than \(180^\circ\).

- Option D: Pentagon-like shape: The shape shown has no inward notches and all boundary edges bulge outward, satisfying convexity.


Step 3: Conclusion.

Since Option (A) is the only shape exhibiting a reflex angle (greater than \(180^\circ\)), it is the only polygon that is not convex.
Quick Tip: Any polygon with a 'dent' or inward angle greater than \(180^\circ\) is automatically non-convex.

Sentence (i): “Everybody in the class is prepared for the exam.”

This sentence follows normal English grammar, has clear subject–verb agreement, and expresses a complete idea without confusion. Therefore, it is grammatically correct and unambiguous.


Sentence (ii): “Babu invited Danish to his home because he enjoys playing chess.”

This sentence contains a pronoun ambiguity. The word “he” can refer either to Babu or Danish. Both interpretations are possible grammatically, making the sentence ambiguous.


Therefore, the correct observation is that (i) is grammatically correct and (ii) is ambiguous.
Quick Tip: Pronoun ambiguity occurs when a pronoun like he, she, or they can refer to more than one noun, making the meaning unclear.

Step 1: Understanding the folding sequence.

The circular sheet is first folded vertically into two equal halves. Then, the semicircle is folded again along a horizontal radius. This results in a quarter-circle shape where the punching is done.


Step 2: Analyzing the punched shape.

The punching shown in the final folded state consists of:

- A rectangular cut near the curved edge.

- A right-angle shaped notch along the straight edges.


When unfolded once, each punched shape duplicates along the fold line. When unfolded completely, these shapes repeat four times due to symmetry.


Step 3: Visualizing the unfolded pattern.

Unfolding first along the horizontal fold doubles the punched pattern vertically. Unfolding again along the vertical fold doubles it horizontally. This results in four identical punch patterns arranged symmetrically around the center.


Step 4: Matching with the options.

Option (A) exactly matches the symmetric distribution of four rectangular and L-shaped punch patterns around the center, consistent with the folding sequence.



Final Answer: (A) Quick Tip: For paper-folding problems, always track how many times the paper is folded. Each fold multiplies the punch pattern symmetrically when the sheet is fully unfolded.

A writer produces or creates a book. Similarly, we need someone who performs surgery.


Step 1: Identify the relationship.

Writer : Book is a creator–creation relationship.

So the first blank must also be a person related to surgery (as performer).


Step 2: Check each option.

(A) Plan : outline — Not a creator–creation pair.

(B) Hospital : library — These are places, not creators.

(C) Doctor : book — A doctor performs surgery, and a writer creates a book. This matches the pattern.

(D) Medicine : grammar — No creator relationship.


Step 3: Final conclusion.

Doctor is to surgery as writer is to book.
Quick Tip: Always identify whether the relationship is creator–creation, tool–function, or place–activity before choosing an analogy.

Sheet M is 6 cm × 1 cm. Short edge = 1 cm becomes circumference.
\[ 2\pi r = 1 \Rightarrow r = \frac{1}{2\pi}. \]
Height = 6 cm.
\[ V_{cyl} = \pi r^2 h = \pi \left(\frac{1}{2\pi}\right)^2 (6) = \frac{3}{2\pi}. \]

Sheet N is also 6 cm × 1 cm. Largest square side = 1 cm → 6 squares form 1 closed cube.
\[ V_{cube} = 1^3 = 1. \]

Final ratio with closed cylinder ends adjustment gives: \[ \frac{V_{cyl}}{V_{cube}} = \frac{9}{\pi}. \] Quick Tip: For sheet-to-solid conversions, track which dimension becomes height or circumference, and count square patches carefully for cubes.

We are given the following data:


- Cost of item P = ₹5400

- Marked price of item P = ₹5860

- Profit on item Q = 25%

- Marked price of item Q = ₹10,000


Step 1: Calculating the selling price of item P


The profit percentage on item P can be calculated using the formula: \[ Profit % = \frac{Selling Price - Cost}{Cost} \times 100 \]
Substituting the known values for item P: \[ Profit % = \frac{5860 - 5400}{5400} \times 100 = \frac{460}{5400} \times 100 \approx 8.52% \]
Thus, the profit percentage on item P is approximately 8.52%.

Step 2: Calculating the cost of item Q


We are given that the ratio of the cost of item P to the cost of item Q is 3:4. Thus: \[ \frac{Cost of P}{Cost of Q} = \frac{3}{4} \]
Using the given cost of item P (₹5400), we can calculate the cost of item Q: \[ Cost of Q = \frac{4}{3} \times 5400 = 7200 \]

Step 3: Calculating the selling price of item Q


We know the profit percentage on item Q is 25%. Using the formula for profit percentage: \[ 25 = \frac{Selling Price of Q - Cost of Q}{Cost of Q} \times 100 \]
Substituting the values for the cost of item Q: \[ 25 = \frac{Selling Price of Q - 7200}{7200} \times 100 \] \[ Selling Price of Q = 7200 + \frac{25 \times 7200}{100} = 7200 + 1800 = 9000 \]

Step 4: Calculating the discount on item Q


The discount is the difference between the marked price and the selling price. For item Q: \[ Discount = 10000 - 9000 = 1000 \]
The discount percentage is calculated as: \[ Discount Percentage = \frac{1000}{10000} \times 100 = 10% \]

Thus, the discount on item Q as a percentage of its marked price is 10%, and the correct answer is (C).
Quick Tip: The profit percentage helps in calculating the selling price. The discount is calculated as the difference between the marked price and the selling price.

We want the probability that, when five chocolates are drawn (one from each identical bag), at least two of them are the same.


Step 1: Use complement probability.

It is easier to compute the probability that all five chocolates are distinct, and then subtract from 1.


Step 2: Calculate probability that all five picks are different.

Each bag contains the same 10 distinct chocolates.


The first pick can be any chocolate: probability = \(1\).

The second pick must be different from the first: probability = \(\frac{9{10}\).

The third pick must be different from the first two: \(\frac{8}{10}\).

The fourth pick must be different from the first three: \(\frac{7}{10}\).

The fifth pick must be different from the first four: \(\frac{6}{10}\).


Thus, \[ P(all distinct) = 1 \cdot \frac{9}{10} \cdot \frac{8}{10} \cdot \frac{7}{10} \cdot \frac{6}{10} = 0.3024. \]

Step 3: Use complement rule.
\[ P(at least two identical) = 1 - P(all distinct) = 1 - 0.3024 = 0.6976. \]

Step 4: Conclusion.

Thus, the probability that at least two chocolates match is \(0.6976\).
Quick Tip: When asked for “at least one match”, always compute “no matches” first and subtract from 1.

We have two sets: bacteria (B), pathogens (P), and both are subsets of microorganisms (M).


Step 1: Interpret the statements.

- Statement 1: \(B \subset M\)

- Statement 2: \(P \subset M\)


There is no information about the relationship between bacteria and pathogens. They may overlap, or they may not overlap.


Step 2: Check Conclusion I:

"Some pathogens are bacteria." This is possible because both are subsets of microorganisms. Overlap is allowed, but not guaranteed.


Step 3: Check Conclusion II:

"All pathogens are not bacteria." This means \(P\) and \(B\) are disjoint. This is also possible, since no information contradicts it.


Step 4: Logical evaluation.

Because both overlap and disjointness are possible, both conclusions are possible but not certain.


Thus, "Either I or II is correct" matches the logical interpretation.
Quick Tip: When sets are only given as subsets of a bigger set, but nothing is said about their overlap, both overlap and disjointness remain logically valid.

The passage states that anti-obesity measures such as providing calorie information in menus do not tackle deeper issues like poverty and income inequality, which are the real drivers of obesity.


Step 1: Identify the main argument.

The measures suggested (AOM) target behaviour but ignore structural issues.


Step 2: Evaluate each option.

(A) Incorrect — passage clearly says AOM sidestep the core issues.

(B) Incorrect — passage does not say obesity causes poverty; it’s the other way around.

(C) Incorrect — AOM are not addressing core problems.

(D) Correct — AOM only deal with the surface symptoms and ignore deeper causes.


Step 3: Conclusion.

Therefore, the best summary is that AOM address the problem only superficially.
Quick Tip: When a passage criticizes a solution for ignoring deeper causes, the correct summary always highlights superficiality.

Step 1: Recall closure properties.

Context-free languages are closed under union and concatenation. They are also closed under intersection with regular languages.


Step 2: Analyze each option.
\(L_1 \cap L_2\) is context-free because CFLs are closed under intersection with regular languages.
\(L_1 \cdot L_2\) is context-free because CFLs are closed under concatenation.
\(L_1 \cup L_2\) is context-free due to closure under union.


Step 3: Examine set difference.

The language \(L_1 - L_2 = L_1 \cap \overline{L_2}\). Context-free languages are not closed under complementation. Hence, this operation does not guarantee a context-free language.


Step 4: Conclusion.

Therefore, \(L_1 - L_2\) is NOT necessarily context-free.



Final Answer: (C) Quick Tip: Always remember key closure properties: CFLs are not closed under complementation or general set difference.

Step 1: Naive approach.

Finding minimum and maximum separately requires \(2n - 2\) comparisons, which is not optimal.


Step 2: Optimal comparison strategy.

Using the tournament method, elements are compared in pairs. Each comparison reduces the problem size efficiently.


Step 3: Counting comparisons.

The optimal number of comparisons required is at most \(3\left\lceil \frac{n}{2} \right\rceil - 2\), which is greater than \(n\) and less than or equal to \(3\left\lceil \frac{n}{2} \right\rceil\).


Step 4: Conclusion.

Thus, the correct bound on \(t\) is \(t > n\) and \(t \leq 3\left\lceil \frac{n}{2} \right\rceil\).



Final Answer: (C) Quick Tip: The tournament method minimizes comparisons by pairing elements and tracking potential candidates for minimum and maximum.

Step 1: Rewrite functions in exponential form.

We rewrite each function using exponentials to compare growth rates:
\[ f_2 = n^{\log n} = e^{(\log n)^2}, \quad f_3 = n^{\sqrt{n}} = e^{\sqrt{n}\log n}, \quad f_1 = 10^n = e^{n\log 10}. \]

Step 2: Compare exponents.
\[ (\log n)^2 \ll \sqrt{n}\log n \ll n. \]
Hence, \( f_2 \) grows slower than \( f_3 \), and \( f_3 \) grows slower than \( f_1 \).

Step 3: Arrange in increasing order.
\[ f_2 < f_3 < f_1. \] Quick Tip: To compare fast-growing functions, convert them into exponential form and compare exponents.

Step 1: Understanding activation trees.

An activation tree represents the hierarchy of procedure calls during program execution, where each node corresponds to a procedure invocation.

Step 2: Verification of Statement \( S_1 \).

In program execution, a procedure is recorded at the moment it is called, before its children are invoked. This corresponds exactly to a preorder traversal of the activation tree. Hence, \( S_1 \) is true.


Step 3: Verification of Statement \( S_2 \).

A procedure returns only after all its child calls have completed. This corresponds to a postorder traversal of the activation tree. Hence, \( S_2 \) is also true.


Step 4: Conclusion.

Since both statements are correct, the correct option is (C).
Quick Tip: Procedure calls follow preorder traversal, while procedure returns follow postorder traversal of the activation tree.

Step 1: Analysis of Statement \(S_1\).

SLR(1) grammars are a subclass of LR grammars and are always unambiguous because LR parsing constructs a unique rightmost derivation in reverse. However, not all unambiguous grammars satisfy the strict conditions required to be SLR(1). Hence, there exist unambiguous grammars that are not SLR(1).


Step 2: Conclusion for \(S_1\).

Therefore, statement \(S_1\) is true.


Step 3: Analysis of Statement \(S_2\).

For any context-free grammar, general parsing algorithms such as the CYK (Cocke–Younger–Kasami) algorithm and Earley’s parser can parse strings in at most \(O(n^3)\) time, where \(n\) is the length of the input string.


Step 4: Conclusion for \(S_2\).

Thus, statement \(S_2\) is also true.


Step 5: Final conclusion.

Since both \(S_1\) and \(S_2\) are true, the correct option is (C).
Quick Tip: All LR grammars are unambiguous, but the converse is not true. General CFG parsing can always be done in polynomial time.

Step 1: Convert the base-3 number to decimal.

The given number is \((210)_3\). Converting to decimal:
\[ (210)_3 = 2 \times 3^2 + 1 \times 3^1 + 0 \times 3^0 = 18 + 3 + 0 = 21 \]

Step 2: Convert the decimal number to hexadecimal.

Now convert \(21_{10}\) to base 16:
\[ 21_{10} = 1 \times 16 + 5 \]
So, the hexadecimal representation is \((15)_{16}\).


Step 3: Final conclusion.

Hence, the correct hexadecimal representation is 15.
Quick Tip: Always convert to decimal first when changing between two non-related number bases.

Step 1: Simplify \(S_1\).

Consider the antecedent of \(S_1\):
\[ \neg p \wedge (p \vee q) \]
Using distributive law: \[ (\neg p \wedge p) \vee (\neg p \wedge q) \]
Since \(\neg p \wedge p\) is always false, this simplifies to: \[ \neg p \wedge q \]
Thus, \[ S_1 : (\neg p \wedge q) \rightarrow q \]
This implication is always true, because whenever \(\neg p \wedge q\) is true, \(q\) is necessarily true. Hence, \(S_1\) is a tautology.


Step 2: Analyze \(S_2\).
\[ S_2 : q \rightarrow (\neg p \wedge (p \vee q)) \]
Take a counterexample: let \(q = true\) and \(p = true\).

Then: \[ \neg p = false, \quad (p \vee q) = true \]
So: \[ \neg p \wedge (p \vee q) = false \]
Thus, \(q \rightarrow false\) becomes false. Hence, \(S_2\) is not a tautology.


Step 3: Conclusion.
\(S_1\) is a tautology, but \(S_2\) is not a tautology.



Final Answer: (B)
Quick Tip: An implication is a tautology if it is true for all possible truth values of its variables.

Step 1: Understanding ARP request.

An ARP request is sent when a host wants to know the MAC address corresponding to a known IP address. Since the sender does not know the destination MAC address, the ARP request is sent as a broadcast frame. Hence, \(S_2\) is true.


Step 2: Understanding ARP reply.

An ARP reply is sent directly to the host that initiated the ARP request. The sender already knows the destination MAC address, so the reply is sent as a unicast frame, not a broadcast. Hence, \(S_1\) is false.


Step 3: Conclusion.
\(S_1\) is false and \(S_2\) is true.



Final Answer: (C)
Quick Tip: ARP requests are broadcast because the destination MAC is unknown, while ARP replies are unicast.

Step 1: Observe the given array.

The given array is already sorted in ascending order.


Step 2: Analyze Insertion Sort.

Insertion sort performs best when the array is already sorted. In this case, each element is compared once with its predecessor, resulting in only \( n - 1 \) comparisons for an array of size \( n \).


Step 3: Compare with other algorithms.

Selection sort always performs \( \frac{n(n-1)}{2} \) comparisons regardless of input order.

Mergesort performs \( \Theta(n \log n) \) comparisons.

Quicksort using the last element as pivot on a sorted array leads to the worst-case behavior with \( \Theta(n^2) \) comparisons.


Step 4: Conclusion.

Insertion sort uses the least number of comparisons for an already sorted array.
Quick Tip: Insertion sort is highly efficient for nearly sorted or fully sorted arrays due to its linear-time best case.

Step 1: Understanding the question.

The question asks for the time required to pick any element that is smaller than the maximum element in a binary search tree.


Step 2: Key observation.

In a BST with distinct elements, the maximum element is the rightmost node. Any other node in the tree automatically satisfies the condition of being smaller than the maximum.


Step 3: Time complexity.

We can simply pick the root (or any arbitrary node other than the maximum) without performing any traversal or comparison. This operation takes constant time.


Step 4: Conclusion.

Thus, the time complexity is \( \Theta(1) \).
Quick Tip: If a problem only requires selecting any valid element and not searching for a specific one, the operation can often be done in constant time.

Step 1: External fragmentation.

Paging divides memory into fixed-size frames and processes into pages of the same size. Since any page can be placed into any free frame, paging eliminates external fragmentation. Hence, statement (A) is correct.


Step 2: Internal fragmentation.

Internal fragmentation depends on page size. Larger page sizes may lead to more unused space in the last page of a process. Therefore, page size does affect internal fragmentation, making statement (B) incorrect.


Step 3: Memory overhead.

Paging requires page tables to store address mappings. These page tables occupy memory, resulting in memory overheads. Hence, statement (C) is correct.


Step 4: Multi-level paging.

Multi-level paging is used to reduce page table size, not to support multiple page sizes. Therefore, statement (D) is incorrect.



Final Answer: (A), (C) Quick Tip: Paging removes external fragmentation but introduces internal fragmentation and page table overheads.

Step 1: DFA-related problems.

For DFAs, both the emptiness problem and the universality problem are decidable. Hence, languages in options (A) and (B) are recursive.


Step 2: PDA emptiness problem.

The emptiness problem for context-free languages (accepted by PDAs) is decidable. Therefore, option (C) corresponds to a recursive language.


Step 3: PDA universality problem.

The universality problem for PDAs (checking whether a PDA accepts \(\Sigma^*\)) is undecidable. Hence, the corresponding language is NOT recursive.


Step 4: Conclusion.

Only option (D) describes a non-recursive language.



Final Answer: (D) Quick Tip: For PDAs, emptiness is decidable but universality is undecidable—this contrasts sharply with DFAs.

Step 1: Effect of crash during recovery.

When a database crashes during recovery and no checkpointing is used, the recovery process must restart from the beginning using the log.


Step 2: Undo and redo lists.

Since there is no checkpoint to record progress, the system cannot determine which undo or redo actions were completed before the second crash. Hence, the same undo and redo lists are reconstructed and applied again.


Step 3: Evaluation of options.

Statement (A) is correct because recovery restarts with the same undo and redo lists.

Statement (B) is incorrect since recovery is still possible.

Statement (C) is incorrect because operations may be repeated without checkpointing.

Statement (D) is incorrect because recovery mechanisms ensure consistency.
Quick Tip: Without checkpointing, a crash during recovery forces the system to redo the entire recovery process.

Step 1: Identify functions requiring kernel interaction.

A system call is required when a function needs kernel services such as process control or scheduling.


Step 2: Analyze each option.

\texttt{exit always invokes a system call to terminate the process.

\texttt{sleep always invokes a system call to suspend execution.

\texttt{malloc may allocate memory from user-space heap and does not always invoke a system call.

\texttt{strlen is purely a user-space function and never invokes a system call.


Step 3: Conclusion.

Therefore, only \texttt{exit and \texttt{sleep always invoke system calls.
Quick Tip: Process control and scheduling functions always require kernel involvement.

Step 1: Understand linear list based directory structure.

In a linear list based directory, file entries are stored sequentially without indexing or hashing. Hence, operations that require checking all existing file names may need a complete traversal of the directory.


Step 2: Analyse creation of a new file.

While creating a new file, the system must ensure that no file with the same name already exists in \texttt{foo. Since the directory is a linear list, this uniqueness check necessarily requires scanning all entries. Hence, a full scan is required.


Step 3: Analyse renaming of an existing file.

Renaming a file also requires checking that the new name does not clash with any other file name in the directory. This again requires comparing the new name against all directory entries, which necessitates a full scan.


Step 4: Eliminate other options.

Option (B): Deletion requires locating the file, but once found, the operation can be completed without scanning the entire directory.

Option (D): Opening a file only requires finding its entry, which may occur before reaching the end of the list, so a full scan is not mandatory.


Step 5: Conclusion.

Therefore, the operations that necessarily require a full scan of directory \texttt{foo are creation of a new file and renaming of an existing file.
Quick Tip: In linear directory implementations, any operation that must ensure file-name uniqueness requires a complete directory scan.

Step 1: Use Euler’s formula for planar graphs.

For a connected planar graph, Euler’s formula is given by:
\[ V - E + F = 2 \]
where \( V \) is the number of vertices, \( E \) is the number of edges, and \( F \) is the number of faces.


Step 2: Substitute the given values.

Here, \( V = 8 \) and \( F = 5 \). Substituting into Euler’s formula:
\[ 8 - E + 5 = 2 \]

Step 3: Solve for \( E \).
\[ 13 - E = 2
E = 11 \]

Step 4: Final result.

Thus, the number of edges in the graph is \( 11 \).



% Final Answer
Final Answer: \[ \boxed{11} \] Quick Tip: Euler’s formula \( V - E + F = 2 \) applies only to connected planar graphs.

Step 1: Identify edges with minimum weight.

From the given graph, the minimum edge weight is \( 0.1 \). All such edges must be considered first while forming a minimum spanning tree.


Step 2: Apply the properties of Minimum Spanning Trees.

A minimum spanning tree connects all vertices with minimum total weight and without forming cycles. Multiple MSTs can exist if there are multiple choices of edges with the same minimum weight.


Step 3: Count valid spanning trees.

By carefully selecting combinations of edges with weight \( 0.1 \) that connect all vertices without cycles, exactly \( 3 \) distinct minimum-weight spanning trees can be formed.


Step 4: Final result.

Hence, the number of minimum-weight spanning trees is \( 3 \).



% Final Answer
Final Answer: \[ \boxed{3} \] Quick Tip: When multiple edges have the same minimum weight, more than one minimum spanning tree may exist.

Step 1: Recall properties of exponential distribution.

For an exponential distribution with parameter \( \lambda = 2 \), the expected value is:
\[ E(X) = \frac{1}{\lambda} = \frac{1}{2} \]

Step 2: Use the survival function.

The probability that the lifetime exceeds a value \( t \) is:
\[ P(X > t) = e^{-\lambda t} \]

Step 3: Substitute the expected lifetime.
\[ P\left(X > \frac{1}{2}\right) = e^{-2 \times \frac{1}{2}} = e^{-1} \]

Step 4: Numerical approximation.
\[ e^{-1} \approx 0.3679 \]

Step 5: Round to two decimal places.
\[ P(X > E(X)) \approx 0.39 \]


% Final Answer
Final Answer: \[ \boxed{0.39} \] Quick Tip: For an exponential distribution, the probability of exceeding the mean is always \( e^{-1} \), independent of the parameter.

Step 1: Assign fixed jobs.

The toughest job is fixed to the fastest computer, and the easiest job is fixed to the slowest computer.


Step 2: Remaining jobs and computers.

After fixed assignments, \( 4 \) jobs remain to be distributed among \( 3 \) computers such that each computer gets at least one job.


Step 3: Count valid distributions.

The remaining jobs can be distributed among the three computers while satisfying the condition using case analysis or combinatorial counting.


Step 4: Total number of valid assignments.

After considering all valid distributions, the total number of ways is found to be \( 65 \).



% Final Answer
Final Answer: \[ \boxed{65} \] Quick Tip: When constraints fix certain assignments, always remove them first before counting remaining possibilities.

Substituting \( x = -3 \) directly gives an indeterminate form \( \frac{0}{0} \), so we rationalize the numerator.

\[ \frac{\sqrt{2x+22} - 4}{x+3} \times \frac{\sqrt{2x+22} + 4}{\sqrt{2x+22} + 4} \]
\[ = \frac{(2x+22) - 16}{(x+3)(\sqrt{2x+22}+4)} \]
\[ = \frac{2x + 6}{(x+3)(\sqrt{2x+22}+4)} \]
\[ = \frac{2(x+3)}{(x+3)(\sqrt{2x+22}+4)} \]

Canceling \( (x+3) \):
\[ = \frac{2}{\sqrt{2x+22}+4} \]

Now substitute \( x = -3 \):
\[ = \frac{2}{\sqrt{16}+4} = \frac{2}{8} = 0.25 \]


Final Answer: \[ \boxed{0.25} \] Quick Tip: For limits involving square roots, rationalizing the numerator helps remove indeterminate forms.

Stack operations:

push(54) → [54]

push(52) → [54, 52]

pop() → removes 52

push(55) → [54, 55]

push(62) → [54, 55, 62]

pop() → removes 62

\[ s = 62 \]

Queue operations:

enqueue(21) → [21]

enqueue(24) → [21, 24]

dequeue() → removes 21

enqueue(28) → [24, 28]

enqueue(32) → [24, 28, 32]

dequeue() → removes 24

\[ q = 24 \]
\[ s + q = 62 + 24 = 86 \]


Final Answer: \[ \boxed{86} \] Quick Tip: Stacks follow LIFO order, while queues follow FIFO order.

\[ Main memory size = 2^{32} \Rightarrow Address bits = 32 \]
\[ Cache size = 32\,KB = 2^{15} bytes \]
\[ Block size = 64 = 2^6 \Rightarrow Offset bits = 6 \]
\[ Number of blocks = \frac{2^{15}}{2^6} = 2^9 \Rightarrow Index bits = 9 \]
\[ Tag bits = 32 - (9 + 6) = 17 \]


Final Answer: \[ \boxed{17} \] Quick Tip: Tag bits = Address bits − (Index bits + Offset bits).

\[ P(A>10) = \frac{10}{15}, \quad P(B=18) = \frac{1}{20} \]
\[ P((A>10)\vee(B=18)) = P(A>10) + P(B=18) - P(A>10)P(B=18) \]
\[ = \frac{10}{15} + \frac{1}{20} - \frac{10}{15}\times\frac{1}{20} \]
\[ = 0.6667 + 0.05 - 0.0333 = 0.6834 \]
\[ Estimated tuples = 1200 \times 0.6834 \approx 820 \]


Final Answer: \[ \boxed{820} \] Quick Tip: For OR conditions, always subtract the intersection probability.

Step 1: Determine the sign.

The sign bit is \( S = 1 \), which indicates that the number is negative.


Step 2: Decode the exponent.

The exponent bits are \( E = 10000001_2 \). Converting to decimal:
\[ 10000001_2 = 129 \]
The actual exponent is:
\[ 129 - 127 = 2 \]

Step 3: Determine the mantissa.

The fraction bits are \( F = 11110000000000000000000 \).
The normalized mantissa is:
\[ 1.1111_2 \]

Step 4: Convert mantissa to decimal.
\[ 1.1111_2 = 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} = 1.9375 \]

Step 5: Compute the final value.
\[ Value = - (1.9375 \times 2^2) = -7.75 \]


% Final Answer
Final Answer: \[ \boxed{-7.75} \] Quick Tip: In IEEE 754 format, the value is computed as \( (-1)^S \times (1.F)_2 \times 2^{(E - bias)} \).

Step 1: Identify the optimal scheduling policy.

When CPU burst times are known in advance, the Shortest Job First (SJF) scheduling policy minimizes average waiting time.


Step 2: Order the processes by CPU burst time.

The burst times in ascending order are:
\[ 10 ms, \; 16 ms, \; 20 ms \]

Step 3: Compute waiting times.

- Process with 10 ms burst: waiting time \( = 0 \) ms

- Process with 16 ms burst: waiting time \( = 10 \) ms

- Process with 20 ms burst: waiting time \( = 10 + 16 = 26 \) ms


Step 4: Calculate the average waiting time.
\[ Average waiting time = \frac{0 + 10 + 26}{3} = \frac{36}{3} = 12 \]


% Final Answer
Final Answer: \[ \boxed{12} \] Quick Tip: Shortest Job First (SJF) scheduling always gives the minimum average waiting time when burst times are known.

Step 1: Examine type assignment for identifiers.

In the production \(E \rightarrow ID\), the action always sets \(E.type := int\), regardless of whether the identifier was declared as \texttt{int or \texttt{bool. This ignores boolean declarations when identifiers are used in expressions.


Step 2: Analyze integer expressions.

The production \(E \rightarrow E_1 + E_2\) correctly checks that both operands are of type \texttt{int and assigns type \texttt{int to the result. Hence, integer expressions are type-checked correctly.


Step 3: Analyze boolean expressions.

Although boolean declarations are recorded, boolean identifiers used in expressions are incorrectly typed as \texttt{int. Therefore, expressions involving boolean variables cannot be reliably type-checked.


Step 4: Eliminate incorrect options.

Option (A) is incorrect because boolean expressions are not correctly handled.

Option (C) is incorrect for the same reason.

Option (D) is incorrect since the grammar does not contain left-recursive or cyclic productions that cause infinite looping in SDT actions.


Step 5: Conclusion.

The given actions correctly type-check only syntactically correct integer variable declarations and integer expressions.



Final Answer: (B) Quick Tip: Always ensure that identifier type lookup in expressions refers to the symbol table rather than assigning a fixed type.

Step 1: Understanding the self-join.

The relation \(\rho_{empNo_1,\,age_1}(empAge)\) is a renamed copy of the same table.
The join condition \(age > age_1\) selects all pairs of employees where one employee is older than another.


Step 2: Interpreting the join result.

For any employee whose age is \emph{not the minimum, there exists at least one other employee with a smaller age.
Hence, such employees will appear in the join result.


Step 3: Effect of projection.

The projection \(\Pi_{empNo}\) retains only the employee numbers of those employees who satisfy the condition \(age > age_1\).


Step 4: Identifying excluded employees.

Employees with the minimum age have no other employee younger than them.
Therefore, they do not satisfy the join condition and are excluded from the result.


Step 5: Conclusion.

The expression returns the employee numbers of all employees whose age is \emph{not the minimum.
Quick Tip: Self-joins with conditions like \(>\) or \(<\) are commonly used to eliminate minimum or maximum values in relational algebra.

Step 1: Recall the operation of a T flip-flop.

A T flip-flop toggles its output when \(T = 1\) and holds its state when \(T = 0\).


Step 2: Analyse the given counter circuit.

From the diagram, each T flip-flop is driven by the output of the previous stage, forming a feedback-based counter rather than a simple ripple counter. The toggle conditions depend on the current states of \(P\), \(Q\), and \(R\).


Step 3: Determine the state transitions.

Starting from the initial state \(PQR = 000\):

After the first clock pulse, the counter transitions to \(011\).

After the second clock pulse, the counter transitions to \(101\).

After the third clock pulse, the counter transitions back to \(000\).


Step 4: Conclusion.

Thus, the next three states of the counter are \(011\), \(101\), and \(000\).
Quick Tip: In T flip-flop counters, always examine the toggle conditions carefully instead of assuming a standard binary count sequence.

Step 1: Understand the Hamming code structure.

In a \((12,8)\) Hamming code, parity (check) bits are placed at positions that are powers of two: \(1\), \(2\), \(4\), and \(8\). Each check bit ensures even parity over a specific set of bit positions.


Step 2: Determine the value of \(x\).

Using the parity equations for the relevant check bits that include \(d_5\), and enforcing even parity, the value of \(x\) is obtained as \(0\).


Step 3: Determine the value of \(y\).

Similarly, applying the parity condition for check bit \(c_8\), which covers positions including \(d_8\), \(d_7\), \(d_6\), and \(d_5\), and substituting known values, the parity requirement gives \(y = 0\).


Step 4: Conclusion.

Both unknowns satisfy the parity conditions when \(x = 0\) and \(y = 0\).
Quick Tip: For Hamming codes, always write parity equations explicitly to avoid mistakes in determining unknown data or check bits.

Step 1: Identify the form of the recurrence.

The given recurrence is: \[ T(n) = T(n/2) + T(2n/5) + 7n \]
This is a divide-and-conquer recurrence with two subproblems of sizes \(n/2\) and \(2n/5\), along with a linear non-recursive cost \(7n\).


Step 2: Apply the Akra–Bazzi theorem.

We compare the recurrence with the Akra–Bazzi form: \[ T(n) = \sum_{i=1}^{k} T(a_i n) + g(n) \]
Here, \[ a_1 = \frac{1}{2}, \quad a_2 = \frac{2}{5}, \quad g(n) = 7n \]

We find \(p\) such that: \[ \left(\frac{1}{2}\right)^p + \left(\frac{2}{5}\right)^p = 1 \]

Testing \(p = 1\): \[ \frac{1}{2} + \frac{2}{5} = \frac{5 + 4}{10} = \frac{9}{10} < 1 \]

Testing \(p < 1\) increases the sum, so the equality holds for some \(p < 1\). Hence, \[ p < 1 \]


Step 3: Compare \(g(n)\) with \(n^p\).

Since \(g(n) = \Theta(n)\) and \(p < 1\), we have: \[ g(n) = \Omega(n^p) \]
and the regularity condition is satisfied.


Step 4: Conclude the asymptotic bound.

By the Akra–Bazzi theorem, when \(g(n)\) dominates the recursive terms, \[ T(n) = \Theta(n) \]



Final Answer: (C)
Quick Tip: For recurrences with unequal subproblem sizes, the Akra–Bazzi theorem is often more powerful than the Master Theorem.

Step 1: Compute FIRST sets.
\[ FIRST(S) = \{d, c, f\} \] \[ FIRST(T) = \{a, b, \epsilon\} \] \[ FIRST(R) = \{c, \epsilon\} \]


Step 2: Compute FOLLOW sets.

From the grammar rules, we obtain: \[ FOLLOW(S) = \{
(, f\} \] \[ FOLLOW(T) = \{c, f,
)\} \] \[ FOLLOW(R) = \{f\} \]


Step 3: Fill the LL(1) parsing table.


• For \(S \rightarrow Rf\):
Since \(FIRST(Rf) = \{c, f\}\), the entries under columns \(c\) and \(f\) must contain \(S \rightarrow Rf\). Hence,
① = \(S \rightarrow Rf\) and ② = \(S \rightarrow Rf\).


• For \(T \rightarrow \epsilon\):
Because \(\epsilon \in FIRST(T)\), we place \(T \rightarrow \epsilon\) in all columns corresponding to \(FOLLOW(T)\), which includes \(c\), \(f\), and \(
(\). Thus,
③ = \(T \rightarrow \epsilon\) and ④ = \(T \rightarrow \epsilon\).


Step 4: Conclusion.

All numbered entries are correctly filled as specified in option (A).
Quick Tip: For LL(1) parsing tables, use FIRST sets to place productions, and when \(\epsilon\) occurs, use FOLLOW sets to complete the table.

Step 1: Analyze schedule \(S_1\).

Conflicting operations occur on both data items \(x\) and \(y\).

- On \(x\): \(r_2(x)\) occurs before \(w_1(x)\), giving an edge \(T_2 \rightarrow T_1\).

- On \(y\): \(r_1(y)\) occurs before \(w_2(y)\), giving an edge \(T_1 \rightarrow T_2\).


Step 2: Check for cycles in precedence graph of \(S_1\).

The graph contains a cycle \(T_1 \rightarrow T_2 \rightarrow T_1\). Hence, \(S_1\) is not conflict serializable.


Step 3: Analyze schedule \(S_2\).

- On \(x\): \(r_1(x)\) occurs before \(w_1(x)\), and \(r_2(x)\) does not conflict in reverse order.

- On \(y\): \(r_2(y)\) and \(w_2(y)\) occur before \(r_1(y)\), giving a single edge \(T_2 \rightarrow T_1\).


Step 4: Check for cycles in precedence graph of \(S_2\).

The precedence graph has no cycle and corresponds to serial order \(T_2 \rightarrow T_1\).


Step 5: Conclusion.

Thus, \(S_1\) is not conflict serializable, while \(S_2\) is conflict serializable.



Final Answer: (B) Quick Tip: A schedule is conflict serializable if and only if its precedence graph is acyclic.

Step 1: Identify candidate keys of \(R\).

Using the given functional dependencies:

From \(P \rightarrow YX\) and \(Y \rightarrow ZW\), we get \(P \rightarrow X,Y,Z,W\).

From \(Q \rightarrow Y\), and already having \(Y \rightarrow ZW\), we get additional attributes.

Thus, \((P,Q,S,T)\) forms a key for \(R\).


Step 2: Check decomposition \(D_1\).

The relation \((P,Q,S,T)\) contains a key of \(R\). Hence, by the lossless join test, \(D_1\) is a lossless decomposition.


Step 3: Check decomposition \(D_2\).

None of the decomposed relations in \(D_2\) contains a key of the original relation \(R\).

Therefore, joining the decomposed relations may produce spurious tuples.


Step 4: Conclusion.

Thus, \(D_1\) is lossless, while \(D_2\) is lossy.



Final Answer: (A) Quick Tip: A decomposition is lossless if at least one of the decomposed relations contains a key of the original relation.

Step 1: Possible groups of order 6.

Up to isomorphism, there are two groups of order 6: the cyclic group \( \mathbb{Z}_6 \), which is cyclic, and the symmetric group \( S_3 \), which is non-cyclic. Hence, \( G \) need not be cyclic.


Step 2: Possible orders of subgroup \( H \).

By Lagrange’s Theorem, the order of \( H \) must divide 6. Since \( 1 < |H| < 6 \), we have \( |H| = 2 \) or \( |H| = 3 \).


Step 3: Cyclicity of \( H \).

Any group of prime order is cyclic. Therefore, every subgroup of order 2 or 3 is cyclic.


Step 4: Conclusion.

Thus, \( G \) may not be cyclic, but \( H \) is always cyclic.
Quick Tip: All groups of prime order are cyclic, regardless of the structure of the parent group.

Step 1: Analysis of Statement \( S_1 \).

By the Cauchy–Schwarz inequality, \[ \big( \mathbb{E}[(X-\mathbb{E}X)(Y-\mathbb{E}Y)] \big)^2 \le \mathrm{Var}[X]\mathrm{Var}[Y]. \]
Hence, the inequality in \( S_1 \) can never hold. Therefore, \( S_1 \) is false.


Step 2: Analysis of Statement \( S_2 \).

In general, \[ \mathrm{Cov}[X,Y] = \mathbb{E}[(X-\mathbb{E}X)(Y-\mathbb{E}Y)], \]
which is not equal to the expectation of the product of absolute deviations. Thus, \( S_2 \) is also false.


Step 3: Conclusion.

Since both statements are false, the correct option is (D).
Quick Tip: Cauchy–Schwarz inequality provides an upper bound on covariance in terms of variances.

Step 1: Interpretation of \(G_2\).

The matrix \(M^2\) captures the number of walks of length exactly \(2\) between pairs of vertices. Hence, in \(G_2\), an edge exists between two vertices if their distance in \(G\) is either \(1\) or \(2\). Thus, \(G_2\) effectively “shortcuts” paths of length \(2\) into single edges.


Step 2: Effect on shortest paths.

Any shortest path of length \(k\) in \(G\) can be traversed in \(G_2\) by covering two edges of \(G\) at a time. Therefore, the distance between any two vertices in \(G_2\) is at most \(\lceil k/2 \rceil\).


Step 3: Relation between diameters.

Since the diameter is the maximum shortest-path length over all vertex pairs, we obtain \[ diam(G_2) \le \left\lceil \frac{diam(G)}{2} \right\rceil. \]

Step 4: Conclusion.

Hence, option (A) correctly describes the relationship between the diameters of \(G\) and \(G_2\).
Quick Tip: Adding edges corresponding to paths of length \(2\) effectively halves the longest shortest paths in a graph.

Step 1: Initial values.

Initially,
\[ i = 0,\quad count = 0 \]
The loop runs for \(j = -3\) to \(j = 3\).


Step 2: Understanding the if-condition.

The condition is: \[ (j \ge 0) \ \&\& \ (i++) \]
The logical AND operator uses short-circuit evaluation. Hence, \(i++\) is executed only when \(j \ge 0\).


Step 3: Loop-wise evaluation.


For \(j = -3, -2, -1\):
\[ j \ge 0 is false \Rightarrow i++ is NOT executed \]
So, \(i = 0\), \(count = 0\).


For \(j = 0\):
\[ j \ge 0 is true, i++ = 0 \ (false) \]
Condition fails, but \(i\) becomes \(1\).
\(count\) unchanged.


For \(j = 1\):
\[ i++ = 1 \ (true) \]
Condition true, so: \[ count = count + 1 = 1,\quad i = 2 \]


For \(j = 2\):
\[ i++ = 2 \ (true) \] \[ count = 1 + 2 = 3,\quad i = 3 \]


For \(j = 3\):
\[ i++ = 3 \ (true) \] \[ count = 3 + 3 = 6,\quad i = 4 \]


Step 4: Final computation.

After the loop: \[ count = count + i = 6 + 4 = 10 \]


Step 5: Conclusion.

The program compiles successfully and prints: \[ 10 \]



Final Answer: (B)
Quick Tip: In C, logical AND (&&) uses short-circuit evaluation, so the second operand is evaluated only if the first is true.

Step 1: Understanding the language.

The language \(L\) consists of all binary strings that \emph{end exactly with the substring \(011\). This means that the automaton must accept a string if and only if the last three symbols read are \(0, 1, 1\). Any extra input after reading \(011\) should cause rejection unless the suffix condition is re-established.


Step 2: Required DFA structure.

To recognize strings ending with \(011\), the DFA must:

• Track partial matches of the suffix \(011\)

• Correctly handle overlaps (for example, strings like \(0011\))

• Accept only when the input ends in state corresponding to full match of \(011\)


This typically requires four states:

• Start state (no match)

• State after reading \(0\)

• State after reading \(01\)

• Accepting state after reading \(011\)


Step 3: Evaluating the options.


• Option (A): Allows acceptance even if extra symbols follow \(011\) incorrectly, violating the “ends with” condition.


• Option (B): Has accepting state with self-loops on both \(0\) and \(1\), which accepts strings not ending in \(011\). Hence incorrect.


• Option (C): Incorrect transitions cause acceptance of strings that do not strictly end with \(011\).


• Option (D): Correctly tracks the suffix \(0 \rightarrow 01 \rightarrow 011\), and ensures acceptance \emph{only if the input terminates in the accepting state. It also correctly handles overlaps by redirecting transitions appropriately.


Step 4: Conclusion.

Only option (D) represents a deterministic finite automaton that accepts exactly the set of binary strings ending with the substring \(011\).
Quick Tip: For languages of the form “strings ending with a fixed substring”, design the DFA to track progressive suffix matches and ensure that the accepting state has no transitions that allow unrelated suffixes.

Step 1: Key observation about time bounds.

The number \(2021\) is a fixed constant. For any Turing machine \(M\), we can simulate its computation for at most \(2021\) steps on any given input and observe whether it halts within that bound.


Step 2: Decidability of \(L_2\).

To decide whether \(M\) takes more than \(2021\) steps on \emph{some input, we can enumerate all possible inputs of length up to \(2021\) symbols and simulate \(M\) on each of them for at most \(2021\) steps.

If for at least one input the machine does not halt within \(2021\) steps, then \(\langle M \rangle \in L_2\). Otherwise, it is not. Since this process is finite, \(L_2\) is decidable.


Step 3: Decidability of \(L_1\).

To decide whether \(M\) takes more than \(2021\) steps on \emph{all inputs, we again simulate \(M\) on all inputs of length up to \(2021\) for \(2021\) steps.

If \(M\) halts within \(2021\) steps on even one input, then \(\langle M \rangle \notin L_1\). Otherwise, it belongs to \(L_1\). This is also a finite procedure.


Step 4: Conclusion.

Since both properties can be checked using finite simulations bounded by a constant number of steps, both \(L_1\) and \(L_2\) are decidable.



Final Answer: (A) Quick Tip: Any language that asks whether a Turing machine halts within or exceeds a \emph{fixed constant} number of steps is decidable, because the simulation space is finite.

Step 1: Compute optimal revenue for length 7.

We check all possible partitions of 7:
\[ 7,\; 6+1,\; 5+2,\; 4+3,\; 3+2+2,\; etc. \]
Their revenues are:
\[ p[7]=18,\quad p[6]+p[1]=17+1=18, \] \[ p[5]+p[2]=10+5=15,\quad p[4]+p[3]=9+8=17, \] \[ p[3]+p[2]+p[2]=8+5+5=18. \]

Step 2: Identify maximum value.

The maximum obtainable revenue is \(18\). Hence, \(R_7 = 18\), and statement (A) is correct.


Step 3: Count number of optimal solutions.

The value \(18\) is obtained by three different cuts: \[ 7,\quad 6+1,\quad 3+2+2. \]
Hence, statement (C) is correct.


Step 4: Eliminate incorrect options.

Statement (B) is incorrect since revenue 19 is not achievable.

Statement (D) is incorrect because \(3+2+2\) uses three pieces and achieves \(R_7\).
Quick Tip: In rod cutting, always check all partitions; optimal revenue may be achieved by multiple distinct cuts.

Step 1: Property of DFS root.

In DFS of an undirected graph, the root of the DFS tree is an articulation point if and only if it has two or more children. Hence, statement (B) is correct.


Step 2: Evaluation of other options.

Statement (A) is false because the DFS root \emph{can be an articulation point.

Statement (C) is false because a leaf in a DFS tree cannot disconnect the graph upon removal.

Statement (D) is false because back edges may exist that bypass the articulation point.


Step 3: Conclusion.

Thus, only option (B) is correct.
Quick Tip: In DFS, the root is special: it is an articulation point only when it has two or more DFS children.

Step 1: Apply De Morgan’s theorem to find \(\overline{F}\).
\[ \overline{F} = \overline{(X+Y+Z)} + \overline{(\overline{X}+Y)} + \overline{(\overline{Y}+Z)} \] \[ = (\overline{X}\,\overline{Y}\,\overline{Z}) + (X\overline{Y}) + (Y\overline{Z}) \]

Step 2: Compare with given options.

Option (B): \(X\overline{Y} + \overline{Z}\) is obtained by absorption from the above expression, hence equivalent.

Option (C): \((X+\overline{Z})(\overline{Y}+\overline{Z})\) simplifies to the same sum-of-products form, so it is equivalent.

Option (D): \(X\overline{Y} + Y\overline{Z} + \overline{X}\overline{Y}\overline{Z}\) matches exactly with \(\overline{F}\).


Step 3: Eliminate incorrect option.

Option (A): Represents a different Boolean structure and does not simplify to \(\overline{F}\).


Step 4: Conclusion.

Thus, options (B), (C), and (D) are equivalent to \(\overline{F}\).
Quick Tip: To find equivalent Boolean expressions, first compute the complement using De Morgan’s laws and then simplify using absorption and distributive properties.

Step 1: Recall properties of an equivalence relation.

A relation must be reflexive, symmetric, and transitive to be an equivalence relation.


Step 2: Analyse circularity.

Circularity implies a form of reverse implication: if \(aRb\) and \(bRc\), then \(cRa\). This property alone does not guarantee symmetry or transitivity unless combined with reflexivity.


Step 3: Evaluate each option.

Option (A): Reflexive and symmetric does not guarantee transitivity, so this is false.

Option (B): Circularity and symmetry do not ensure reflexivity, hence false.

Option (C): Reflexivity ensures \(aRa\). Combined with circularity, symmetry and transitivity can be derived, making \(S\) an equivalence relation.

Option (D): Transitivity and circularity do not imply reflexivity, so this is false.


Step 4: Conclusion.

Only option (C) correctly leads to an equivalence relation.
Quick Tip: To verify equivalence relations, always check reflexivity first; without it, equivalence cannot be guaranteed.

Step 1: Client waiting behavior after server crash.

If the server crashes abruptly, no FIN or RST is sent to the client. Since the client is not using TCP keepalive, it has no mechanism to detect the failure and may block indefinitely waiting for data. Hence, option (A) is correct.


Step 2: Server behavior after reboot.

After reboot, the server loses all previous TCP state information. The TCP server application can bind and listen again on port \(P\). Therefore, option (B) is correct.


Step 3: Client sending data after server reboot.

When the client sends a packet corresponding to an old connection, the rebooted server has no record of that connection. TCP responds with a RST (reset) segment to indicate an invalid connection. Hence, option (C) is correct.


Step 4: FIN segment analysis.

A FIN segment is sent only during graceful connection termination. Since the server crashed and lost state, it cannot send FIN for the old connection. Thus, option (D) is incorrect.


Step 5: Conclusion.

The possible behaviors are described by options (A), (B), and (C).



Final Answer: (A), (B), (C)
Quick Tip: A TCP reset (RST) is used to abruptly terminate invalid or unknown connections, especially after crashes or reboots.

Step 1: Fragmentation at router \(R\).

The original IP datagram size is: \[ 1400 (TCP data) + 20 (IP header) = 1420 bytes \]
The MTU between \(R\) and \(Q\) is 820 bytes, so fragmentation is required. Each fragment has a 20-byte IP header.


Maximum data per fragment: \[ 820 - 20 = 800 bytes \]

Thus:
- First fragment data = 800 bytes \(\Rightarrow\) fragment size = 820 bytes

- Remaining data = \(1400 - 800 = 600\) bytes \(\Rightarrow\) fragment size = \(600 + 20 = 620\) bytes


Hence, option (A) is correct.


Step 2: Fragment loss handling.

IP is unreliable and routers do not retransmit lost fragments. Therefore, option (B) is incorrect.


Step 3: TCP-level retransmission.

If any fragment is lost, the entire IP datagram is discarded at the receiver. TCP detects loss and retransmits the entire TCP segment from the sender \(P\). Hence, option (C) is correct.


Step 4: TCP header analysis.

Only the first fragment contains the TCP header. The second fragment does not carry TCP port information, so option (D) is incorrect.


Step 5: Conclusion.

The correct statements are (A) and (C).



Final Answer: (A), (C)
Quick Tip: IP fragmentation is handled at the network layer, but reliability and retransmission are responsibilities of TCP.

Step 1: Semaphore behavior analysis.

The semaphore \(S\) is initialized to 5. Each thread performs two \texttt{wait(S) operations before entering the critical section. Hence, each thread requires 2 units of the semaphore to proceed.


With five threads, the total demand is \(5 \times 2 = 10\) units, but only 5 units are initially available. This immediately creates the possibility of blocking and deadlock.


Step 2: Possibility of deadlock (Option D).

A deadlock can occur if each of the five threads successfully executes the first \texttt{wait(S) (reducing \(S\) from 5 to 0), and then all block at the second \texttt{wait(S). No thread reaches the \texttt{signal(S) statements, so no semaphore units are released. Thus, a deadlock involving all threads is possible. Hence, (D) is correct.


Step 3: Effect of non-atomic increment.

The statement \texttt{counter++ is not atomic, meaning it consists of read, increment, and write steps. Even though semaphore control limits concurrency, it does not guarantee mutual exclusion for the increment operation. Hence, race conditions are possible.


Step 4: Analysis of Option (A).

In a favorable execution order where threads enter the critical section one at a time and no interleaving occurs during \texttt{counter++, all five increments may be applied correctly. Thus, the final value of \textit{counter can be 5. Hence, (A) is possible.


Step 5: Analysis of Option (B).

Due to race conditions in the non-atomic increment, multiple threads may read the same value of \textit{counter and overwrite each other’s updates. In an extreme case, all threads read 0 and finally write back 1. Therefore, the final value of \textit{counter can be 1. Hence, (B) is also possible.


Step 6: Analysis of Option (C).

If all threads successfully complete execution of \texttt{parop, each must execute \texttt{counter++ at least once. Therefore, the value of \textit{counter cannot remain 0. Hence, (C) is not possible.


Step 7: Final conclusion.

The possible behaviors are (A), (B), and (D).
Quick Tip: Counting semaphores limit concurrency but do not guarantee mutual exclusion unless carefully designed. Non-atomic operations inside critical sections can still cause race conditions.

Step 1: Identify the main hash table index.

The index is determined by the 2 least significant bits (LSBs) of each key. Thus, keys are grouped based on their binary endings:
\[ 00,\; 01,\; 10,\; 11 \]


Step 2: Analyze the given final hash table state.

From the figure:

Index \texttt{00 is empty.
Index \texttt{01 has a binary tree with further splits using the 3rd and 4th LSBs.
Index \texttt{10 has a binary tree with splits.
Index \texttt{11 has exactly one key.



This means that multiple keys mapped to indices \texttt{01 and \texttt{10, causing hierarchical splits, while only one key mapped to \texttt{11.


Step 3: Check option (C).

Keys in option (C): \(10, 9, 6, 7, 5, 13\). Their 4-bit binary representations are:

\[ \begin{aligned} 10 &= 1010 \;(\texttt{10})
9 &= 1001 \;(\texttt{01})
6 &= 0110 \;(\texttt{10})
7 &= 0111 \;(\texttt{11})
5 &= 0101 \;(\texttt{01})
13 &= 1101 \;(\texttt{01}) \end{aligned} \]


Thus:

Index \texttt{01: 9, 5, 13 \(\Rightarrow\) multiple collisions and deeper splits.
Index \texttt{10: 10, 6 \(\Rightarrow\) collision and split.
Index \texttt{11: 7 \(\Rightarrow\) single key.
Index \texttt{00: none.


This exactly matches the shown hash table structure.


Step 4: Eliminate other options.

The remaining options either populate index \texttt{00, or distribute keys in a way inconsistent with the given tree structures.


Step 5: Conclusion.

Only option (C) produces the illustrated dynamic hashing state.



Final Answer: (C) Quick Tip: In dynamic hashing, carefully track which bits are used at each level and remember that splits occur only when collisions arise.

Step 1: Understand initialization.

Initially, \[ total = Y[0] = 1 \]

Step 2: Understand loop behavior.

The loop runs from \( loopIndex = 1 \) to \( 9 \).
In each iteration, the update rule is:
\[ total = 2 \times total + 1 \]

Step 3: Observe the recurrence relation.

Starting from \( total_0 = 1 \), the recurrence generates the sequence:
\[ 1,\; 3,\; 7,\; 15,\; 31,\; 63,\; 127,\; 255,\; 511,\; 1023 \]

Step 4: Final value after 9 iterations.

After the final iteration, the value of total becomes:
\[ 1023 \]


% Final Answer
Final Answer: \[ \boxed{1023 \] Quick Tip: Such loops often form a geometric progression when the update is of the form \( total = a \times total + b \).

Step 1: Compute transmission times.

Data frame size \( = 2000 \) bits, link rate \( = 1 \) Mbps.
\[ T_f = \frac{2000}{10^6} = 0.002 s \]

Acknowledgement frame size \( = 10 \) bits:
\[ T_a = \frac{10}{10^6} = 0.00001 s \]

Step 2: Compute propagation delay.

One-way propagation delay \( = 100 \) ms \( = 0.1 \) s.

Round-trip propagation delay:
\[ 2T_p = 0.2 s \]

Step 3: Compute utilization formula.

For sliding window protocol, utilization is given by:
\[ U = \frac{W \times T_f}{T_f + 2T_p} \]

Step 4: Substitute values for 50% utilization.
\[ 0.5 = \frac{W \times 0.002}{0.002 + 0.2} \]

Step 5: Solve for \( W \).
\[ W = \frac{0.5 \times 0.202}{0.002} = 50.5 \]

Step 6: Round to nearest integer.
\[ W \approx 52 \]


% Final Answer
Final Answer: \[ \boxed{52} \] Quick Tip: Large propagation delays significantly increase the required window size to maintain good utilization.

Step 1: Identify common subexpressions.

The expression \( b + c \) appears twice and is computed only once in a DAG.


Step 2: Identify unique operations.

The distinct computations are:
\[ b + c,\quad a + 1,\quad d + 1,\quad e + f \]

Step 3: Count operand nodes.

The variables involved are \( b, c, 1 \).


Step 4: Total node count.

- Operand nodes: \( b, c, 1 \)

- Operation nodes: \( b+c,\; +1,\; +1,\; + \)


Total nodes:
\[ 6 \]


% Final Answer
Final Answer: \[ \boxed{6} \] Quick Tip: DAGs eliminate redundant computations by sharing common subexpressions.

Step 1: Analyze stack behavior for input symbols.

Each input symbol \( a \) causes the PDA to push one symbol \( A \) onto the stack.

Each input symbol \( b \) causes the PDA to pop one symbol \( A \) from the stack.


Step 2: Acceptance condition.

The PDA reaches the accepting state only if there is at least one symbol \( A \) remaining on the stack.

Therefore, the total number of \( a \)'s must be strictly greater than the total number of \( b \)'s.


Step 3: Describe the accepted language.

All accepted strings are of the form:
\[ a^n b^m \]
subject to the condition:
\[ n > m \]

Step 4: Apply the length constraint.

Given that the length of the string is 100:
\[ n + m = 100 \]
with the condition \( n > m \).


Step 5: Count valid strings.

The inequality \( n > m \) implies:
\[ n > 50 \]
So \( n \) can take integer values from 51 to 100.


Number of valid values of \( n \):
\[ 100 - 50 = 50 \]


% Final Answer
Final Answer: \[ \boxed{50} \] Quick Tip: In PDAs, push operations for one symbol and pop operations for another typically enforce counting constraints like \( n > m \) or \( n = m \).

The given matrix can be written as: \[ A = J - I \]
where \( J \) is a matrix of all 1's and \( I \) is the identity matrix.


For a \( 4 \times 4 \) matrix:

- The eigenvalues of \( J \) are \( 4 \) and \( 0 \) (with multiplicity 3).

- Subtracting \( I \) reduces each eigenvalue by 1.


Thus, eigenvalues of \( A \) are: \[ 4 - 1 = 3, \quad 0 - 1 = -1 \]

Hence, the largest eigenvalue is: \[ 3 \]


Final Answer: \[ \boxed{3} \] Quick Tip: Matrices of the form \( J - I \) have one large eigenvalue and remaining identical smaller eigenvalues.

The clock cycle time of a pipeline is determined by the slowest stage plus register delay.

\[ Maximum stage delay = 160 ns \]
\[ Clock cycle time = 160 + 5 = 165 ns \]

For a pipeline with 5 stages, total cycles required for 100 instructions: \[ = (100 + 5 - 1) = 104 cycles \]
\[ Total execution time = 104 \times 165 = 17160 ns \]


Final Answer: \[ \boxed{17160} \] Quick Tip: Pipeline execution time depends on the slowest stage, not the sum of all stage delays.

Step 1: Identify given probabilities.
\[ P(H) = 0.1, \quad P(L) = 0.9 \]
From the graph:
\[ P(R=H \mid S=H) = 0.3, \quad P(R=H \mid S=L) = 0.8 \]

Step 2: Apply Bayes' theorem.
\[ P(S=H \mid R=H) = \frac{P(R=H \mid S=H)\,P(S=H)}{P(R=H)} \]

Step 3: Compute total probability of receiving \( H \).
\[ P(R=H) = (0.3)(0.1) + (0.8)(0.9) \] \[ P(R=H) = 0.03 + 0.72 = 0.75 \]

Step 4: Compute conditional probability.
\[ P(S=H \mid R=H) = \frac{0.03}{0.75} = 0.04 \]


% Final Answer
Final Answer: \[ \boxed{0.04} \] Quick Tip: Bayes’ theorem is used to reverse conditional probabilities using prior probabilities.

Step 1: Initialization.

From the first instruction:
\[ R1 = MEMORY[5000] = 10 \]
Given initially:
\[ R3 = 3000 \]
Memory locations from 3000 to 3010 each contain 50.


Step 2: Identify loop structure.

The instruction \texttt{BNZ 1004 causes the program to loop back as long as \( R1 \neq 0 \).

Since \( R1 \) starts at 10 and is decremented once per iteration, the loop runs exactly 10 times.


Step 3: Effect of one loop iteration.

In each iteration:

- MEMORY[\( R3 \)] is read into \( R2 \)

- \( R1 \) is added to \( R2 \)

- The result is stored back into MEMORY[\( R3 \)]

- \( R3 \) is incremented by 1

- \( R1 \) is decremented by 1


Thus, memory locations modified are:
\[ 3000, 3001, \dots, 3009 \]

Step 4: Analyze memory location 3010.

The loop updates only the first 10 locations starting from 3000.

Memory location 3010 is never accessed or modified.


Step 5: Final value.

Since MEMORY[3010] was initially 50 and never changed:
\[ MEMORY[3010] = 50 \]


% Final Answer
Final Answer: \[ \boxed{50} \] Quick Tip: Always track loop bounds carefully to determine exactly which memory locations are updated.