GATE 2026 Previous Year Questions (PYQs) with Solutions

The words “expedite”, “hasten”, and “hurry” all mean to speed up or make something happen faster.

The word with the same meaning is “Accelerate”.

Therefore, the correct answer is Accelerate.

Compare the boundaries of the given part in Panel I with the candidate pieces in Panel II. The required second part must fill the white stepped cut-out exactly so that the two pieces together form the original square PQRS.

The missing outline has one vertical projection and one horizontal stepped projection arranged in the same orientation as shape (iii). Shapes (i), (ii), and (iv) either place the projections on the wrong side or form a mirror orientation that will not fit the gaps in Panel I.

Therefore, the other part is shape (iii).

Each day is independently cloudy with probability 1/2 and sunny with probability 1/2.

We need exactly 3 cloudy days and 1 sunny day in 4 days.

Choose the position of the sunny day: C(4,1) = 4 ways.
Probability of any one such sequence = (1/2)^4 = 1/16.

Required probability = 4 × 1/16 = 1/4.

Therefore, the probability is 1/4.

Stock A price initially = Rs. 50. Investment in A = Rs. 100, so number of shares of A = 100/50 = 2.
Next day price of A = Rs. 55, so selling value = 2 × 55 = Rs. 110. Profit from A = 110 - 100 = Rs. 10.

Stock B price initially = Rs. 80. Investment in B = Rs. 80, so number of shares of B = 80/80 = 1.
Next day price of B = Rs. 70, so selling value = 1 × 70 = Rs. 70. Loss from B = 80 - 70 = Rs. 10.

Net profit = 10 - 10 = Rs. 0.

Therefore, the profit made by the investor is Rs. 0.

Let R mean “it is raining” and D mean “peacocks dance”.

The given sentence says: R -> D.

The only logically equivalent necessary statement among the options is the contrapositive: not D -> not R.

In words, if peacocks are not dancing, then it is not raining.

Therefore, the necessarily true option is: “When peacocks are not dancing, it is not raining.”

The analogy should use the same relationship on both sides. Water is used to satisfy thirst. Similarly, food is used to satisfy hunger.

So P = Thirst and Q = Hunger.

Therefore, the correct option is P = Thirst; Q = Hunger.

Count the black dots in each tile. In Panel I, the first row has 8 + 1 + 6 = 15 black dots. The first column has 8 + 3 + 4 = 15 black dots, and the second column has 1 + 5 + 9 = 15 black dots. Therefore the same total of 15 must be maintained for every row and column.

For the second row, the upper missing tile must have 15 - (3 + 5) = 7 black dots. For the third row, the lower missing tile must have 15 - (4 + 9) = 2 black dots. Only option (i) gives a vertical pair with 7 black dots in the upper tile and 2 black dots in the lower tile. Hence option (i) is correct.

Concept

A Hamiltonian cycle is a closed walk in a graph that visits every vertex exactly once before returning to the start — exactly the "visit each city once and return" trip the question describes. This is different from an Euler circuit, which instead must traverse every edge exactly once and requires every vertex to have even degree; Euler circuits are not relevant here because the constraint in this question is on cities (vertices), not on roads (edges).

A useful fact for checking existence: if a vertex has degree 2, both of its incident edges must be part of any Hamiltonian cycle passing through it, since there is no alternative edge available. When several such degree-2 vertices are all forced to share the same one or two neighbours, this can force a neighbour to need more cycle-edges than a cycle allows — giving a quick way to rule a graph out.

Application

Figure (i) is a 4×4 grid graph (16 vertices). Labelling positions (row, column) with rows and columns numbered 1–4, an explicit closed route through every vertex is:

1. Traverse row 1 left to right: (1,1) → (1,2) → (1,3) → (1,4).

2. Drop to row 2 and traverse right to left, stopping one column early: (1,4) → (2,4) → (2,3) → (2,2).

3. Drop to row 3 and traverse left to right, stopping one column early: (2,2) → (3,2) → (3,3) → (3,4).

4. Drop to row 4 and traverse right to left across all four columns: (3,4) → (4,4) → (4,3) → (4,2) → (4,1).

5. Climb back up column 1 through row 3 and row 2: (4,1) → (3,1) → (2,1).

6. Close the cycle: (2,1) → (1,1).

This route touches all 16 vertices exactly once and returns to the start, so figure (i) admits the required trip.

Figure (ii) has 5 vertices. Two of them (call the top-left vertex and the bottom-right vertex) each connect to three other vertices; the remaining three vertices each connect to exactly those same two vertices and nothing else — each has degree 2.

1. Each of the three degree-2 vertices has only two edges available, both going to the top-left and bottom-right vertices, so any Hamiltonian cycle passing through one of them must use both of its edges — there is no other edge to substitute.

2. Applying this to all three degree-2 vertices forces all three of their edges toward the top-left vertex to be included in the cycle, which would give that single vertex three cycle-edges.

3. A Hamiltonian cycle can only use exactly two cycle-edges at every vertex, so three forced edges at one vertex is a contradiction.

4. Therefore figure (ii) cannot have a Hamiltonian cycle.

Cross-check

Running the same forcing argument from the bottom-right vertex instead of the top-left one gives an identical contradiction — all three degree-2 vertices equally force their edge toward the bottom-right vertex, again demanding three cycle-edges there. Both directions agree, confirming figure (ii) has no Hamiltonian cycle, while the explicit 16-step route above confirms figure (i) does.

So the trip described is possible for figure (i) but not for figure (ii).

From Panel I, the required row counts from top to bottom are 3, 1, 2, and 2. The required column counts from left to right are 2, 2, 2, and 2.

Check each option against both sets of counts.

Option (ii) has 3 shaded cells in the first row, 1 in the second row, 2 in the third row, and 2 in the fourth row. Its four columns also each contain exactly 2 shaded cells.

The other options fail at least one row or column count.

Therefore, the correctly shaded grid is option (ii).

There are 6 x 6 = 36 equally likely ordered outcomes when the die is rolled twice. The possible prime sums are 2, 3, 5, 7 and 11. Their counts are: sum 2 -> 1 outcome, sum 3 -> 2 outcomes, sum 5 -> 4 outcomes, sum 7 -> 6 outcomes, and sum 11 -> 2 outcomes. Thus the number of favourable outcomes is 1 + 2 + 4 + 6 + 2 = 15. Therefore the required probability is 15/36. Hence option C is correct.

Step-by-Step Solution

Let's break down the statement: "There is a person who does not know anyone else, but that person is known by everyone else."

1. Analyze the Subject

The phrase "There is a person" indicates an existential quantifier (∃). Let's call this person y. So, we start with (∃y).

2. Analyze the Condition for Others

The phrase "everyone else" refers to all other persons x. This requires a universal quantifier (∀). So, for the person y, the condition must hold for all x where x ≠ y.

3. Translate the Relationships

The statement has two parts for the relationship between x and y (where x ≠ y):

• "that person is known by everyone else": This means x knows y, represented as M(x, y).

• "who does not know anyone else": This means y does not know x, represented as ¬M(y, x).

These two conditions must be true simultaneously, so we use the AND operator (∧).

4. Construct the Final Expression

Combining the quantifiers and the condition:

For all x (where x ≠ y), M(x, y) is true AND ¬M(y, x) is true.

There exists a y such that for all x (where x ≠ y), the condition holds.

Expression: (∃y)(∀x) ((x ≠ y) → (M(x,y) ∧ ¬M(y,x)))

Conclusion

The correct expression corresponds to Option A.

The correct matching is based on the Three-Schema Architecture of a Database Management System.

1. External Schema (III): This level describes the user views. It matches with L: Views.

2. Logical Schema (I): This level describes the structure of the whole database, typically using relations. It matches with N: Relations.

3. Physical Schema (II): This level describes how data is stored, including file organization and indexes. It matches with M: File organization and indexes.

Therefore, the correct matching is I–N, II–M, III–L.

A Turing machine M decides a language L if it satisfies two main conditions for every input string w.

First, M must halt on all inputs, meaning it never enters an infinite loop.

Second, M must accept w if w is in L, and reject w if w is not in L.

This combination ensures that for any input, the machine provides a definitive decision (accept or reject) in finite time.

The standard normal-family density is f(x) = (1/(σ√(2π))) exp(-(x - μ)²/(2σ²)), for -∞ < x < ∞. The given density is (1/(3√(2π))) exp(-x²/18). Comparing terms gives μ = 0 and 2σ² = 18, so σ² = 9 and σ = 3. Therefore X follows a normal distribution. The correct option is Normal.

To solve this, we need to match the traversal names in set T with their visiting orders in set S.

1. Inorder Traversal (I)

In an Inorder traversal, we visit the left subtree first, then the current node, and finally the right subtree. This corresponds to order: left subtree, node, right subtree. This matches description L.

2. Preorder Traversal (II)

In a Preorder traversal, we visit the current node first, then the left subtree, and finally the right subtree. This corresponds to order: node, left subtree, right subtree. This matches description M.

3. Postorder Traversal (III)

In a Postorder traversal, we visit the left subtree first, then the right subtree, and finally the current node. This corresponds to order: left subtree, right subtree, node. This matches description N.

Conclusion

Based on the above analysis: - I matches with L - II matches with M - III matches with N Therefore, the correct match is I–L, II–M, III–N.

Boolean Algebra follows specific laws. The Complement Law states that a variable ANDed with its negation equals 0 (a.a′ = 0), not 1. Options representing the Commutative Law and the OR Complement Law (a+a′ = 1) are valid properties. Since option 1 claims a.a′ = 1, it is incorrect and thus the answer.

The correct answer is C — A dynamically allocated array of integers created using malloc() function call.

In C runtime memory organization:

• Heap → stores dynamically allocated memory using malloc(), calloc(), realloc()

• Stack → stores local variables, function parameters, return addresses

• Data segment → stores static and global variables

So:

• A → Static variable → Data segment

• B → Local array inside function → Stack

• C → malloc() allocated array → Heap ✅

• D → Return address → Stack

Statement S1

In non-vectored interrupt mechanism, it usually takes more time to start the Interrupt Service Routine (ISR) when compared to that in a vectored interrupt mechanism.

This statement is True.

In a vectored interrupt, the interrupting device directly provides the ISR address (or vector number), so the CPU can immediately jump to the corresponding ISR.

In a non-vectored interrupt, the CPU must first identify which device generated the interrupt, usually through additional checking or polling. This extra step increases the interrupt response time.

Therefore, non-vectored interrupts generally take more time to begin ISR execution.

Statement S2

In daisy-chain interrupt mechanism, the CPU polls all the input devices individually to determine the source of the interrupt.

This statement is False.

In a daisy-chain interrupt mechanism, devices are connected serially according to priority. The interrupt acknowledge signal passes through the chain, and the highest-priority requesting device captures it and responds.

The CPU does not poll every device individually. Priority resolution is handled by the hardware chain itself.

Correct Option

Option C: S1 is true and S2 is false

Analysis of Programs

To determine which program compiles, we analyze the variable declarations in each:

Program P1

P1 declares a global variable `int a=5;`. Inside `main`, it declares a local variable `int a=7;`. In C, a local variable can shadow a global variable with the same name. This is valid syntax.

Program P2

P2 declares `int a=5;` and then `int a=7;` inside the same function scope. C does not allow redeclaring a variable with the same name in the same block. This causes a compilation error.

Program P3

P3 declares `int a=5;` and then `float a=7;` inside the same function scope. Similar to P2, redeclaring a variable name in the same block is invalid, regardless of the data type. This causes a compilation error.

Conclusion

Only P1 compiles without any error. P2 and P3 fail due to variable redeclaration errors.

To find the total transfer time, first convert the file size from bytes to bits. Then, identify the bottleneck bandwidth among the three links. Finally, divide the total bits by the bottleneck bandwidth.

File Size = 4 million bytes = 4 * 10^6 * 8 bits = 32 * 10^6 bits.

Bandwidths: 2 Mbps, 500 kbps, 1 Mbps. Bottleneck = 500 kbps = 0.5 * 10^6 bps.

Time = 32 * 10^6 / 0.5 * 10^6 = 64 seconds.

Network protocols utilize different communication methods depending on their purpose. Some operate over direct connections, while others require reaching multiple devices simultaneously.

SMTP, FTP, and HTTP typically function using unicast communication. They establish dedicated links between a specific client and server to exchange data securely and efficiently.

DHCP, however, often requires broadcasting messages during the initial configuration phase. A client sends a broadcast discovery packet to find a DHCP server on the local network without knowing its IP address.

Therefore, among the given options, DHCP is the protocol that may need to broadcast some of its messages to function correctly.

First Come First Serve (FCFS) is inherently non-preemptive because once a process begins execution, it runs to completion. Other algorithms like Round Robin allow interruption based on time slices or priority changes.

Step-by-Step Asymptotic Analysis

To determine the increasing order of asymptotic growth rates, we analyze the behavior of each function as n approaches infinity.

1. Analyze Individual Functions

• log(n): Grows logarithmically. This is the slowest growth among the given functions.

• n^(1/3): Grows as a fractional power of n. Polynomial growth (even with a small exponent) is faster than logarithmic growth.

• 2 log(n): This is a constant multiple of log(n). In asymptotic analysis, constant factors are ignored, so 2 log(n) = Θ(log(n)). It grows at the same rate as log(n).

• log(n!): Using Stirling's approximation, log(n!) ≈ n log(n). This grows faster than any polynomial n^k (where k < 1) and significantly faster than log(n).

2. Compare Growth Rates

Comparing the functions:

• log(n) vs n^(1/3): log(n) grows slower than n^(1/3).

• n^(1/3) vs 2 log(n): n^(1/3) grows faster than 2 log(n) because polynomial growth dominates logarithmic growth.

• 2 log(n) vs log(n!): Since 2 log(n) is Θ(log(n)) and log(n!) is Θ(n log(n)), log(n!) grows much faster.

3. Final Ordering

The correct increasing order of asymptotic growth rates is:

log(n) < n^(1/3) < 2 log(n) < log(n!)

Note: While log(n) and 2 log(n) are in the same complexity class, in terms of specific values for large n, 2 log(n) is strictly greater than log(n). However, the primary distinction is that n^(1/3) sits between the logarithmic terms and the factorial logarithm.

Thus, the list corresponding to this order is Option C.

To determine the time complexity, we analyze each recurrence relation individually.

Option A: T(n) = T(n-1) + 1. Expanding this gives T(n) = T(1) + (n-1). Since T(1) is constant, the complexity is Theta(n).

Option B: T(n) = 2T(n/2) + 1. Using the Master Theorem, a=2, b=2, f(n)=1. Since n^log_b a = n dominates f(n), the complexity is Theta(n).

Option C: T(n) = 2T(n/2) + n. Here a=2, b=2, f(n)=n. Since f(n) matches n^log_b a, the complexity is Theta(n log n).

Option D: T(n) = T(n-1) + n. This sums integers from 1 to n, resulting in a quadratic complexity of Theta(n^2).

Conclusion: Options A and B correspond to an algorithm with time complexity Theta(n).

Given a binary relation R on the set {1, 2, ..., 10} where (x, y) ∈ R if x * y is a perfect square.

Reflexive: For any x, x * x = x^2, which is always a perfect square. Thus, (x, x) ∈ R for all x. The relation is Reflexive.

Symmetric: If x * y is a square, then y * x is the same product and also a square. Thus, (x, y) ∈ R implies (y, x) ∈ R. The relation is Symmetric.

Transitive: If x * y = a^2 and y * z = b^2, then (x * y) * (y * z) = (ab)^2. Dividing by y^2 gives x * z = (ab/y)^2. Since x, y, z are integers, x * z is a square. The relation is Transitive.

Antisymmetric: Consider x = 2 and y = 8. x * y = 16 (square), so (2, 8) ∈ R. Also (8, 2) ∈ R. Since 2 ≠ 8, the relation is not Antisymmetric.

Conclusion: The relation R satisfies Reflexive, Symmetric, and Transitive properties.

I(a) = ∫ from -1 to 1 (3x² - ax + 1) dx. Split the integral: ∫3x² dx - a∫x dx + ∫1 dx over [-1, 1]. The middle term is 0 because x is an odd function on a symmetric interval. Therefore I(a) = [x³] from -1 to 1 + [x] from -1 to 1 = (1 - (-1)) + (1 - (-1)) = 2 + 2 = 4. Hence I(a) is independent of a and is always positive. The true statements are options 1 and 3.

Step-by-Step Analysis

First, convert the 4-bit two's complement numbers to decimal to determine their values. The range for 4-bit two's complement is -8 to +7.

N1 = 1011: Invert bits (0100) + 1 = 0101 (5). Since MSB is 1, value is -5.

N2 = 1101: Invert bits (0010) + 1 = 0011 (3). Since MSB is 1, value is -3.

N3 = 1010: Invert bits (0101) + 1 = 0110 (6). Since MSB is 1, value is -6.

N4 = 1001: Invert bits (0110) + 1 = 0111 (7). Since MSB is 1, value is -7.

Evaluate Each Operation

Option A (N1 + N2): -5 + (-3) = -8. This is within the range [-8, +7]. No overflow.

Option B (N2 + N3): -3 + (-6) = -9. This is less than -8. Arithmetic overflow occurs.

Option C (N3 - N4): -6 - (-7) = -6 + 7 = 1. This is within the range. No overflow.

Option D (N1 + N4): -5 + (-7) = -12. This is less than -8. Arithmetic overflow occurs.

Both Option B and Option D result in arithmetic overflow.

Analysis of Grammar Ambiguity

A grammar is considered ambiguous if there exists at least one string that has more than one leftmost derivation or parse tree.

Option A generates strings of the form an bn. Each string has a unique derivation sequence, making this grammar unambiguous.

Option B allows multiple parse trees for expressions like id + id * id due to missing operator precedence rules. This creates ambiguity.

Option C allows derivation of strings like 'aa' via left recursion (S -> aS -> aa) or right recursion (S -> Sa -> aa). This results in ambiguity.

Option D generates strings of the form an. Each string length corresponds to a unique number of recursive steps, ensuring a single derivation tree.

Conclusion: Options B and C are ambiguous grammars.

Hash Table Chain Analysis

Given hash function: h(k) = k mod 9

Step 1: Calculate hash values for each key

• 5 mod 9 = 5

• 28 mod 9 = 1

• 19 mod 9 = 1

• 15 mod 9 = 6

• 26 mod 9 = 8

• 33 mod 9 = 6

• 12 mod 9 = 3

• 17 mod 9 = 8

• 10 mod 9 = 1

Step 2: Build chains at each index

• Index 0: (empty)

• Index 1: 28 → 19 → 10 (length = 3)

• Index 2: (empty)

• Index 3: 12 (length = 1)

• Index 4: (empty)

• Index 5: 5 (length = 1)

• Index 6: 15 → 33 (length = 2)

• Index 7: (empty)

• Index 8: 26 → 17 (length = 2)

Step 3: Find maximum chain length

The longest chain is at index 1 with length 3.

Answer: 3

For a system of linear equations to have multiple (infinite) solutions, the ratios of corresponding coefficients must be equal.

Given: ax + y = b and 16x + ay = 24. Condition: a/16 = 1/a = b/24.

From a/16 = 1/a, we get a^2 = 16, so a = ±4. From 1/a = b/24, we get b = 24/a.

Product ab = a * (24/a) = 24. Thus, the product of a and b is 24.

To find the number of void merge operations, we trace the Merge Sort algorithm on the array A = [10, 7, 8, 19, 41, 35, 25, 31].

Step 1: Divide the Array

The array is recursively divided until sub-arrays of size 1 are reached:

• Level 0: [10, 7, 8, 19, 41, 35, 25, 31]

• Level 1: [10, 7, 8, 19] and [41, 35, 25, 31]

• Level 2: [10, 7], [8, 19], [41, 35], [25, 31]

• Level 3 (Base): [10], [7], [8], [19], [41], [35], [25], [31]

Step 2: Perform Merges (Bottom-Up)

A merge is 'void' if the largest element of the left sub-array is less than or equal to the smallest element of the right sub-array. In this case, the output is just the left elements followed by the right elements.

• Merge 1: [10] and [7]. Left max (10) > Right min (7). Result: [7, 10]. (Not void)

• Merge 2: [8] and [19]. Left max (8) < Right min (19). Result: [8, 19]. (Void)

• Merge 3: [41] and [35]. Left max (41) > Right min (35). Result: [35, 41]. (Not void)

• Merge 4: [25] and [31]. Left max (25) < Right min (31). Result: [25, 31]. (Void)

• Merge 5: [7, 10] and [8, 19]. Left max (10) > Right min (8). Result: [7, 8, 10, 19]. (Not void)

• Merge 6: [35, 41] and [25, 31]. Left max (41) > Right min (25). Result: [25, 31, 35, 41]. (Not void)

• Merge 7: [7, 8, 10, 19] and [25, 31, 35, 41]. Left max (19) < Right min (25). Result: [7, 8, 10, 19, 25, 31, 35, 41]. (Void)

Step 3: Count Void Merges

The void merges occurred in Merge 2, Merge 4, and Merge 7.

Total void merge operations = 3.

Step 1: Convert the subnet mask 255.255.240.0 to binary notation. The third octet 240 corresponds to 11110000 in binary.

Step 2: Count the network bits. There are 8 + 8 + 4 = 20 network bits in total.

Step 3: Determine the host bits. Subtract network bits from 32 total bits: 32 - 20 = 12 host bits.

Step 4: Calculate total addresses. 2 raised to the power of 12 equals 4096 total addresses.

Step 5: Calculate usable addresses. Subtract 2 reserved addresses (network and broadcast) from the total: 4096 - 2 = 4094.

Step-by-Step Conversion

The given 32-bit IEEE 754 single precision hexadecimal value is 0xC2710000.

First, convert the hexadecimal value to binary:

C = 1100, 2 = 0010, 7 = 0111, 1 = 0001, 0 = 0000, 0 = 0000, 0 = 0000, 0 = 0000

Binary: 1100 0010 0111 0001 0000 0000 0000 0000

Break down the 32 bits into Sign (1 bit), Exponent (8 bits), and Mantissa (23 bits):

Sign bit: 1 (Negative number)

Exponent bits: 10000100

Mantissa bits: 11100010000000000000000

Calculate the actual exponent:

Exponent (binary) = 10000100 = 128 + 4 = 132

Actual Exponent = 132 - 127 (bias) = 5

Calculate the significand (Mantissa + 1):

Mantissa = 1.1110001 (binary)

Convert to decimal: 1 + 1/2 + 1/4 + 1/8 + 1/128 = 1 + 0.5 + 0.25 + 0.125 + 0.0078125 = 1.8828125

Final Calculation:

Value = (-1)^Sign × Significand × 2^Actual Exponent

Value = -1 × 1.8828125 × 2^5

Value = -1 × 1.8828125 × 32

Value = -60.25

The decimal representation rounded to two decimal places is -60.25.

To find the number of tokens, we parse the input string from left to right using the given grammar rules.
Rules: id starts with a letter, number starts with a digit.
x1 -> id
23 -> number
mm -> id
78 -> number
y -> id
7 -> number
z -> id
zz5 -> id
14 -> number
A -> id
8 -> number
H -> id
AaYcD -> id
Total number of tokens = 13.

Step 1: A spanning tree of a complete graph K_n with n vertices contains exactly n-1 edges.

Step 2: The Jaccard coefficient between two sets of edges E1 and E2 is defined as |E1 ∩ E2| / |E1 ∪ E2|.

Step 3: To minimize the coefficient, we must minimize the intersection size |E1 ∩ E2|.

Step 4: For n > 4, the complete graph K_n contains at least two edge-disjoint spanning trees.

Step 5: If two spanning trees are edge-disjoint, their intersection size is zero. This results in a Jaccard coefficient of 0 / (2n - 2) = 0.

Shortest Path in Directed Acyclic Graph

For a weighted Directed Acyclic Graph (DAG), the shortest paths from a single source can be found efficiently using a combination of topological sorting and edge relaxation.

Algorithm Steps

1. Compute the topological sort of the graph vertices.

2. Initialize distances from the source to infinity, except source distance is zero.

3. Process vertices in topological order and relax all outgoing edges.

Time Complexity Analysis

Topological sorting takes O(V + E) time. Relaxing all edges also takes O(V + E) time. Therefore, the total worst-case time complexity is O(V + E), which is linear.

The given condition requires checking if the difference between consecutive elements is strictly increasing for all valid indices.

Let D[i] = A[i+1] - A[i]. The condition becomes D[i] > D[j] for all i > j, which implies the sequence D must be strictly increasing.

We can compute all D values and verify the increasing order in a single pass through the array. This involves O(n) operations to calculate differences and O(n) to check the order.

Thus, the total time complexity is Θ(n), as we only need to traverse the array once to validate the property.

The recurrence relation depends on T[i-1][j] and T[i][j-1]. Both algorithms must ensure these values are computed before T[i][j].

Algorithm B1 iterates i from 1 to n, then j from 1 to n. When computing T[i][j], T[i-1][j] is from the previous row (already computed) and T[i][j-1] is from the current row (already computed). Thus, B1 is correct.

Algorithm B2 iterates S from 2 to 2n. Dependencies T[i-1][j] and T[i][j-1] have index sums S-1. Since S increases, values for S-1 are computed before S. Thus, B2 is also correct.

Conclusion: Both algorithms respect the dependency structure and compute the table correctly.

The given Boolean function is F(A,B,C,D) = Σm(0,1,2,3,8,9,10,11).

Convert minterms to binary (A is MSB, D is LSB):

0: 0000, 1: 0001, 2: 0010, 3: 0011, 8: 1000, 9: 1001, 10: 1010, 11: 1011

Group 1 (0,1,2,3): A=0, B=0. Term: A'B'

Group 2 (8,9,10,11): A=1, B=0. Term: AB'

Combine terms: A'B' + AB' = B'(A' + A) = B'

Construct the LR(0) item sets and count the states that contain both a completed item, which gives a reduce action, and an item that shifts a terminal.

1. For A → aA | ε, the initial state and the state reached after shifting a both contain A → · and also have a shift on a. This gives 2 shift-reduce conflicts.
2. After A is recognized, the analogous C states contain C → · and also have a shift on c. This gives 2 more shift-reduce conflicts.
3. For B → bB | b, the state reached after shifting b contains B → b · as a reduce item and also has a shift on b from B → · bB / B → · b. This gives 1 more shift-reduce conflict.

Total conflicts = 2 + 2 + 1 = 5.
Therefore, option D is correct.

The correct answer is Option D: Augmentation and Transitivity.

Proof of Union Rule:

Given:
X → Y
X → Z

Step 1:
From X → Y, apply Augmentation with X:

XX → XY

Since XX = X,

X → XY

Step 2:
From X → Z, apply Augmentation with Y:

XY → YZ

Step 3:
Using Transitivity on:

X → XY
XY → YZ

We get:

X → YZ

Thus, the Union rule is derived using only:

• Augmentation

• Transitivity

Reflexivity is not required in this proof.

Hence, the correct answer is Option D.

Generator polynomial: 1001
Degree = 3 → append 3 zeros to the data.

Data bits:
110001011 → 110001011000

Now perform mod-2 division of 110001011000 by 1001.

After XOR divisions, the remainder obtained = 100.

So the CRC bits appended to the data = 100.

Final transmitted bit pattern:
110001011100

✔ Answer: 100 (remainder appended).

Concept

For a fixed 16-bit instruction word with variable-length prefix opcodes, each opcode reserves every bit pattern formed by its operand fields. Therefore, the fractions of the instruction space occupied by all instruction classes must add to at most 1.

If a class has k operand bits and n opcodes, it occupies n × 2k encodings out of 216. This is the prefix-space constraint expressed by the Kraft inequality.

Application

1. Each register number needs log2(16) = 4 bits.

2. An M-type instruction has 2 × 4 + 6 = 14 operand bits. Its 2 opcodes occupy 2 × 214 = 32768 encodings.

3. An R-type instruction has 3 × 4 = 12 operand bits. Its 7 opcodes occupy 7 × 212 = 28672 encodings.

4. A C-type instruction has 4 + 6 = 10 operand bits. If N C-type opcodes are provided, they occupy N × 210 encodings.

5. The total cannot exceed 216: 2 × 214 + 7 × 212 + N × 210 ≤ 216.

6. Dividing by 210 gives 32 + 28 + N ≤ 64, so N ≤ 4. Therefore, the maximum number of C-type opcodes is 4.

Cross-check

Using opcode-prefix fractions directly: 2/22 + 7/24 + N/26 ≤ 1. Thus 1/2 + 7/16 + N/64 ≤ 1, which again gives N ≤ 4.

Live Variable Analysis Solution

We perform backward data flow analysis to find the set of live variables at the exit of each basic block (LiveOut). A variable is live at a point if its value is used along some path from that point to the exit.

Step 1: Analyze Block B4

Statement: g = d + e

Uses: {d, e}, Defines: {g}

Successor: Exit (no live variables)

LiveOut(B4) = ∅

LiveIn(B4) = Uses ∪ (LiveOut(B4) - Defines) = {d, e} ∪ (∅ - {g}) = {d, e}

Step 2: Analyze Block B2

Statement: d = a + e

Uses: {a, e}, Defines: {d}

Successor: B4

LiveOut(B2) = LiveIn(B4) = {d, e}

LiveIn(B2) = {a, e} ∪ ({d, e} - {d}) = {a, e}

Step 3: Analyze Block B1 and B3 (Loop)

Block B1: a = b + c. Uses: {b, c}, Defines: {a}. Successors: B2, B3.

Block B3: e = a + f. Uses: {a, f}, Defines: {e}. Successor: B1.

Equations:

LiveOut(B1) = LiveIn(B2) ∪ LiveIn(B3) = {a, e} ∪ LiveIn(B3)

LiveIn(B1) = {b, c} ∪ (LiveOut(B1) - {a})

LiveIn(B3) = {a, f} ∪ (LiveIn(B1) - {e})

Solving the system:

1. LiveIn(B1) = {b, c} ∪ ({a, e} ∪ LiveIn(B3) - {a}) = {b, c, e} ∪ LiveIn(B3)

2. Substitute LiveIn(B3): LiveIn(B1) = {b, c, e} ∪ {a, f} ∪ (LiveIn(B1) - {e})

3. This implies LiveIn(B1) must contain {a, b, c, e, f}. Let's verify: LiveIn(B1) = {b, c, e, f}.

If LiveIn(B1) = {b, c, e, f}, then LiveIn(B3) = {a, f} ∪ ({b, c, e, f} - {e}) = {a, b, c, f}.

Then LiveOut(B1) = {a, e} ∪ {a, b, c, f} = {a, b, c, e, f}.

Check consistency: LiveIn(B1) = {b, c} ∪ ({a, b, c, e, f} - {a}) = {b, c, e, f}. Consistent.

Final Result

LiveOut(B1) = {a, b, c, e, f}

LiveOut(B2) = {d, e}

LiveOut(B3) = LiveIn(B1) = {b, c, e, f}

LiveOut(B4) = ∅

A dense index contains an entry for every search-key value in the file, while a sparse index contains entries for only some values.

Statement S1 is true because a hash index must map every search key to a bucket address to ensure retrieval, making it inherently dense.

Statement S2 is true because B+ tree indexes can be implemented as either dense or sparse depending on the specific design requirements and data organization.

Since both statements accurately describe the properties of their respective index types, the correct conclusion is that both S1 and S2 are true.

Option A is false (languages differ).
Example - 000 is accepted by D1 but not by D2

Option B is false (D1 has strings not in D2).
Example - 000 is in D1 but not in D2

Option C is Correct1
The intersection is just {ε}.

Option D is true e.g., '100' has length 3 but is not in either language).

Analysis of Constraints

The base language L = {a^i b^j c^k d^ℓ | i, j, k, ℓ ≥ 0} is regular. The context-free status depends on the constraints linking the counts.

Option A: i + k = j + ℓ

This constraint implies i - j = ℓ - k. A PDA can push for 'a' and 'c', and pop for 'b' and 'd'. State transitions handle stack underflow, making this language context-free.

Option B: i = k and j = ℓ

This requires matching 'a' with 'c' and 'b' with 'd' independently. The structure a^i b^j c^i d^j is not context-free because the stack cannot track two independent counts separated by other symbols.

Option C: i = ℓ and j = k

This forms a^i b^j c^j d^i. A PDA pushes 'a' and 'b', pops 'b' for 'c', and pops 'a' for 'd'. The nesting is valid, so this language is context-free.

Option D: i + j = k + ℓ

This balances the first half against the second half. A PDA pushes for 'a' and 'b', then pops for 'c' and 'd'. The linear relationship allows verification with a single stack.

Conclusion

Options A, C, and D ensure the language is context-free. Option B does not.

Core Idea

For every leaf LiL_iLi​ with successor:

Val(Li)<ki<Val(Suc(Li))\text{Val}(L_i) < k_i < \text{Val}(Suc(L_i))Val(Li​)<ki​<Val(Suc(Li​))

So each new key lies strictly between two consecutive inorder elements

Option A: K cannot have duplicates

TRUE

• Each kik_iki​ lies in a unique open interval between two consecutive keys

• Intervals do not overlap
  So no two kik_iki​ can be equal

Option B: K will have at least one element

FALSE

• If BST has only one node (also a leaf)

• It has no successor
  No kik_iki​ generated

• Option C: Height increases at most by one

TRUE

• Each kik_iki​ is inserted between a leaf and its successor

• So it becomes child of that leaf
  Only extends leaf depth by 1

Option D: Number of nodes doubles
FALSE

• New keys = number of leaves with successor

• In skewed tree → only 1 such leaf
  Not doubling

Final Answer:

A and C

Step 1: Analyze Output Structure The output 4 3 1 2 5 is generated in two phases. First, Stack S is emptied (popped). Second, Queue Q is emptied (dequeued). Thus, 4 3 1 comes from S, and 2 5 comes from Q.

Step 2: Analyze Stack S Stack is LIFO (Last In First Out). Output 4 3 1 means 4 was pushed last, then 3, then 1. So 1, 3, 4 must be in S.

Step 3: Analyze Queue Q Queue is FIFO (First In First Out). Output 2 5 means 2 was enqueued first, then 5. So 2, 5 must be in Q.

Step 4: Conclusion Valid assignment: 1S, 2Q, 3S, 4S, 5Q.

Now check each option

A: $###

✔ Possible

• P1 → * (X=1)

• P2 → * (X=2) → $

• P3 runs later → prints *

• then ###

**B: $*###

✔ Possible

• P1, P2 → ** → $

• P3 → *

• then ###

**C: $##*#

✔ Possible (this is the tricky one)

Sequence:

• P1 → *

• P2 → * → $

• P2 immediately continues → prints #

• P2 signals → another #

• P3 (delayed earlier) now runs → prints *

• last #

So * can appear between #

**D: *$###

❌ NOT possible

Why?

• For this to happen:

  • 3 stars must happen before $

• But $ occurs exactly at X == 2
  So it must appear immediately after 2nd star, not after 3rd

1. Cache Configuration Analysis

Cache Size = 4 KB = 2^12 bytes. Block Size = 16 bytes = 2^4 bytes. Number of Cache Lines = 2^12 / 2^4 = 2^8 = 256 lines. Index Bits = log2(256) = 8 bits. Offset Bits = log2(16) = 4 bits. Physical Address = 16 MB = 2^24 bits. Tag Bits = 24 - 8 - 4 = 12 bits.

2. Address Breakdown (Tag | Index | Offset)

P: 0x845B32 -> Tag: 0x845 | Index: 0xB3 | Offset: 0x2 Q: 0x845B26 -> Tag: 0x845 | Index: 0xB2 | Offset: 0x6 R: 0x845B36 -> Tag: 0x845 | Index: 0xB3 | Offset: 0x6 S: 0x846B32 -> Tag: 0x846 | Index: 0xB3 | Offset: 0x2

3. Access Sequence Analysis (Initially Empty Cache)

Iteration 1: - P: Miss (Load 0xB3, Tag 0x845) - Q: Miss (Load 0xB2, Tag 0x845) - R: Hit (Index 0xB3, Tag 0x845 matches) - S: Miss (Index 0xB3, Tag 0x846 != 0x845). Evicts P. Iteration 2: - P: Miss (Index 0xB3, Tag 0x845 != 0x846). Evicts S. - Q: Hit (Index 0xB2, Tag 0x845) - R: Hit (Index 0xB3, Tag 0x845) - S: Miss (Index 0xB3, Tag 0x846 != 0x845). Evicts R.

4. Conclusion

P always misses due to conflict with S. Q hits after first access (unique index). R always hits (P loads block before R). S always misses due to conflict with P.

Step 1: Calculate the total number of blocks on the disk.

Disk Size = 16 GB = 16 * 2^30 bytes.

Block Size = 2 KB = 2 * 2^10 bytes.

Total Number of Blocks = (16 * 2^30) / (2 * 2^10) = 8 * 2^20 = 8,388,608 blocks.

Step 2: Calculate total space required for pointers.

In a linked list approach, each block stores a pointer to the next free block.

Pointer Size = 4 bytes.

Total Pointer Space = 8,388,608 * 4 bytes.

Step 3: Calculate blocks required to store pointers.

Blocks Required = (Total Pointer Space) / Block Size

= (8,388,608 * 4) / 2048 = 16,384 blocks.

Final Answer: 16384

First, calculate the number of TLB entries. TLB Reach is 1 MB and Page Size is 4 KB. Number of Entries = 1 MB / 4 KB = 256 entries.

Next, determine the bits required per entry. PID is 4 bits. Control field is 2 bits.

Page Number (VPN) bits: Virtual Address Space is 64 GB (2^36). Offset is 12 bits (4 KB). VPN = 36 - 12 = 24 bits.

Frame Number (PFN) bits: Physical Address Space is 1 GB (2^30). Offset is 12 bits. PFN = 30 - 12 = 18 bits.

Total bits per entry = 4 (PID) + 24 (VPN) + 18 (PFN) + 2 (Control) = 48 bits.

Total TLB Size = 256 entries * 48 bits = 12288 bits. Convert to bytes: 12288 / 8 = 1536 bytes.

Step-by-Step Best-Fit Allocation

Initial holes: 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, 12 KB.

Process P1 (16 KB): Find the smallest hole >= 16 KB.

• Candidates: 20 KB, 25 KB, 18 KB.

• Best fit is 18 KB.

Remaining hole from 18 KB: 18 - 16 = 2 KB.

Current holes: 20 KB, 4 KB, 25 KB, 2 KB, 7 KB, 9 KB, 15 KB, 12 KB.

Process P2 (9 KB): Find the smallest hole >= 9 KB.

• Candidates: 20 KB, 25 KB, 9 KB, 15 KB, 12 KB.

• Best fit is exactly 9 KB.

Remaining hole from 9 KB: 9 - 9 = 0 KB (hole disappears).

Final holes: 20 KB, 4 KB, 25 KB, 2 KB, 7 KB, 15 KB, 12 KB.

Count holes with size < 8 KB: 4 KB, 2 KB, 7 KB.

Total count = 3.

In a direct-mapped cache, a byte-addressable physical address splits into a TAG field, a BLOCK-INDEX field, and a BLOCK-OFFSET field. The offset field has log2(block size) bits (here block size = 64 = 26 bytes, so 6 offset bits); the remaining higher-order bits form the block address. For a cache with N = 2k blocks, the block index of any address equals its BLOCK ADDRESS (address ÷ block size, integer division) taken modulo N -- which, since N is a power of two, is exactly the value formed by the block address's lowest k bits.

So the same block index survives as k grows only as long as each newly-included bit of the block address (bit k, k+1, ...) is 0; the moment a 1-bit is included, the index changes. The "maximum possible cache size" is therefore the largest N = 2k for which the block address's low k bits still equal the given block index -- i.e. up to (but not including) the next 1-bit above that index's own bits.

Application:

1. Convert the physical address to decimal: 0xA2C28 = 10×164 + 2×163 + 12×162 + 2×16 + 8 = 655360 + 8192 + 3072 + 32 + 8 = 666,664.

2. With a 64-byte block, the block address = ⌊666,664 ÷ 64⌋ = 10,416 (the low 6 bits of the physical address, 6 bits of 40 = 101000, form the byte-within-block offset and are dropped).

3. Write 10,416 in binary: 10,416 = 101000101100002 (14 bits), i.e. its 1-bits sit at positions 13, 11, 7, 5 and 4 (bit 0 = least significant).

4. For a cache with N = 2k blocks, the block index equals the block address's lowest k bits. Taking the lowest 8, 9, 10 or 11 bits of 10,416 all give the SAME value, 176 (= 101100002 = bits 4, 5 and 7 set), because block-address bits 8, 9 and 10 are all 0 -- it only changes at k = 12, where bit 11 (which is 1) enters and pushes the value up to 176 + 2048 = 2224.

5. So the largest k for which the block index stays 176 is k = 11, giving the maximum cache size N = 211 = 2,048 blocks.

6. With block size 64 bytes, cache size = 2,048 × 64 = 131,072 bytes. In KB (1K = 210): 131,072 ÷ 1024 = 128 KB.

Cross-check:

10,416 mod 2,048 = 176, which matches the given block index. Taking one more index bit (N = 212 = 4,096 blocks = 256 KB) would instead give block index 2,224 (not 176), confirming 131,072 bytes (128 KB) is indeed the maximum cache size consistent with this mapping.

Final answer: 128 KB.

Given:

• MSS = 2 KB → initial cwnd = 1 MSS = 2 KB

• ssthresh = 16 KB

Slow start growth (doubling each round):

• Start: cwnd = 2 KB

• After Round 1: cwnd = 4 KB

• After Round 2: cwnd = 8 KB

• After Round 3: cwnd = 16 KB

Now the key detail
TCP enters congestion avoidance after completing the round where cwnd reaches ssthresh.

So:

• Round 1 → sending with 2 KB

• Round 2 → sending with 4 KB

• Round 3 → sending with 8 KB

• Round 4 → sending with 16 KB (ssthresh)

• Congestion avoidance starts after Round 4 begins transmission

Correct Answer:

4

Your answer is correct.

Step 1: Calculate execution time for non-pipelined design. Time = Cycles × (1 / Frequency) = 5 × (1 / 1.6 GHz).

Step 2: Calculate execution time for pipelined design. Effective Cycles = 1 + (0.30 × 2) = 1.6. Time = 1.6 × (1 / 1.2 GHz).

Step 3: Calculate Speed-up. Speed-up = Time_non-pipelined / Time_pipelined = (5/1.6) / (1.6/1.2) = 2.34375.

First, analyze the 2:4 Decoder (Q). With inputs A and B, the output D0 is high (1) when A=0 and B=0. The output D3 is high (1) when A=1 and B=1.

Next, analyze the 4-to-1 Multiplexer (M). The select lines are S1 and S0. The inputs are: I0=D0, I1=0, I2=1, I3=D3.

The output Y depends on S1 and S0 as follows:

- If S1=0, S0=0, Y selects I0 (D0). Y=1 when A=0, B=0. (1 combination)

- If S1=0, S0=1, Y selects I1 (0). Y is always 0. (0 combinations)

- If S1=1, S0=0, Y selects I2 (1). Y is always 1 regardless of A and B. (4 combinations)

- If S1=1, S0=1, Y selects I3 (D3). Y=1 when A=1, B=1. (1 combination)

Total combinations where Y=1: 1 + 0 + 4 + 1 = 6.

Code Execution Trace

1. Initialization: a = 5, b = 11, c = 20.

2. ptr = &a; The pointer ptr now holds the address of variable a.

3. *ptr = c; Since ptr points to a, this updates a to the value of c (20). Now a = 20.

4. ptr = &c; The pointer ptr is updated to hold the address of variable c.

5. a = *(&b); The address of b is taken and dereferenced, assigning the value of b (11) to a. Now a = 11.

6. c = *ptr - a; ptr points to c, so *ptr is 20. a is 11. Calculation: c = 20 - 11 = 9.

7. printf("%d", c); The program prints the final value of c, which is 9.

To find the maximum return value, we analyze how the 'length' variable changes in each recursive call.

1. If length % 3 == 0: length decreases by 1 (start increases by 1).

2. If length % 3 == 1: length decreases by 1 (end decreases by 1), and 1 is added to the result.

3. If length % 3 == 2: length decreases by 2 (start increases by 2).

Notice the cycle of remainders modulo 3:

- From 1 mod 3, we go to 0 mod 3 (add 1).

- From 0 mod 3, we go to 2 mod 3 (subtract 1).

- From 2 mod 3, we go to 0 mod 3 (subtract 2).

Once the length is not congruent to 1 mod 3, it enters a cycle between 0 and 2, never returning to 1. Thus, the value '1' is added at most once.

The maximum possible value is 1.

For an n × n matrix A, det(kA) = kⁿ det(A). Here n = 4 and k = 2. Hence, det(2A) = 2⁴ det(A) = 16 × 3 = 48. Therefore, the required integer answer is 48.

Let the tosses be numbered 1 to 6. Event E2 says that among tosses 1, 2, 3 and 5 there are exactly two heads.

By symmetry under E2, toss 2 is still equally likely to be H or T, so P(toss 2 is H | E2) = 1/2. Tosses 4 and 6 are independent of E2 and remain fair coin tosses.

Therefore, under E2, the three tosses relevant to E1, namely tosses 2, 4 and 6, behave like three independent fair tosses. The probability of at least two heads among three fair tosses is:

C(3,2)/2^3 + C(3,3)/2^3 = 3/8 + 1/8 = 4/8 = 0.5.

Thus P(E1 | E2) = 0.5, rounded to one decimal place.

Write a number r in (0, 1) as 0.d1d2d3... . The value of f depends only on the second digit d2.

On every open interval (k/100, (k+1)/100), the first two decimal digits are fixed, so f is constant there. Therefore discontinuities can occur only at the boundary points k/100, where k = 1, 2, ..., 99.

Across such a boundary, the second decimal digit changes from (k - 1) mod 10 on the left to k mod 10 on the right. The set for which f = 1 is {2, 3, 6, 7}. The function value changes exactly at the transitions
1 -> 2, 3 -> 4, 5 -> 6, and 7 -> 8.

Thus, in each block of ten hundredths there are 4 discontinuity points. There are 10 such blocks from 0.00 to 1.00, so the total number of discontinuities is 10 x 4 = 40.

Concept

For a sliding-window / Go-Back-N link protocol where every byte gets its own sequence number, the minimum sequence-number width N must satisfy TWO independent constraints at once:

• No-wrap-around: the total distinct sequence numbers, 2N, must exceed the total bytes transmitted during the required no-wrap interval — Bandwidth × Time / 8.

• Maximum utilization: the sequence-number space must be large enough to number every byte in flight during one round-trip time, i.e. 2N must cover the bandwidth-delay product — Bandwidth × RTT / 8, where RTT = 2 × propagation delay.

Since both conditions must hold simultaneously, N is the LARGER of the two individually-required bit counts.

Application

1. Link parameters

Link Length (L) = 3000 km = 3,000,000 meters

Propagation delay per metre (v) = 5 ns/m = 5 × 10-9 s/m

Propagation Delay (T_prop) = L × v = 3,000,000 × 5 × 10-9 = 0.015 seconds

Bandwidth (B) = 108 bits per second

2. Maximum-utilization condition

Round Trip Time (RTT) = 2 × T_prop = 2 × 0.015 = 0.03 seconds

Bandwidth-Delay Product (in bits) = B × RTT = 108 × 0.03 = 3,000,000 bits

Bandwidth-Delay Product (in bytes) = 3,000,000 / 8 = 375,000 bytes

So the window size W must be at least 375,000 bytes, meaning the sequence-number space (2N − 1) must be at least 375,000.

219 = 524,288, which already exceeds 375,000 — so this condition alone needs only N = 19.

3. No-wrap-around condition

Total bytes transmitted in 60 seconds = (Bandwidth × Time) / 8 = (108 × 60) / 8 = 6,000,000,000 / 8 = 750,000,000 bytes

So we need 2N > 750,000,000.

• 229 = 536,870,912 (too small)

• 230 = 1,073,741,824 (greater than 750,000,000)

So this condition needs N = 30.

4. Combine the two conditions

N must satisfy BOTH conditions, so N = max(19, 30) = 30. The wrap-around requirement is the binding (dominant) constraint.

Cross-check

Verify N = 30 independently satisfies both requirements: 230 ≈ 1.074 × 109 bytes of sequence space, which is (a) greater than the 750,000,000 bytes sent in 60 seconds — no wrap — and (b) far greater than the 375,000-byte window needed for full utilization. A smaller value, N = 29, gives only 229 = 536,870,912 sequence numbers, which is less than 750,000,000 and would wrap around before 60 seconds — confirming 30 is the minimum.

Final Answer

The minimum number of bits N is 30.

A Turing machine M decides a language L if and only if it halts on all inputs.

Specifically, for every input string w in the alphabet, M must halt and either accept or reject.

If w is in L, M must accept. If w is not in L, M must reject.

Option D captures both conditions: acceptance for strings in L and rejection for strings outside L.

The correct answer is:

B) antagonist

Explanation:

• A protagonist is the main or central character in a story (usually the hero).

• An antagonist is the character who opposes the protagonist (often the villain).

Why others are incorrect:

• Agnostic – someone unsure about religious beliefs

• Arsonist – a person who sets fires

• Anarchist – someone who opposes authority/government

So, the antonym of protagonist is antagonist

1. Analyze the building blocks: Both given patterns are composed of exactly 4 small square tiles.
2. Establish the core rule: Any new figure constructed without overlapping these blocks must have a total tile count that is perfectly divisible by 4.
3. Count the total tiles in each option: Option A = 2x4 (8 tiles), Option B = 3x4 (12 tiles), Option C = 3x5 (15 tiles), Option D = 4x5 (20 tiles).
4. Since 15 is not a multiple of 4, Option C cannot be formed.

Final Answer: Option C

The grammar S → aSbS | bS | ε generates a Context-Free Language. To check for ambiguity, consider the string 'abb'. It admits two distinct derivations: S ⇒ aSbS ⇒ abS bS ⇒ abb and another structural variation, confirming the grammar is ambiguous (Options 0 and 1). For string 'abab', the derivation structure forces a unique rightmost path, validating Option 2. Since all Context-Free Languages are decidable, the claim regarding undecidability is false.

Step-by-Step Solution

To find the minimum value of k for the system to be deadlock-free, we first determine the maximum number of resources that can be held by the processes without causing a deadlock, and then add one more resource to break the potential deadlock.

1. Analyze the Worst-Case Scenario

A deadlock occurs if every process holds the maximum number of resources it can hold without completing, and no process can proceed. In this scenario:

• There are 5 processes.

• Each process requires a maximum of 2 instances.

• A process can request the second instance only after acquiring the first. This means a process can hold 1 instance and wait for the second.

In the worst-case scenario (potential deadlock), each of the 5 processes holds 1 instance of the resource and is waiting for the second instance. No process can proceed because no resources are available to satisfy the second request.

2. Calculate Resources in Deadlock State

Number of processes = 5 Resources held per process in worst case = 1 Total resources held = 5 × 1 = 5

3. Determine Minimum k for Deadlock-Free System

To prevent deadlock, we need at least one extra resource beyond the worst-case scenario. This extra resource allows one process to acquire its second instance, complete its execution, and release both instances, thereby allowing other processes to proceed.

Minimum k = (Resources in worst case) + 1 Minimum k = 5 + 1 = 6

Final Answer

The minimum value of k for the system to be deadlock-free is 6.

In a knockout tournament with no ties, every game eliminates exactly one player. To declare one winner from 64 players, 63 players must be eliminated. Therefore, the total number of games required is 64 - 1 = 63.

To maximize elective credits, the student should enroll for the maximum allowed total credits, which is 70. The compulsory credits are 15 for core courses and 20 for the project. The minimum specialization credits are 10. Therefore, maximum elective credits = 70 - 15 - 20 - 10 = 25.

Let T mean “the teacher is in the room” and S mean “all students stand silently.” The given statement says T → S. From this, we can conclude S whenever T is true, and we can also conclude the contrapositive ¬S → ¬T. However, the converse S → T is not necessarily true. Students may all be standing even when the teacher is not in the room. Therefore, the statement “If all students are standing, then the teacher is in the room” is not necessarily true.

Statement P claims combinatorics is always invoked, but the passage states it is often used. Thus, P is false. Statement Q aligns with the text regarding assigning probabilities to compute average values. Therefore, Q is true.

Compare each candidate structure with the two projections in Panel I. The correct structure must match the L-shaped front view and also have the same footprint when viewed from the top. Options (i), (ii), and (iii) fail to match one of these two projections. Option (iv) matches both the front view and the top view, so it is the required 3D structure.

H_K(S) = max(S - K, 0) is zero for S <= K and equals S - K for S > K.

For H_10(S) - H_20(S):
- If S <= 10, both terms are zero, so the value is 0.
- If 10 < S <= 20, H_10(S) = S - 10 and H_20(S) = 0, so the value is S - 10.
- If S > 20, H_10(S) = S - 10 and H_20(S) = S - 20, so the value is 10.

This gives exactly the plotted capped ramp: 0 until S = 10, increasing linearly to 10 at S = 20, and then remaining constant at 10. Therefore N(S) = H_10(S) - H_20(S).

Concept

In a ranking puzzle, if one competitor is already ahead and another competitor also strictly exceeds a third competitor, that third competitor cannot hold second place. Candidate cases can therefore be eliminated by combining score validity, timing constraints, and strict rank order.

Application

1. Observation (i) rules out rounds 1 and 2: Neeraj’s medal-winning throws occurred there, while Vítězslav Veselý had no medal-winning throw in either round.

2. Observation (iii) says neither of Veselý’s later throws equalled or improved on the best he had after four rounds. Therefore, rounds 5 and 6 cannot be when he first recorded his best; observation (ii) also identifies his round-6 attempt as a foul.

3. Only rounds 3 and 4 remain. Suppose Veselý first recorded his best throw in round 4.

4. Observation (iv) says Jakub Vadlejch’s round-4 throw was strictly longer than every other valid throw in that round, including Veselý’s assumed personal best. Neeraj’s gold-medal throw was already ahead, so Jakub would also be ahead of Veselý. Veselý would then be third after four rounds, contradicting observation (iii), which places him second.

Cross-check

The official World Athletics series independently confirms the deduction: Veselý’s six attempts were 79.73 m, 80.30 m, 85.44 m, foul, 84.98 m, and foul. His unique best was therefore 85.44 m in round 3. IIT Guwahati’s official GATE 2026 answer key for this master-paper question likewise identifies ‘Third’ as the correct answer.

Result

Vítězslav Veselý first recorded his best throw in the third round.

For each first roll a, count the possible second rolls b such that b is an integer multiple of a.

If a = 1, b can be 1, 2, 3, 4, 5, 6: 6 outcomes.
If a = 2, b can be 2, 4, 6: 3 outcomes.
If a = 3, b can be 3, 6: 2 outcomes.
If a = 4, 5, or 6, only b = a works: 1 outcome each.

Total favorable ordered pairs = 6 + 3 + 2 + 1 + 1 + 1 = 14.
Total possible ordered pairs = 6 × 6 = 36.

Therefore, the required probability is 14/36 = 7/18.

Initially, the urn contains 1 red ball and 1 blue ball (total 2).

After Step 1, picking either color (probability 1/2 each) changes the composition. If Red is picked first, the urn has 2R and 1B (total 3). If Blue is picked first, the urn has 1R and 2B (total 3).

To have equal numbers (2R, 2B) after Step 2, we need the opposite color in the second step. From (2R, 1B), picking Blue has probability 1/3. From (1R, 2B), picking Red has probability 1/3.

Total probability = (1/2 * 1/3) + (1/2 * 1/3) = 1/6 + 1/6 = 1/3.

Choose the entries in the first 3 rows and first 3 columns arbitrarily. This gives 3 × 3 = 9 independent binary choices, so there are 2^9 possibilities. Once these 9 entries are fixed, the entries in the fourth column are determined by the requirement that each of the first three rows has even parity. Similarly, the entries in the fourth row are determined by the requirement that each of the first three columns has even parity. The bottom-right entry is then automatically consistent because the total parity of all row sums and all column sums must match. Therefore, the number of such matrices is 2^9 = 512.

The multiplicity of an eigenvalue refers to its algebraic multiplicity, i.e., the number of times it appears as a root of the characteristic polynomial.

For an n×n matrix:

• The characteristic polynomial has degree n.
  

• Therefore, the sum of the algebraic multiplicities of all eigenvalues is exactly n.
  

• Hence, the maximum possible multiplicity of a single eigenvalue is n.

To solve this matching question, we need to understand the typical use cases for each addressing mode in high-level programming contexts.

1. Immediate Mode (P): In this mode, the operand is a constant value specified directly within the instruction itself. Therefore, it corresponds to a Constant (4).

2. Indirect Mode (Q): Here, the address field contains the address of the operand, which is stored in a memory location. This is commonly used to access Pointers (2).

3. Base with Index (R): This mode uses a base register and an index register. The base register holds the starting address, and the index register holds the offset. This is typically used to access an Element of an array (1).

4. Base with Offset/Displacement (S): This mode uses a base register and a displacement value. The base register points to the start of a data structure, and the offset points to a specific field. This is used to access an Element of a record (3).

Matching these: P-4, Q-2, R-1, S-3.

In a load-store architecture, arithmetic operations can only be performed on data stored in registers. Memory operands cannot be directly accessed by arithmetic instructions.

To implement Z = X + Y, where X, Y, and Z are memory operands, the data must first be moved from memory to registers.

The correct sequence involves loading X into a register, loading Y into another register, adding the two registers, and storing the result into Z.

This ensures compliance with the instruction format where the first operand is the destination and all arithmetic sources are registers.

In a pipelined processor, a data hazard occurs when one instruction depends on the result of another instruction that has not yet completed.

The most common dependency causing this problem is:Read After Write (RAW)

Here, a later instruction needs to read a value that an earlier instruction is still in the process of writing.

Therefore, the correct answer is:

B) Read-after-write

Solution

Step 1: Analyze T2(n). Using Master Theorem with a=5, b=4, we get Theta(n^log4 5).

Step 2: Substitute into T1(n). The recurrence becomes T1(n) = 4T1(n/2) + Theta(n^log4 5).

Step 3: Apply Master Theorem again. Here a=4, b=2, so log_b a = 2.

Step 4: Compare n^log4 5 with n^2. Since 2 > log4 5, the n^2 term dominates.

The client and server can initiate closing of the connection at the same time

HTTP/1.1 supports persistent connections, allowing multiple objects or webpages from the same server over a single TCP connection. It also supports pipelining, which permits sending multiple requests without waiting for previous responses. However, a single TCP connection cannot span multiple distinct servers.

For a real n×n matrix M, the null space (kernel) is the set of vectors x with Mx = 0. Two governing facts follow directly from linear algebra: (1) M is singular — equivalently det(M) = 0 — exactly when its null space contains a nonzero vector, since a nonzero solution of Mx = 0 means the columns of M are linearly dependent; and (2) the null space is itself a linear subspace, so it is closed under scalar multiplication — once it holds one nonzero vector, it holds every nonzero scalar multiple of that vector.

1. The vector (0, 1, 0, …, 0) is the second standard basis vector, e2. It is nonzero and, by hypothesis, lies in the null space of M, so M e2 = 0.

2. Multiplying M by e2 extracts the second column of M, so M e2 = 0 means the second column of M is the zero column.

3. A matrix with a zero column has linearly dependent columns, so by fact (1) it is singular — hence det(M) = 0 for every such M.

4. By fact (2), since e2 is a nonzero vector in the null space, every nonzero scalar multiple c·e2 (c ≠ 0) is also in the null space — giving infinitely many nonzero null-space vectors, so certainly at least two.

Cross-check against the other claims:

• A determinant of 1 would require M to be invertible, but an invertible matrix cannot have a nonzero vector in its null space — so this value is impossible here, consistent with fact (1) instead forcing det(M) = 0.

• The rank is not pinned to any single number: only the second column is forced to be zero, while the remaining n − 1 columns can still be chosen linearly independent, so the rank can be as large as n − 1.

So the properties that hold for every matrix M satisfying the given condition are: det(M) = 0, and the null space contains at least two nonzero vectors.

Solution

Step 1: Convert binary to decimal. X = 10110100 (Sign-Magnitude) = -52. Y = 01001100 = +76.

Step 2: Determine range. 8-bit signed magnitude range is -127 to +127.

Step 3: Evaluate operations. A: -52 + 76 = 24 (Valid). B: -52 - 76 = -128 (Overflow). C: 52 + 76 = 128 (Overflow). D: 52 - 76 = -24 (Valid).

Step 4: Conclusion. Operations B and C result in overflow.

In a binary heap with n elements using 1-based indexing, the parent of node i is floor(i/2). A node i has children if 2*i <= n. Therefore, nodes with indices from 1 to floor(n/2) are internal nodes (non-leaves), and nodes with indices from floor(n/2)+1 to n are leaf nodes. Since n is odd, floor(n/2) equals (n-1)/2. Thus, any index less than or equal to (n-1)/2 does not correspond to a leaf node.

The hash table has size 11 (indices 0-10). The hash function is h(x) = (x + 7) mod 11. We use linear probing for collisions.

1. Insert 1: h(1) = (1+7)%11 = 8. Slot 8 is empty. Place 1 at index 8.

2. Insert 13: h(13) = (13+7)%11 = 9. Slot 9 is empty. Place 13 at index 9.

3. Insert 22: h(22) = (22+7)%11 = 7. Slot 7 is empty. Place 22 at index 7.

4. Insert 15: h(15) = (15+7)%11 = 0. Slot 0 is empty. Place 15 at index 0.

5. Insert 11: h(11) = (11+7)%11 = 7. Slot 7 occupied. Probe 8 (occupied), 9 (occupied), 10 (empty). Place 11 at index 10.

6. Insert 24: h(24) = (24+7)%11 = 9. Slot 9 occupied. Probe 10 (occupied), 0 (occupied), 1 (empty). Place 24 at index 1.

Final occupied indices: 0, 1, 7, 8, 9, 10. Empty indices: 2, 3, 4, 5, 6.

Step 1: Understand the relationship between NFA and DFA states. An NFA with n states can be converted to a DFA with at most 2^n states using the subset construction method.

Step 2: Calculate the maximum number of states. Given n = 6, the maximum number of states in the equivalent DFA is 2^6 = 64.

Step 3: Determine the valid range. The number of states in the minimal DFA equivalent to an NFA with n states must be between 1 and 2^n inclusive.

Step 4: Evaluate the options. Options 32 and 1 are within the range [1, 64]. Options 65 and 128 exceed the maximum limit of 64.

Conclusion: The options that CANNOT be the number of states are 65 and 128.

Statement S1 contains an unclosed string literal, which causes a lexical error because the tokenizer cannot identify the end of the token. Statement S3 attempts to assign a string literal to an integer variable, which is a type mismatch classified as a semantic error. Option 2 correctly identifies S1's lexical error and S3's semantic error, matching standard compiler behavior for these specific code snippets.

LL(1) parsers are predictive parsers that scan input from left to right and construct a leftmost derivation. They use one token of lookahead to decide which production rule to apply.

A grammar must be left-factored to be LL(1). This transformation removes common prefixes from production rules, ensuring the parser can choose the correct rule based on the next input token.

LL(1) grammars cannot be left-recursive. Left recursion causes infinite loops in top-down parsing, so it must be eliminated before parsing table construction.

SLR parsers are more powerful than LL(1) parsers. The class of grammars accepted by SLR parsers is a superset of those accepted by LL(1) parsers.

Statement A is false because the Banker’s algorithm prevents deadlock through avoidance, not prevention. Statement C is false since assignment edges in a resource allocation graph point from resources to processes, indicating allocation. Statements B and D correctly describe deadlock prevention conditions and safe states.

Functional dependencies (FDs) define relationships where one set of attributes determines another in a relational schema.

The Union Rule states that if P ⟶ R and Q ⟶ S, then {P, Q} ⟶ {R, S}. This validates Option C as always true.

The Augmentation Rule states that if P ⟶ R, then {P, Q} ⟶ {R, S}. Adding attributes to the determinant preserves the dependency, validating Option D.

Other options are incorrect because composite dependencies do not imply individual determinants without specific constraints.

In relational database normalization, 3NF decomposition always preserves dependencies using synthesis algorithms. All relations can be decomposed into 1NF while preserving dependencies. However, BCNF decomposition may lose dependencies in some cases. Option D is false because 2NF decompositions can preserve dependencies.

In a full binary tree, every node has either:

• 0 children, or

• 2 children.

For a full binary tree:Number of nodes=2i+1
where iii = number of internal nodes.

Given:

n=23n = 23n=23

To get the maximum height, we make the tree as skewed as possible while still remaining full.

In a full binary tree with maximum height:

• each internal node contributes one extra level,

• and one subtree continues the chain while the other is a leaf.

Number of internal nodes:

Step 1: Convert Hexadecimal to Binary

Convert X and Y from hexadecimal to 32-bit binary representation.

X: 35C00000 -> 0011 0101 1100 0000 0000 0000 0000 0000

Y: 34A00000 -> 0011 0100 1010 0000 0000 0000 0000 0000

Step 2: Parse IEEE 754 Fields

X: Sign=0, Exponent=01101011 (107), Mantissa=1.1000...

Y: Sign=0, Exponent=01101001 (105), Mantissa=1.0100...

Step 3: Align Exponents

Difference in exponents is 2. Shift Y's mantissa right by 2 bits.

Y Mantissa becomes 0.010100... (aligned to exponent 107)

Step 4: Add Mantissas

Add X and aligned Y mantissas: 1.1000... + 0.010100... = 1.110100...

Step 5: Convert Result to Hex

Result Binary: 0011 0101 1110 1000 0000 0000 0000 0000

Hexadecimal: 35E80000

Given:

Physical address space = 2^32 bytes
Cache size = 2^23 bytes
Block size = 128 bytes = 2^7 bytes

--------------------------------------------------
Step 1: Block Offset Bits
--------------------------------------------------

Block offset bits = log2(128)
= 7 bits

--------------------------------------------------
Step 2: Direct Mapped Cache
--------------------------------------------------

Number of cache lines:

= 2^23 / 2^7
= 2^16

Index bits = 16

TAG bits for direct mapped cache:

M = 32 - 16 - 7
M = 9 bits

--------------------------------------------------
Step 3: K-Way Set Associative Cache
--------------------------------------------------

Given:

K = 2^L

Number of sets:

= 2^16 / 2^L
= 2^(16-L)

Set index bits:

= 16 - L

TAG bits:

N = 32 - (16-L) - 7
N = 32 - 16 + L - 7
N = 9 + L

But,

M = 9

Therefore,

N = M + L

--------------------------------------------------
Final Answer
--------------------------------------------------

Option A is correct.

N = M + L
"""

The function counts nodes recursively. For the base case (E1), check if the current node is the last one by verifying head->next == NULL.

For the recursive step (E2), add 1 for the current node and recurse on the next pointer: 1 + getListSize(head->next).

To form a complete BST using numbers 1 to 15,
the final BST must be perfectly balanced.

Hence:

Root = 8

Its immediate children must be:

Left child = 4
Right child = 12

Now analyze insertion order.

1st inserted element:
Must be 8 (root)

2nd inserted element:
Must be either 4 or 12

3rd inserted element:
Must become the other child of root.

Therefore, the third inserted element can only be:

4 or 12

--------------------------------------------------
Checking Options
--------------------------------------------------

Option 1: 4
Possible as third insertion.

Option 2: 2
Possible if:
8, 4, 2
This can still later form a complete BST.

Option 3: 10
Possible if:
8, 12, 10

Option 4: 5
Impossible as third insertion.

Reason:
If 5 is inserted before 4 exists,
then 5 becomes direct left child of 8,
which violates the required complete BST structure.

Hence, 5 can NEVER be the third inserted element.

--------------------------------------------------
Final Answer
--------------------------------------------------

5
"""

Given:

d_k(u) denotes the shortest path weight from s to u
using at most k edges.

--------------------------------------------------
Statement S1
--------------------------------------------------

d_(k+1)(u) <= d_k(u)

Reason:

All paths allowed for d_k(u)
are also allowed for d_(k+1)(u).

Allowing one extra edge can only improve
or maintain the shortest path value.

Therefore:

S1 is TRUE.

--------------------------------------------------
Statement S2
--------------------------------------------------

Claim:

d_k(u) <= d_k(v)

This is FALSE.

Counterexample:

s -> u = 5
u -> v = -10

Then:

d(u) = 5
d(v) = -5

Thus:

d(u) > d(v)

Hence the statement does not always hold.

Therefore:

S2 is FALSE.

--------------------------------------------------
Final Answer
--------------------------------------------------

Only S1 is true.
"""

In TCP slow-start, the congestion window (cwnd) doubles every RTT. Starting with cwnd = 1 segment at t=0, the number of segments sent in round k is 2^k. The cumulative segments sent by time t=k is sum(2^i for i=0 to k) = 2^(k+1) - 1. At t=9, cumulative segments = 2^10 - 1 = 1023. At t=10, cumulative segments = 2^11 - 1 = 2047. Since segment 2000 falls between 1023 and 2047, it is transmitted during the round starting at t=10. Thus, transmission starts at t = 10 ms.

Solution

Given:

Frame size = 1000 bits
Bandwidth = 100 kbps
Propagation delay = 100 ms

--------------------------------------------------
Step 1: Transmission Time
--------------------------------------------------

Transmission time:

Tt = Frame Size / Bandwidth

= 1000 / (100 x 10^3)

= 0.01 s

= 10 ms

--------------------------------------------------
Step 2: Propagation Delay Ratio
--------------------------------------------------

Propagation delay:

Tp = 100 ms

Compute:

a = Tp / Tt

= 100 / 10

= 10

--------------------------------------------------
Step 3: Window Size Formula
--------------------------------------------------

For 100% utilization in sliding window protocol:

W >= 1 + 2a

Substitute value of a:

W >= 1 + 2(10)

W >= 21

--------------------------------------------------
Final Answer
--------------------------------------------------

Minimum window size required:

W = 21 frames

Correct Option: 21
"""

For x ≥ 0, |x| = x, so f(x) = (x/2 - x)(x - x/2) = (-x/2)(x/2) = -x²/4. For x < 0, |x| = -x, so f(x) = (-x/2 - x)(x + x/2) = (-3x/2)(3x/2) = -9x²/4. Thus f(0) = 0 and f(x) < 0 for x ≠ 0 near the origin, so f has a local maximum at 0 and not a local minimum. Also, f′(x) = -9x/2 for x < 0, f′(0) = 0, and f′(x) = -x/2 for x > 0, hence f′ is continuous at 0. However, the left derivative of f′ at 0 is -9/2 and the right derivative is -1/2, so f′ is not differentiable at 0. Therefore, statements 1, 3, and 4 are true.

A vertex cover S of size k covers all edges in G. If a vertex v is not in S, then all its neighbors must be in S to cover the edges incident to v. This implies that |S| >= deg(v). Since |S| = k, we must have deg(v) <= k for v to potentially be excluded from S. Conversely, if deg(v) > k (or equivalently deg(v) >= k+1), it is impossible for v to be excluded from S because that would require more than k vertices in the cover. Therefore, any vertex with degree greater than k must be included in every minimum vertex cover of size k.

Given:

G(V,E) is a simple undirected weighted graph
with unique edge weights.

--------------------------------------------------
Statement 1
--------------------------------------------------

"In every cycle C of G,
the edge with the largest weight in C
is not in any MST."

This statement is TRUE.

By the Cycle Property of MSTs:

The maximum-weight edge in a cycle
can never belong to a Minimum Spanning Tree.

Since all edge weights are unique,
the largest edge is uniquely determined.

Therefore Statement 1 is TRUE.

--------------------------------------------------
Statement 2
--------------------------------------------------

"In every cycle C of G,
the edge with the smallest weight in C
is in every MST."

This statement is FALSE.

The minimum edge of a cycle is preferred,
but it is not guaranteed to appear
in every MST.

Hence Statement 2 is FALSE.

--------------------------------------------------
Statement 3
--------------------------------------------------

"For every vertex v in V,
the edge with the largest weight incident on v
is not in any MST."

This statement is FALSE.

The largest incident edge may still be required
to connect that vertex to the graph.

Hence Statement 3 is FALSE.

--------------------------------------------------
Statement 4
--------------------------------------------------

"For every vertex v in V,
the edge with the smallest weight incident on v
is in every MST."

This statement is TRUE.

Consider the cut separating vertex v
from all remaining vertices.

The minimum-weight edge incident on v
is the unique lightest edge crossing that cut.

By the Cut Property of MSTs,
this edge must belong to every MST.

Hence Statement 4 is TRUE.

--------------------------------------------------
Final Answer
--------------------------------------------------

Statements 1 and 4 are TRUE.
"""

To determine the true statements, we analyze the balance of terminal symbols 'a' and 'b' in each production rule.

First, consider non-terminal B. The productions are B → aBb | ab. In both cases, the number of 'a's equals the number of 'b's generated directly or recursively. Thus, for any string derived from B, n1 = n2.

Next, analyze non-terminal A. Production 1 (aaBBAb) adds more 'a's than 'b's and includes A recursively. Production 2 (bBabaa) adds more 'a's than 'b's and includes B. Derivation shows that for any string from A, n1 > n2.

Finally, analyze the start symbol S (ab a A B A b b a). It adds more 'a's than 'b's directly and includes two instances of A (where n1 > n2) and one B (n1 = n2). The total count confirms that for any string s in L(G), the number of 'a's is strictly greater than the number of 'b's.

Based on this analysis, the statements corresponding to options 1 and 3 are true.

A TLB hit implies the page table entry is valid and present in memory. A Page Table Miss indicates the virtual address is unmapped, triggering a page fault. Without a valid physical translation from the MMU, the cache cannot be accessed successfully because it requires a physical address. Therefore, a Cache Hit is impossible during a Page Table Miss. Additionally, a valid TLB entry contradicts the condition of a Page Table Miss as they cannot both be true for the same address translation. Thus, sequences combining these events are logically impossible.

Solution

A graph is 2-colorable if adjacent vertices
can be colored using two colors such that
no two adjacent vertices have the same color.

2-colorable graphs are exactly bipartite graphs.

--------------------------------------------------
Statement 1
--------------------------------------------------

"If G is 2-colorable,
then G may contain cycles of odd length"

This is FALSE.

A bipartite graph cannot contain odd cycles.

Hence Statement 1 is FALSE.

--------------------------------------------------
Statement 2
--------------------------------------------------

"If G is 2-colorable,
then G may contain cycles of even length"

This is TRUE.

Example:
A cycle of length 4 is bipartite.

Hence Statement 2 is TRUE.

--------------------------------------------------
Statement 3
--------------------------------------------------

"An optimal algorithm for testing whether
G is 2-colorable runs in time
Theta(|V| + |E|),
if G is represented as an adjacency list"

This is TRUE.

Using BFS or DFS,
we can color the graph while traversing it.

Each vertex and edge is processed once.

Therefore time complexity is:

Theta(|V| + |E|)

--------------------------------------------------
Statement 4
--------------------------------------------------

"An optimal algorithm for testing whether
G is 2-colorable runs in time
Theta(|E| log |V|)"

This is FALSE.

The optimal complexity is linear:

Theta(|V| + |E|)

Hence Statement 4 is FALSE.

--------------------------------------------------
Final Answer
--------------------------------------------------

Statements 2 and 3 are TRUE.
"""

The correct answers are A, B, and C.

Step 1: Determine the Required Block Size

The client requires 6000 IP addresses.

In CIDR, address blocks must contain a power-of-2 number of addresses.

• (2^{12} = 4096) (not sufficient)

• (2^{13} = 8192) (sufficient)

Hence, the client must be allocated a block of 8192 addresses.

Since (8192 = 2^{13}), 13 bits are needed for host addresses.

Therefore, the prefix length is:

32 − 13 = 19

So, the required subnet size is /19.

Step 2: Determine the ISP's Address Range

The ISP owns the block 202.16.0.0/15.

A /15 network covers all addresses from:

202.16.0.0 to 202.17.255.255

All four options lie within this range.

Step 3: Check Valid /19 Network Boundaries

A /19 subnet mask is:

255.255.224.0

Since 224 = 11100000, the third octet increments in blocks of:

256 − 224 = 32

Therefore, valid /19 network addresses must have a third octet equal to:

0, 32, 64, 96, 128, 160, 192, or 224

Step 4: Evaluate Each Option

A. 202.16.0.0/19

• Third octet = 0

• 0 is a valid multiple of 32

Valid

B. 202.17.64.0/19

• Third octet = 64

• 64 is a valid multiple of 32

Valid

C. 202.16.32.0/19

• Third octet = 32

• 32 is a valid multiple of 32

Valid

D. 202.17.24.0/19

• Third octet = 24

• 24 is not a multiple of 32

• Therefore, it is not the starting address of a valid /19 subnet

Invalid

Hence, the correct options are:

A. 202.16.0.0/19

B. 202.17.64.0/19

C. 202.16.32.0/19

D. 202.17.24.0/19

For a path graph on nnn vertices, the number of matchings is:

E[X] = Σ x·Pr(X = x). For values 1, 2, 5, and 7, each probability is 1/6, so their contribution is (1 + 2 + 5 + 7)/6 = 15/6 = 2.50. For values 3, 4, 6, and 8, each probability is 1/12, so their contribution is (3 + 4 + 6 + 8)/12 = 21/12 = 1.75. Therefore, E[X] = 2.50 + 1.75 = 4.25. Rounded to two decimal places, the answer is 4.25.

Solution

Given:

Rotational speed = 15000 rpm
Adjacent track seek time = 1 ms
Tracks accessed in order = 5, 12, 7
Sectors per track = 400
Sector size = 1024 bytes
10 randomly located sectors are accessed per track

--------------------------------------------------
Step 1: Rotation Time
--------------------------------------------------

Time for one complete rotation:

= 60 / 15000 seconds

= 0.004 s

= 4 ms

Average rotational latency:

= 4 / 2

= 2 ms

--------------------------------------------------
Step 2: Seek Time
--------------------------------------------------

Track movement:

0 -> 5 = 5 tracks
5 -> 12 = 7 tracks
12 -> 7 = 5 tracks

Total tracks moved:

= 5 + 7 + 5

= 17 tracks

Since adjacent-track seek time = 1 ms:

Total seek time:

= 17 ms

--------------------------------------------------
Step 3: Rotational Latency
--------------------------------------------------

Total sectors accessed:

= 10 sectors/track × 3 tracks

= 30 sectors

Since sectors are randomly located,
each sector requires average rotational latency.

Average rotational latency per sector:

= 2 ms

Total rotational latency:

= 30 × 2

= 60 ms

--------------------------------------------------
Step 4: Transfer Time
--------------------------------------------------

400 sectors are transferred in one rotation.

One rotation time = 4 ms

Time per sector:

= 4 / 400

= 0.01 ms

For 30 sectors:

= 30 × 0.01

= 0.3 ms

--------------------------------------------------
Final Calculation
--------------------------------------------------

Total time:

= Seek Time + Rotational Latency + Transfer Time

= 17 + 60 + 0.3

= 77.3 ms

--------------------------------------------------
Final Answer
--------------------------------------------------

77.3 ms
"""

The pipeline clock cycle is 1 ns. The EX stage is a shared resource. If an instruction takes t_EX > 1 ns, the EX stage is occupied for multiple cycles, causing structural hazards (stalls) for subsequent instructions.

Number of cycles occupied = ceil(t_EX / 1 ns). Stall cycles per instruction = (Occupied Cycles - 1). We calculate total stalls by summing (M * Stalls) for each instruction type.

• LOAD: ceil(1.8) = 2 cycles -> 1 stall * 15 = 15

• IMUL: ceil(1.5) = 2 cycles -> 1 stall * 10 = 10

• IDIV: ceil(2.5) = 3 cycles -> 2 stalls * 5 = 10

• FADD: ceil(1.7) = 2 cycles -> 1 stall * 10 = 10

• FSUB: ceil(1.7) = 2 cycles -> 1 stall * 5 = 5

• FMUL: ceil(2.8) = 3 cycles -> 2 stalls * 15 = 30

• FDIV: ceil(3.2) = 4 cycles -> 3 stalls * 5 = 15

• Others: ceil(<1.0) = 1 cycle -> 0 stalls * 35 = 0

Total stall cycles = 15 + 10 + 10 + 10 + 5 + 30 + 15 = 95.

First, analyze the function bar(n). It returns the number of times n can be divided by 2 before reaching 1. Mathematically, bar(n) = floor(log2(n)). For example, bar(1)=0, bar(2)=1, bar(4)=2, bar(8)=3.

Next, analyze foo(n). It adds 1 for each recursive step: foo(n) = 1 + foo(bar(n)). We want foo(n) = 5.

This implies foo(bar(n)) = 4, foo(bar(bar(n))) = 3, foo(bar(bar(bar(n)))) = 2, and foo(bar(bar(bar(bar(n))))) = 1.

Since foo(1) = 1, we need bar(bar(bar(bar(n)))) = 1.

Working backwards: bar(x) = 1 for x in [2, 3]. bar(y) = 2 for y in [4, 7]. bar(z) = 3 for z in [8, 15].

Continuing, bar(w) = 4 for w in [16, 31] and bar(w) = 15 for w in [32768, 65535]. So bar(n) must be in [16, 65535].

Finally, bar(n) = 16 for n in [65536, 131071]. The smallest positive integer n is 65536.

Step 1: Reconstruct the Binary Search Tree (BST) using the given preorder traversal: 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77.

Step 2: Identify the root (50). Left subtree contains values < 50: 25, 13, 40, 30, 47. Right subtree contains values > 50: 75, 60, 70, 80, 77.

Step 3: Recursively build subtrees. Left root is 25. Right root is 75. Continue recursively to form the full tree structure.

Step 4: Generate postorder traversal (Left, Right, Root). Sequence: 13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50.

Step 5: Locate element 60 in the sequence. It is at the 7th position.

The correct answer is 4. Trace: 1. P0 (i=0): Forks. Parent (P0) breaks, prints (1). Child (C1) continues. 2. C1 (i=1): Forks. Parent (C1) breaks, prints (2). Child (C2) continues. 3. C2 (i=2): Forks. Parent (C2) breaks, prints (3). Child (C3) continues. 4. C3 (i=3): Loop condition (3 < 3) is false. Loop terminates. C3 prints (4). Total executions: 4.

Step-by-Step Solution

We need to calculate the waiting time for each of the 10 processes using the First Come First Serve (FCFS) scheduling policy. Waiting Time = Start Time - Arrival Time.

Process Timeline Analysis

1. Process A1: Arrives at 10s. Starts at 10s. Burst = 6s. Finishes at 16s. Waiting Time = 10 - 10 = 0s.

2. Process C1: Arrives at 11s. CPU is busy with A1 until 16s. Starts at 16s. Burst = 8s. Finishes at 24s. Waiting Time = 16 - 11 = 5s.

3. Process A2: Arrives at 20s. CPU is busy with C1 until 24s. Starts at 24s. Burst = 6s. Finishes at 30s. Waiting Time = 24 - 20 = 4s.

4. Process C2: Arrives at 22s. CPU is busy with A2 until 30s. Starts at 30s. Burst = 8s. Finishes at 38s. Waiting Time = 30 - 22 = 8s.

5. Process A3: Arrives at 30s. CPU is busy with C2 until 38s. Starts at 38s. Burst = 6s. Finishes at 44s. Waiting Time = 38 - 30 = 8s.

6. Process C3: Arrives at 33s. CPU is busy with A3 until 44s. Starts at 44s. Burst = 8s. Finishes at 52s. Waiting Time = 44 - 33 = 11s.

7. Process A4: Arrives at 40s. CPU is busy with C3 until 52s. Starts at 52s. Burst = 6s. Finishes at 58s. Waiting Time = 52 - 40 = 12s.

8. Process C4: Arrives at 44s. CPU is busy with A4 until 58s. Starts at 58s. Burst = 8s. Finishes at 66s. Waiting Time = 58 - 44 = 14s.

9. Process A5: Arrives at 50s. CPU is busy with C4 until 66s. Starts at 66s. Burst = 6s. Finishes at 72s. Waiting Time = 66 - 50 = 16s.

10. Process C5: Arrives at 55s. CPU is busy with A5 until 72s. Starts at 72s. Burst = 8s. Finishes at 80s. Waiting Time = 72 - 55 = 17s.

Calculation of Average Waiting Time

Sum of Waiting Times = 0 + 5 + 4 + 8 + 8 + 11 + 12 + 14 + 16 + 17 = 95 seconds.

Total number of processes = 10.

Average Waiting Time = Total Waiting Time / Total Processes = 95 / 10 = 9.5 seconds.

The average waiting time is 9.5 seconds.

A superkey is any set of attributes that contains at least one candidate key. The relation R has attributes {A, B, C, D}.

Candidate keys are {A, B} and {A, C}. Superkeys containing {A, B} are formed by adding any subset of remaining attributes {C, D}.

There are 2^2 = 4 such superkeys: {A, B}, {A, B, C}, {A, B, D}, {A, B, C, D}.

Similarly, superkeys containing {A, C} are formed by adding any subset of remaining attributes {B, D}. There are 2^2 = 4 such superkeys.

The intersection contains superkeys with both {A, B} and {A, C}, which means {A, B, C} plus subsets of {D}. There are 2^1 = 2 such superkeys.

Total superkeys = (Superkeys with {A, B}) + (Superkeys with {A, C}) - (Intersection) = 4 + 4 - 2 = 6.

Answer: 6

Given that L₂ is a regular language and the intersection L₁ ∩ L₂ is also regular.

Since every regular language is a context-free language, the intersection L₁ ∩ L₂ must be context-free. Therefore, the statement asserting that L₁ ∩ L₂ is context-free (Option C) is always true.

To verify why other options are not always true, consider the counter-example where L₂ = ∅ (the empty set). The empty set is regular. In this case, L₁ ∩ L₂ = ∅, which satisfies the condition regardless of what L₁ is. This means L₁ does not have to be regular or context-free, disproving options claiming constraints on L₁. Similarly, the union L₁ ∪ L₂ = L₁ in this case, so it is not necessarily regular.

In Depth-First Search (DFS), the discovery time $d[v]$ and finishing time $f[v]$ for any vertex $v$ satisfy $d[v] < f[v]$. The relationship between intervals $[d[u], f[u]]$ and $[d[v], f[v]]$ for any two vertices is governed by the Parenthesis Theorem: the intervals are either disjoint or one is contained within the other.

Analysis of Edge Types

For an edge $(u, v) \in E$ in a DAG:

• Tree/Forward Edge: $v$ is a descendant of $u$. Interval of $v$ is inside $u$. Order: $d[u] < d[v] < f[v] < f[u]$. (Option A is possible)

• Back Edge: $u$ is a descendant of $v$. This implies a cycle. Order: $d[v] < d[u] < f[u] < f[v]$. (Option B is impossible in a DAG)

• Cross Edge: $u$ and $v$ are in different subtrees. Intervals are disjoint. Order: $d[v] < f[v] < d[u] < f[u]$ (if $v$ finished first). (Option C is possible)

Why Option D is Impossible

Option D suggests $d[u] < d[v] < f[u] < f[v]$. This implies that the interval $[d[u], f[u]]$ partially overlaps with $[d[v], f[v]]$. The Parenthesis Theorem states that DFS intervals cannot partially overlap; they must be either completely disjoint or completely nested. Therefore, this ordering is structurally impossible in any DFS traversal.

Thus, the options that will NEVER be correct are B and D.

Construct a K-map for F(P,Q,R,S) with minterms 1, 2, 3, 4, 5, 7, 10, 12, 13, 14.

Identify Prime Implicants (PIs):

- Group 1: m1, m3, m5, m7 -> Term: P'S

- Group 2: m4, m5, m12, m13 -> Term: Q\bar{R}

- Remaining minterms to cover: 2, 10, 14.

- Cover m2: Use PI \bar{P}\bar{Q}R (covers 2,3).

- Cover m10, m14: Use PI PR\bar{S} (covers 10,14).

The minimal SOP is P'S + Q\bar{R} + \bar{P}\bar{Q}R + PR\bar{S}, which matches Option 1.

To find the equivalent relational algebra expression, we analyze the Tuple Relational Calculus (TRC) expression:

E = { ⟨u⟩ | ∃v ∃w (⟨u, v⟩ ∈ R ∧ ⟨v, w⟩ ∈ S) }

1. Identify Attributes: Relation R has attributes (P, Q) and S has attributes (X, Y).

2. Map Variables: The tuple ⟨u, v⟩ ∈ R implies u corresponds to P and v corresponds to Q. The tuple ⟨v, w⟩ ∈ S implies v corresponds to X and w corresponds to Y.

3. Determine Join Condition: The variable v is common to both relations. Thus, the join condition is R.Q = S.X.

4. Determine Projection: The result is projected on u, which corresponds to attribute P of relation R.

5. Construct Expression: The equivalent expression is Π_P (S ⋈_{S.X=R.Q} R) or Π_P (R ⋈_{R.Q=S.X} S).

Option B matches this structure: Π_P (S ⋈_{S.X=R.Q} R).

Analysis of Redundant Expressions

A redundant expression (or common subexpression) in a basic block is one that has been computed previously along all paths leading to the current point, and the operands have not been modified since that computation.

1. Analysis of Basic Block B4

Predecessors of B4 are B2 and B3.

• Expression g*k: Computed in B2 (a = g*k) and B3 (t = g*k). Neither block modifies g or k. Thus, g*k is available at the entry of B4.

• Expression b+i: Computed in B1. However, in path B1 -> B3 -> B4, the variable b is modified in B3 (b = c+m). Thus, b+i is not available along all paths.

Conclusion for B4: The only redundant expression is { g*k }.

2. Analysis of Basic Block B5

Predecessor of B5 is B4.

Expression c+m: Computed in B3 (b = c+m). However, it is not computed in B2. Since it is not available along the path through B2, it is not redundant in B5.

Conclusion for B5: No redundant expressions { }.

Final Answer

B4: { g*k }, B5: { }

The correct option is B. By analyzing the state table for the 2-bit saturating up/down counter: For D1 (Q1+), the minterms are 1, 2, 3, 7. Simplifying yields D1 = P'Q1 + P'Q0 + Q1Q0. For D0 (Q0+), the minterms are 0, 2, 3, 6, 7. Simplifying yields D0 = Q1 + P'Q0'. Option B matches these derived expressions.

1. In main(), i = 9 and j = 10. func(9, 10) is called.

2. Inside func(), parameter i = 9, j = 10.

3. if (9 < 10) is true. int i = 0 declares a new local variable i, shadowing the parameter i.

4. The while loop modifies the new local i and parameter j. Parameter i remains 9.

5. After the if block, the new local i is out of scope. printf prints the parameter i, which is 9.

For x ≤ 0, f(x) = 3, so f(0) = 3 and the left-hand limit at 0 is 3. For x > 0, f(x) = c₁eˣ - c₂ ln(1/x). As x → 0+, ln(1/x) → ∞. For the right-hand limit to be finite, we must have c₂ = 0. Then the right-hand limit becomes c₁e⁰ = c₁. Continuity at x = 0 requires c₁ = 3. Hence c₁ + c₂ = 3 + 0 = 3.

Given F(P, Q) = (P' + Q) ⊕ (P'Q). Using the definition A ⊕ B = AB' + A'B, we substitute A = (P' + Q) and B = P'Q.

The expression becomes (P' + Q)(P'Q)' + (P' + Q)'(P'Q). Applying De Morgan's laws: (P'Q)' = P + Q' and (P' + Q)' = PQ'. Substituting these back, we get F = (P' + Q)(P + Q') + PQ'(P'Q).

The second term simplifies to 0 because P'P = 0. Expanding the first term: P'P + P'Q' + QP + QQ'. Since P'P = 0 and QQ' = 0, this simplifies to P'Q' + PQ.

This expression represents the XNOR operation (P ⊙ Q). Thus, F is equivalent to (P ⊕ Q)' and also P' ⊕ Q.

Given:

F(P,Q) = (P' + Q) xor (P'Q)

Using XOR identity:

A xor B = AB' + A'B

Let A = (P' + Q) and B = (P'Q).

F = (P' + Q)(P'Q)' + (P' + Q)'(P'Q)

Now,

(P'Q)' = P + Q'

(P' + Q)' = PQ'

So,

F = (P' + Q)(P + Q') + (PQ')(P'Q)

Expand the first term:

(P' + Q)(P + Q') = P'P + P'Q' + PQ + QQ'

Since P'P = 0 and QQ' = 0, this becomes:

P'Q' + PQ

The second term is:

(PQ')(P'Q) = PP'QQ' = 0

Therefore,

F = P'Q' + PQ

This is XNOR. Hence:

(P xor Q)' = P'Q' + PQ

Also,

P' xor Q = P'Q' + PQ

P xor Q' = PQ + P'Q'

Thus, the equivalent expressions are options A, C, and D.

Final Answer: A, C and D.

The array A = [10, 7, 8, 19, 41, 35, 25, 31] has n=8 elements. Merge sort performs n-1 = 7 merge operations.

Level 1 Merges (4 operations):

1. Merge [10] and [7]: 10 > 7, not void. 2. Merge [8] and [19]: 8 < 19, void. 3. Merge [41] and [35]: 41 > 35, not void. 4. Merge [25] and [31]: 25 < 31, void.

Level 2 Merges (2 operations):

5. Merge [7, 10] and [8, 19]: max(10) > min(8), not void. 6. Merge [35, 41] and [25, 31]: max(41) > min(25), not void.

Level 3 Merge (1 operation):

7. Merge [7, 8, 10, 19] and [25, 31, 35, 41]: max(19) < min(25), void.

Total void merge operations = 3.

SOLUTION:

OPTION A) TRUE. The grammar is ambiguous.

A grammar is ambiguous if and only if there exists at least one string in L(G) for which the grammar produces more than one parse tree.

String abb ∈ L(G) and G produces more than one parse tree for abb:

OPTION B) TRUE. The string abb has two distinct derivations in this grammar.

1st derivation:

S ⇒ aSbS
⇒ abS
⇒ abbS
⇒ abb

2nd derivation:

S ⇒ aSbS
⇒ abSbS
⇒ abbS
⇒ abb

Note that the question is not asking for rightmost (or leftmost) derivations. It is just asking about derivations. There are more than 2 derivations of the string abb, but the question is asking for the existence of at least two derivations.

OPTION C) TRUE. The string abab has only one rightmost derivation.

S ⇒rmd aSbS
⇒rmd aSbaSbS
⇒rmd aSbaSb
⇒rmd aSbab
⇒rmd abab

At each step, the next terminal forces a unique production choice, so no alternative rightmost derivation exists.

This fact can also be seen using the parse tree. There is only 1 parse tree that yields the string abab. Therefore, only 1 rightmost derivation exists. For any CFG, the number of rightmost derivations is the same as the number of parse trees for a given string.

OPTION D) False. The language generated by the grammar is undecidable.

This is incorrect. The given grammar is a context-free grammar (CFG), and every language generated by a CFG is a context-free language. Membership testing for context-free languages is decidable.

Therefore, the language generated by the grammar is decidable, not undecidable.

For x ≤ 0, f(x) = 3, so f(0) = 3 and the left-hand limit at 0 is 3. For x > 0, f(x) = c₁eˣ - c₂ ln(1/x). As x → 0+, ln(1/x) → ∞. For the right-hand limit to be finite, c₂ must be 0. Then the right-hand limit becomes c₁e⁰ = c₁. Continuity at x = 0 requires c₁ = 3. Therefore c₁ + c₂ = 3 + 0 = 3.

Both grammars generate declarations of the form type followed by one or more identifiers.

Statement A is true. In G1, D → T V and V → V₁ id | id generate one or more identifiers after a type. In G2, D → D₁ id | T id generates the same strings by left recursion. Hence P = Q.

Statement B is true. In SDD2, every type attribute is synthesized: T.type is set from the terminal int/float, and D.type is computed from T.type or D₁.type. No inherited attribute is used, so SDD2 is S-attributed.

Statement C is false. SDD1 is L-attributed because the inherited attribute V.type is passed to V₁.type in a left-to-right manner. However, it does not contain only inherited attributes; T.type and D.type are synthesized attributes.

Statement D is true. In both SDDs, each identifier receives the type computed from the declaration, so the same put(id.entry, type) entries are added to the symbol table.

Therefore, the correct options are A, B, and D.

Inorder traversal (I) visits the left subtree, then the node, and finally the right subtree, which corresponds to sequence L. Preorder traversal (II) visits the node first, followed by left and right subtrees, matching sequence M. Postorder traversal (III) visits the left subtree, then the right subtree, and ends with the node, matching sequence N. Therefore, the correct pairing is I-L, II-M, and III-N.