GATE 2023 CSE Question Paper With Detailed Solutions

Other options don’t fit well grammatically or contextually:
– “Near” is usually used as a preposition or adjective, not an adverb.
– “Utterly” and “mostly” indicate degree or extent, not proximity or probability.

We can compute backwards using the recurrence relation:
\[
F_5 = F_7 – F_6 = 60 – 37 = 23 \\
F_4 = F_6 – F_5 = 37 – 23 = 14 \\
F_3 = F_5 – F_4 = 23 – 14 = 9 \\
F_2 = F_4 – F_3 = 14 – 9 = 5 \\
F_1 = F_3 – F_2 = 9 – 5 = 4
\]

Hence, \( F_1 = 4 \).

So, 60% of 90% = 54% of total women received care from doctors.

Hence, more than half of the pregnant women received medical care at least once from a doctor.
Thus, Option (A) is correct.

Therefore, the surface may be concave in some places and convex in others.
Hence, Option (C) is correct.

However, there is no evidence in the passage to suggest that all workers will cycle (Option A), or that cycling guarantees full health (Option B), or that the government was instructed to mandate it (Option C).

Hence, the only certain and logical inference is Option (D).

To analyze the statements:
Let us compare both functions:
– Initially, for small values of \( t \), the linear function \( g(t) \) grows faster than the quadratic \( f(t) \).
– But as \( t \) becomes large, \( f(t) \) grows faster and overtakes \( g(t) \).

To find the intersection point, set:
\( f(t) = g(t) \Rightarrow 0.01t^2 = 4t \)
\(\Rightarrow t(0.01t – 4) = 0 \Rightarrow t = 0 \text{ or } t = 400 \)

So,
(i) For \( 0 < t < 400 \), \( g(t) > f(t) \) → TRUE
(ii) For \( t > 400 \), \( f(t) > g(t) \) → TRUE

Hence, both statements are correct.

(iii) Mina buys groceries, so her bags are heavy.
(ii) She starts climbing the stairs and begins to pant.
(i) She reaches the terrace and notices the man.
(iv) He was already there, watching traffic.

This sequence (iii → ii → i → iv) forms a coherent narrative of her journey and setting.

But \( f \) is only in terms of \( x \) and \( g \) only in terms of \( y \).
So for these two to be equal for all values of \( x \) and \( y \), they must both be equal to some constant.

Let the constant be \( c \). Then,
\( f(x) = c \) and \( g(y) = c \)

Hence, both functions are constant.

Step-by-step transformation:

From P to Q
Observe that the star figure rotates 90° in the clockwise direction.
This is a rotation about an axis perpendicular to the plane (i.e., “into the screen”) → Operation 1 is a clockwise rotation by 90°.

From Q to R
Now, look at the flipped orientation. The top tip of the star in Q becomes the bottom tip in R.
This is a reflection along a horizontal line, i.e., a mirror placed horizontally below the image.

Hence:

– Operation 1 = Clockwise 90° rotation
– Operation 2 = Horizontal reflection

✅ This matches Option A.

S1 is TRUE:
The front-end of a compiler (which includes lexical analysis, syntax analysis, and semantic analysis) is largely independent of the target machine. It deals primarily with the source code.

S2 is TRUE:
The back-end (which includes code generation and optimization) deals with translating intermediate code into machine-specific code, making it hardware dependent.

S3 is FALSE:
The programming language dependence is typically resolved in the front-end. Once source code is converted into intermediate representation, it becomes language-independent. Hence, this is not a part of the back-end.

So, the correct combination is:
Only S1 and S2 are TRUE, which matches option (B).

– Left child of node at index `i`: `2i`
– Right child of node at index `i`: `2i + 1`

Let’s verify option (B):
23 (index 1)
→ children: 17 (index 2), 14 (index 3) — OK
17 (index 2)
→ children: 7 (index 4), 13 (index 5) — OK
14 (index 3)
→ children: 10 (index 6), 1 (index 7) — OK
7 (index 4)
→ children: 5 (index 8), 6 (index 9) — OK
13 (index 5)
→ child: 12 (index 10) — OK

Every node is greater than or equal to its children.
Hence, the array forms a valid max-heap.

Other options violate the max-heap property in one or more places.
So, the correct answer is (B).

In contrast, a doubly linked list allows traversal in both directions. If we are given a pointer to the node we want to delete, we can access both the next and previous nodes directly. This allows us to update the links and delete the node in constant time, i.e., O(1).

Hence,
– `SLLdel` is O(n)
– `DLLdel` is O(1)

Therefore, the correct option is (D).

– From state s, on input `1`, it transitions to p (which is an accepting/final state).
– From p, two transitions are allowed:
– On `0`, it goes to q
– On `1`, it loops back to p
– From q, on `1` it goes back to p`, creating a loop structure.
– On `0` from q, it moves to a dead state r, which leads to self-loops for both 0 and 1.

The key transitions that keep the DFA in accepting states revolve around reading a 1 followed by any number of:
– `0` followed by `1` (i.e., the string 01),
– or just 1s directly (from p looping on itself).

Hence, the pattern becomes:
– Start with `1` (to reach accepting state `p`)
– Followed by any number of (0 + 11), which keeps the DFA in the accepting loop

So the correct regular expression is: 1(0 + 11)\
Therefore, the correct answer is (C).

The closed-form expression (also called the Binet formula) for the Lucas numbers is:
\[
L_n = \left( \frac{1 + \sqrt{5}}{2} \right)^n + \left( \frac{1 – \sqrt{5}}{2} \right)^n
\]

This resembles the Fibonacci Binet formula but with a plus sign between the terms instead of minus, which matches option (A).

Hence, the correct answer is (A).

– The degree (or arity) of a relation refers to the number of attributes (or columns) in its schema.
– The cardinality refers to the number of tuples (or rows) present in the relation.

Hence, among the given options:
– Option (A) correctly refers to the degree of the relation.
– Options (B) and (C) refer to the amount of data (not schema structure).
– Option (D) is incorrect because domains define data types, not quantity of attributes.

Therefore, the correct answer is (A).

\[
U = \frac{T_{\text{transmission}}}{T_{\text{transmission}} + 2 \times T_{\text{propagation}}}
\]

Where:
– \( T_{\text{transmission}} = \frac{\text{Frame size}}{\text{Transmission rate}} \)
– \( T_{\text{propagation}} = \frac{\text{Link length}}{\text{Propagation speed}} \)

From the formula:
i. A longer link length increases propagation delay.
ii. A lower transmission rate increases the time to send the data.
Both factors cause greater idle time, resulting in lower utilization.

Hence, Option (A) with both longer link and lower rate leads to the lowest link utilization.

Matrix \( B \) is formed by rearranging the rows of matrix \( A \). Specifically, \( B \) is obtained by swapping the first and third rows of \( A \).
A single row swap in a square matrix negates the determinant:

\[
\text{det}(B) = -\text{det}(A)
\]

Thus, the correct relationship is:
\[
\text{det}(B) = -\text{det}(A)
\]

Hence, Option (B) is true.

\[
\text{id} \rightarrow \text{letter} \, (\text{letter} \mid \text{digit})^{*}
\]

This means the string must start with a letter, followed by zero or more letters or digits. Option (C) is the only automaton that:

i. Starts with a transition on `letter`
ii. Loops on both `letter` and `digit` through \( \varepsilon \)-transitions to allow repetition
iii. Properly includes the Kleene star behavior “ through non-deterministic paths
iv. Ends in a final state reachable after the initial `letter` and any sequence of `letter` or `digit`

Thus, Option (C) correctly accepts all valid identifiers as per the given definition.

The key advantage of universal hashing is that it provides a theoretical guarantee that the expected number of collisions for any key is low, no matter how maliciously the keys are chosen.

Hence, Option (C) is the most secure and effective strategy in adversarial scenarios.

This behavior matches that of a D Latch, which stores the input data when the enable (or control) signal is high, and holds its state otherwise. A D latch is a level-sensitive device, and the MUX configuration here mirrors that functionality exactly.

Therefore, the correct answer is (B) D Latch.

However, each thread has its own stack, program counter, and general-purpose registers, which represent the thread’s current state of execution. These must be saved and restored during a context switch.

i. Stack Pointer (B) – must be saved as it points to the top of the thread’s current stack frame.
ii. Program Counter (C) – indicates the address of the next instruction to be executed for the thread.
iii. General Purpose Registers (D) – these hold intermediate data and must be preserved.

Hence, the correct answer is options (B), (C), and (D).

i. Function Call (A) – This happens entirely in user space and does not require a mode switch.
ii. `malloc` Call (B) – `malloc` may or may not cause a transition. It is a library call in user space; although internally it may request more memory (e.g., via `brk()` or `mmap()` system calls), this is not guaranteed for every call. Hence, not a guaranteed transition.
iii. Page Fault (C) – A page fault is an exception handled by the operating system, and this definitely causes a transition to kernel mode to resolve the fault.
iv. System Call (D) – A system call explicitly requests a service from the kernel, and this always triggers a transition to kernel mode.

Therefore, the correct options are (C) and (D).

ii. Option (B):
Context-free languages are not closed under intersection. A classic counterexample is:
Let
L₁ = { aⁿbⁿcᵐ | n, m ≥ 0 }
L₂ = { aᵐbⁿcⁿ | n, m ≥ 0 }
Both are context-free, but their intersection
L₁ ∩ L₂ = { aⁿbⁿcⁿ | n ≥ 0 },
which is not context-free.
❌ Incorrect.

iii. Option (C):
Recursive (decidable) languages are closed under intersection.
✔️ Correct.

iv. Option (D):
Recursively enumerable (RE) languages are also closed under intersection.
✔️ Correct.

Therefore, the correct options are (A), (C), and (D).

i. Option (A):
Incorrect. OSPF does not use the Bellman-Ford algorithm. It uses Dijkstra’s algorithm (link-state routing) to compute shortest paths.
❌ Incorrect.

ii. Option (B):
Correct. OSPF is a link-state routing protocol and it uses Dijkstra’s shortest path algorithm to determine least-cost paths.
✅ Correct.

iii. Option (C):
Incorrect. OSPF is an intra-domain (interior gateway) routing protocol. It is not used between domains (which is the role of BGP).
❌ Incorrect.

iv. Option (D):
Correct. OSPF supports hierarchical routing by dividing an autonomous system into areas to optimize routing and reduce overhead.
✅ Correct.

Hence, the incorrect statements are (A) and (C).

The given conjecture is:
\[ \forall x (P(x) \Rightarrow \exists y \, Q(x, y)) \] This means: “For every \( x \), if \( P(x) \) is true, then there exists a \( y \) such that \( Q(x, y) \) is true.”

Let’s evaluate the options:

(A) \( \exists x (P(x) \land \forall y \, Q(x, y)) \)
This only asserts the statement for some \( x \), not all \( x \). So it does not imply the conjecture.
❌ Not correct.

(B) \( \forall x \forall y \, Q(x, y) \)
If \( Q(x, y) \) is true for all \( x, y \), then for any \( x \) with \( P(x) \), we can choose any \( y \), and \( Q(x, y) \) will be true. So the implication definitely holds.
✅ Correct.

(C) \( \exists y \forall x (P(x) \Rightarrow Q(x, y)) \)
This implies that for a specific \( y \), the implication holds for all \( x \). So the existential quantifier is fixed for all \( x \), which implies the original statement.
✅ Correct.

(D) \( \exists x (P(x) \land \exists y \, Q(x, y)) \)
This only guarantees the condition for some \( x \), not all \( x \). So it does not imply the conjecture.
❌ Not correct.

Final Answer: (B) and (C).

Let’s analyze each scheduling algorithm for the possibility of starvation (a situation where a process waits indefinitely to be scheduled):

(A) First-in First-Out (FIFO):
FIFO processes are scheduled in the order they arrive. No starvation occurs since every process eventually gets the CPU.
❌ Not correct.

(B) Round Robin:
Each process gets a fixed time slice in a cyclic manner. Every process is guaranteed CPU time, so starvation is not possible.
❌ Not correct.

(C) Priority Scheduling:
Processes with lower priority can be indefinitely delayed if higher-priority processes keep arriving. This can lead to starvation.
✅ Correct.

(D) Shortest Job First (SJF):
SJF favors short jobs. A long job may be delayed indefinitely if shorter jobs keep arriving. This also leads to starvation in many cases.
✅ Correct.

Final Answer: (C) and (D).

We are given a cubic function:

\[
f(x) = x^3 + 15x^2 – 33x – 36
\]

To find local extrema, we first compute the first derivative:

\[
f'(x) = 3x^2 + 30x – 33
\]

Set the derivative equal to zero to find critical points:

\[
3x^2 + 30x – 33 = 0 \Rightarrow x^2 + 10x – 11 = 0
\]

Solving this:

\[
x = \frac{-10 \pm \sqrt{100 + 44}}{2} = \frac{-10 \pm \sqrt{144}}{2} = \frac{-10 \pm 12}{2}
\Rightarrow x = 1, -11
\]

Now, use the second derivative test:

\[
f”(x) = 6x + 30
\]

Evaluate at critical points:

– \( f”(1) = 6(1) + 30 = 36 > 0 \Rightarrow \) local minimum
– \( f”(-11) = 6(-11) + 30 = -66 + 30 = -36 < 0 \Rightarrow \) local maximum

So, the function has both a local maximum and a local minimum.

Correct statements:
✅ (B) \( f(x) \) has a local maximum
✅ (D) \( f(x) \) has a local minimum

We are given:
\( f(n) = n \)
\( g(n) = n^2 \)

We will evaluate each asymptotic relationship:

(A) \( f \in O(g) \)
To check if \( f(n) \in O(g(n)) \), we need:
\[
\exists c > 0, \exists n_0 \text{ such that } f(n) \leq c \cdot g(n) \text{ for all } n \geq n_0
\] Here,
\[
n \leq c \cdot n^2 \Rightarrow \frac{1}{n} \leq c
\] This is true for \( c = 1 \) and \( n \geq 1 \). So, True

(B) \( f \in \Omega(g) \)
We need:
\[
f(n) \geq c \cdot g(n) \Rightarrow n \geq c \cdot n^2 \Rightarrow \frac{1}{n} \geq c
\] This fails as \( \frac{1}{n} \to 0 \). So, False

(C) \( f \in o(g) \)
To check \( f(n) \in o(g(n)) \), we evaluate:
\[
\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{n}{n^2} = \lim_{n \to \infty} \frac{1}{n} = 0
\] So, \( f(n) \in o(g(n)) \) is True

(D) \( f \in \Theta(g) \)
This would mean \( f(n) \in O(g(n)) \) and \( f(n) \in \Omega(g(n)) \). Since \( f(n) \notin \Omega(g(n)) \), this is False

Final Answer: ✅ (A), ✅ (C)

To solve this, we recall a key property of adjacency matrices:

The sum of the eigenvalues of an adjacency matrix is equal to the trace of the matrix, which is the sum of the diagonal elements.

In an adjacency matrix:
– Each diagonal entry \( A_{ii} \) represents a self-loop at node \( i \).
– From the graph, we observe self-loops at vertex 3 and vertex 4.

So the trace of matrix \( A \) is:
\[
\text{Trace}(A) = A_{33} + A_{44} = 1 + 1 = 2
\]

Therefore, the sum of eigenvalues is:
\[
\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_5 = 2
\]

We evaluate the triple integral step-by-step:

\[
\int_{-3}^{3} \int_{-2}^{2} \int_{-1}^{1} (4x^2 y – z^3) \, dz \, dy \, dx
\]

Step 1: Integrate with respect to \( z \)

\[
\int_{-1}^{1} (4x^2 y – z^3) \, dz = \int_{-1}^{1} 4x^2 y \, dz – \int_{-1}^{1} z^3 \, dz
\]

– \( \int_{-1}^{1} 4x^2 y \, dz = 4x^2 y \cdot (1 – (-1)) = 4x^2 y \cdot 2 = 8x^2 y \)
– \( \int_{-1}^{1} z^3 \, dz = 0 \), since \( z^3 \) is an odd function integrated over a symmetric interval.

So the inner integral becomes:
\[
\int_{-1}^{1} (4x^2 y – z^3) \, dz = 8x^2 y
\]

Step 2: Integrate with respect to \( y \)

\[
\int_{-2}^{2} 8x^2 y \, dy = 8x^2 \int_{-2}^{2} y \, dy = 8x^2 \cdot 0 = 0
\]

Again, \( y \) is an odd function over symmetric limits, so this evaluates to 0.

Since this whole part is now 0, the final integration over \( x \) becomes:

\[
\int_{-3}^{3} 0 \, dx = 0
\]

Final Answer:
\[
\boxed{0}
\]

We are given a number in radix-4 (base-4):
\[
(132)_4
\]

Step 1: Convert to decimal (base-10)

Each digit is multiplied by its positional value in base 4:

\[
1 \cdot 4^2 + 3 \cdot 4^1 + 2 \cdot 4^0 = 1 \cdot 16 + 3 \cdot 4 + 2 \cdot 1 = 16 + 12 + 2 = 30
\]

So, \( (132)_4 = (30)_{10} \)

Step 2: Convert decimal to base-5

Now convert 30 to radix-5 by successive division:

\[
30 \div 5 = 6 \text{ remainder } 0 \\
6 \div 5 = 1 \text{ remainder } 1 \\
1 \div 5 = 0 \text{ remainder } 1
\]

Reading the remainders from bottom to top, we get:

\[
(30)_{10} = (110)_5
\]

Final Answer:
\[
\boxed{110}
\]

We are given:

– Stage 1 delay = 10 ns
– Stage 2 delay = 20 ns
– Stage 3 delay = 14 ns

In a pipelined processor, the clock cycle time is determined by the slowest pipeline stage.
So,
\[
\text{Cycle time} = \max(10, 20, 14) = 20 \text{ ns}
\]

For a pipelined processor:

– The first instruction takes 3 cycles to complete (pipeline fill time).
– Each subsequent instruction completes in 1 cycle (due to pipelining).

So, total time for executing \( n \) instructions in a \( k \)-stage pipeline is:

\[
T = (\text{pipeline depth} – 1 + n) \times \text{cycle time}
\]

Here,
Pipeline depth \( k = 3 \)
Number of instructions \( n = 100 \)
Cycle time = 20 ns

\[
T = (3 – 1 + 100) \times 20 = 102 \times 20 = 2040 \text{ ns}
\]

Final Answer:
\[
\boxed{2040}
\]

Polling-based implementation:

– The system polls every 10 ms = 100 times per second
– Each poll consumes 100 µs
– Total time for polling in 1 second:
\[
100 \text{ polls} \times 100 \, \mu\text{s} = 10000 \, \mu\text{s} = 0.01 \text{ sec}
\] – One keystroke per second also takes 200 µs extra for processing
\[
200 \, \mu\text{s} = 0.0002 \text{ sec}
\] – So,
\[
T_1 = 0.01 + 0.0002 = 0.0102 \text{ sec}
\]

Interrupt-based implementation:

– One keystroke per second
– Each keystroke requires 1 ms = 0.001 sec

So,
\[
T_2 = 0.001 \text{ sec}
\]

Final ratio:
\[
\frac{T_1}{T_2} = \frac{0.0102}{0.001} = 10.2
\]

Answer:
\[
\boxed{10.2}
\]

#include &lt;stdio.h&gt;

int funcp(){
static int x = 1;
x++;
return x;
}

int main(){
int x, y;
x = funcp(); // First call: static x = 1 → x++ → returns 2
y = funcp() + x; // Second call: static x = 2 → x++ → returns 3 + x = 2 → y = 5
printf(“%d\n”, (x + y)); // x = 2, y = 5 → prints 7
return 0;
}

Explanation:

i. First call to `funcp()`:
– static `x = 1`
– after `x++`, it becomes 2
– returns 2 → stored in `x`

ii. Second call to `funcp()`:
– static `x = 2`
– after `x++`, it becomes 3
– returns 3 → added to previous `x = 2` → y = 5

iii. Finally, `x + y = 2 + 5 = 7` is printed.

Explanation:

Let’s track each function call:

1. main() calls f1(), which executes and returns 1
2. Then main() calls f2(2)
– Inside f2(2), f3() is called
– Since 2 is not equal to 1, it makes a recursive call to f2(1)
– Inside f2(1), f3() is again called
– This time, since 1 equals 1, f1() is called and returned
3. Finally, main() calls f3() again

So the activation (function call) tree looks like this:

main
├── f1
├── f2
│ ├── f3
│ └── f2
│ ├── f3
│ └── f1
└── f3

This structure matches the diagram in Option (A).

This is a problem on liveness analysis.

Let’s analyze each basic block by examining which variables are used in the future (live) before they are redefined:

– B4: `i = a + 1`
`a` is used here, and `i` is assigned.
Since B4 is the last block before `EXIT`, variables live at `EXIT` must be determined by backtracking.
Variables that are still used after B4 are `{a, i, j}` due to loop-back.

– B3: `a = 20`
`a` is redefined, but not used inside. However, control flows to B2 again where `a` is needed for B4.
Also, `j` is used in B2, hence both `a` and `j` are live.

– B2: `i = i + 1; j = j – 1`
`i` and `j` are used and reassigned. `a` is needed after B2 in both B3 and B4.
So live variables at exit of B2: `{a, j}`

– B1: Initializes `i`, `j`, and `a`. Since all are used in B2 and later blocks, all three are live: `{a, i, j}`

Hence,
B1: {a, i, j}
B2: {a, j}
B3: {a, j}
B4: {a, i, j}

Option (D) is correct.

### Given:
– Initial value of `X` = 10
– 5 `incr` threads → each does `X = X + 1`
– 3 `decr` threads → each does `X = X – 1`

Net effect without synchronization = `X = 10 + 5 – 3 = 12` if all updates execute safely.

Let’s examine each case:

#### Case I-1 (Binary Semaphore `s = 1`):
– Only one thread accesses the critical section at a time.
– So, all 5 increments and all 3 decrements execute mutually exclusively.
– Final value of `X` is guaranteed to be `10 + 5 – 3 = 12`.

So, V1 = 12 (safe execution due to serialization via binary semaphore).

#### Case I-2 (Counting Semaphore `s = 2`):
– At most 2 threads can be in the critical section concurrently.
– This allows two threads to modify `X` at the same time, possibly creating race conditions.
– If two `decr` threads access `X` simultaneously, the value might be read as 10 by both, and then both write back `X = 9`.
– This causes lost updates.
– In the worst case, we could lose up to 2 increments, resulting in final value:
`X = 10 + (5 – lost_increments) – 3 = 10 + 3 – 3 = 10`

But since the worst case minimum is asked, and race conditions could lead to some updates being completely lost (including increments and decrements), minimum value could go down to 7, if all 3 decrements succeed and only 0 effective increments (worst case).

So V2 = 7

Hence,
Minimum possible values: V1 = 12, V2 = 7

Answer: Option (C)

Let us analyze each option:

– Option A: \( (a + b)^* \) is the set of all strings over {a, b}. Too general.
– Option B: \( a (a + b)^* b^* \) generates strings that start with a, followed by any mix of a and b, and then any number of trailing b’s.
– Option C: \( a^* b^* (a + b) \) ends with a single a or b, not a general construction.
– Option D: Regular expressions define regular languages, so unless given context otherwise, the grammar should be regular.

Hence, Option (B) matches the pattern typically described by such a grammar.

Hence, the number of b’s must be less than the number of a’s to leave extra A’s for the `q` state to pop and empty the stack. Also, at least one a is required to start the process.

So the language is:
{ a^m b^n | 1 ≤ m and n < m }

Multiplying b[i] by 8 is equivalent to left shifting it by 3.
So, U1 = 3.

Each int is 4 bytes, so to move from a[i] to a[i+1] and b[i] to b[i+1], we need to increment the pointers by 4.
So, U2 = 4 and U3 = 4.

The loop starts at L01, so the jump at the end of the loop (L08) should go back to L01.
So, U4 = L01.

Therefore, the correct tuple is (3, 4, 4, L01).

The system uses 12-bit addresses (IA11 to IA0), and out of these, only IA4 and IA3 go into the decoder to select the appropriate chip.
That means the decoder distinguishes 4 chips using these 2 bits (IA4, IA3), with combinations:
00 → Chip 0 (X1)
01 → Chip 1 (X2)
10 → Chip 2 (X3)
11 → Chip 3 (X4)

The rest of the address lines (IA2–IA0) are still connected to the address lines of memory directly. Since the memory is byte-addressable, these lower bits influence the internal addressing.

Now, in the address, the bits IA2–IA0 directly select the memory location offset in each chip.
So when Addr = 0 (internal location 0 of each chip), IA2–IA0 = 000.
Hence, the full input address at which each chip gets selected for Addr = 0 will be:
X1 → IA4, IA3 = 00 → 0000 0000 0000₂ = 0
X2 → IA4, IA3 = 01 → 0000 0000 1000₂ = 8
X3 → IA4, IA3 = 10 → 0000 0001 0000₂ = 16
X4 → IA4, IA3 = 11 → 0000 0001 1000₂ = 24

So the correct answer is (0, 8, 16, 24).

– Q1 is the output of a T flip-flop
– Q2 is the output of a D flip-flop
– Q3 is the output of another T flip-flop

The feedback from Q3 (after NOT gate) is connected to the T input of the first T flip-flop (Q1).
So the T input of Q1 is driven by NOT(Q3).
Q2 is a D flip-flop that captures the value of Q1.
Q3 is a T flip-flop driven by Q2.

On each clock cycle:
– Q1 toggles if T = 1, i.e., if Q3 = 0 (because input to Q1 is NOT(Q3))
– Q2 = Q1
– Q3 toggles if Q2 = 1

Now evaluate the state (Q1, Q2, Q3) = (0, 0, 1):
– Q2 = 0 implies previous Q1 = 0
– Q3 = 1 implies previous Q2 = 1 (which contradicts Q2 = 0)
Hence, this combination is NOT possible.

So, (0, 0, 1) is a state that can NEVER be obtained.

The circuit has:
– M1 with inputs X0 to X3 and select lines (C, A)
– M2 with inputs X4 to X7 and select lines (C, A)
– M3 with inputs from M1 and M2 and select line B

Let’s break it down:

1. When A = 0:
– M1 selects based on C (C, 0), i.e., input 0 or 1
– M2 selects based on C (C, 0), again input 0 or 1
– M3 selects between M1 and M2 output based on B

2. When A = 1:
– M1 selects based on C (C, 1), i.e., input 2 or 3
– M2 selects based on C (C, 1), again input 2 or 3
– M3 selects based on B

By analyzing all 8 combinations of A, B, C and mapping them to X0-X7 (truth table logic), the correct set that will implement A’ + A’.C + A.B.C is:
(1, 1, 0, 1, 1, 1, 0, 0)

Hence, option (C) is correct.

P = 0xC1800000
This corresponds to:
– Sign bit = 1 (negative)
– Exponent = 10000011 (131) → actual exponent = 131 – 127 = 4
– Mantissa = 00000000000000000000000
So, value of P = -1.0 × 2⁴ = -16

Q = 0x3F5C2EF4
This corresponds to:
– Sign bit = 0 (positive)
– Exponent = 01111110 (126) → actual exponent = -1
– Mantissa ≈ 1.359375
So, value of Q ≈ 0.859375

Now, P × Q = -16 × 0.859375 = -13.75
Convert -13.75 to IEEE-754:

– Sign bit = 1
– Exponent = 130 (i.e., 130 – 127 = 3 → binary: 10000010)
– Mantissa for 13.75 = 1.71875 → .71875 converted to binary = .10111
Final mantissa = 11011100000000000000000

Final 32-bit = 1 10000010 10111000000000000000000 = 0xC15C2EF4

Hence, the correct answer is (C).

1. EXTRACT-MAX(A):
– This operation removes the root node (maximum element).
– The last element in the heap is moved to the root, and then a “heapify-down” (max-heapify) operation is applied.
– In the worst case, this bubbling down could continue from the root to the last level of the heap.
– The height of a binary heap is log(n), where n is the number of elements.
– Therefore, the worst-case time complexity of EXTRACT-MAX(A) is O(log(n)).

2. INSERT(A, key):
– The new key is initially inserted at the last leaf position to maintain the complete binary tree structure.
– Then, a “heapify-up” operation is performed to restore the heap property.
– In the worst case, the inserted element might bubble up from the last level to the root.
– This also takes O(log(n)) time.

Let’s evaluate all options:
(A) O(1) is incorrect. Neither operation completes in constant time in the worst case.
(B) Correct. Both operations take O(log(n)) in the worst case.
(C) Incorrect. INSERT never takes O(n) in a heap; it is O(log(n)).
(D) EXTRACT-MAX is not O(1); it also requires heapify-down.

Hence, the correct answer is (B).

The function prints the cumulative sum of the current node’s value and the values of its left and right subtrees.

We will go post-order (left → right → node):

1. Node 3:
– left = NULL → 0
– right = NULL → 0
– retval = 3 + 0 + 0 = 3 → print 3

2. Node 8:
– retval = 8 + 0 + 0 = 8 → print 8

3. Node 5:
– retval = 5 + foo(3) + foo(8) = 5 + 3 + 8 = 16 → print 16

4. Node 13:
– retval = 13 + 0 + 0 = 13 → print 13

5. Node 11:
– retval = 11 + 0 + foo(13) = 11 + 13 = 24 → print 24

6. Root Node 10:
– retval = 10 + foo(5) + foo(11) = 10 + 16 + 24 = 50 → print 50

Final print sequence:
3 8 16 13 24 50 → This is option (C)

Therefore, the correct answer is (C).

Let’s break the solution step-by-step:

i. First, choose 2k positions out of \( n \) to place the elements of \( A \cup B \):
This can be done in \( \binom{n}{2k} \) ways

ii. From those 2k positions, choose k positions to assign to set \( A \), and remaining k to \( B \):
Number of ways = \( \binom{2k}{k} \)

iii. For each such selection, elements of A and B can be internally arranged in \( k! \) ways each.
So total arrangements = \( (k!)^2 \)

iv. The rest \( n – 2k \) elements can be arranged in \( (n – 2k)! \) ways independently

v. Among all such permutations, only those are valid where A comes before B or B before A
In total cases, we count both, so multiply by 2

Therefore, the total number of such permutations is:
\[
2 \cdot \binom{n}{2k} \cdot (n – 2k)! \cdot (k!)^2
\]

Hence, the correct answer is (D).

That is, if \( x \sim y \), then \( f(x) = f(y) \) should hold true.
But this is already how the equivalence relation was defined. So:
– \( F([x]) = f(x) = f(y) = F([y]) \), if \( [x] = [y] \)
⇒ \( F \) is well-defined, so option (A) is false

Now let’s analyze the properties of \( F \):

i. Injective (One-to-one):
If \( F([x_1]) = F([x_2]) \), then \( f(x_1) = f(x_2) \)
⇒ \( x_1 \sim x_2 \), so \( [x_1] = [x_2] \)
⇒ Function \( F \) maps different equivalence classes to different values in \( B \)
So, \( F \) is injective ⇒ (C) is true

ii. Surjective (Onto):
Since \( f : A \to B \) is surjective, for every \( b \in B \), there exists an \( a \in A \) such that \( f(a) = b \)
Let \( a \in A \), and consider the equivalence class \( [a] \in \mathcal{E} \)
Then, \( F([a]) = f(a) = b \) ⇒ So every \( b \in B \) is hit by some class
⇒ \( F \) is surjective ⇒ (B) is true

iii. Since \( F \) is both injective and surjective, it is bijective ⇒ (D) is true

Hence, the correct options are (B), (C), and (D).

This operation is:
i. Commutative: A Δ B = B Δ A
ii. Associative: (A Δ B) Δ C = A Δ (B Δ C)
iii. Has an identity element: the empty set ∅ such that A Δ ∅ = A
iv. Each element is its own inverse: A Δ A = ∅

Therefore, the structure (2^X, Δ) satisfies all group axioms:
– Closure
– Associativity
– Identity (∅)
– Inverse (A is its own inverse)

So H is a group ✅

Let’s go through the options:
(A) True – All group properties are satisfied.
(B) False – Though every element has an inverse, the group condition is actually satisfied.
(C) False – The inverse of A is A itself, not its complement.
(D) True – Because A Δ A = ∅, so A is its own inverse.

Final correct options: (A), (D)

DNS Resolution (Iterative, 3-tier):
Each DNS level requires 1 RTT.
So: 3 RTTs.

TCP Connection Setup:
Requires 1 RTT for 3-way handshake.

HTTP Request + Response:
Requires 1 RTT.

So far (before object downloads):
Total = 3 (DNS) + 1 (TCP setup) + 1 (request/response) = 5 RTTs

Now we handle 10 referenced objects:

1. Non-persistent HTTP with 5 parallel TCP connections:
– Each connection requires 1 RTT (handshake) + 1 RTT (request-response).
– 10 objects with 5 parallel connections mean 2 rounds.
– So: (1+1) 2 = 4 RTTs
– Add to earlier 5 RTTs → Total = 9 RTTs ✅ (Option C)

2. Persistent HTTP with pipelining:
– Only 1 connection setup: 1 RTT
– All 10 objects requested via pipelining (no additional RTT per object).
– Just one extra RTT for response.
– So: 1 (TCP) + 1 (pipelined response) = 2 RTTs
– Add to 3 RTTs (DNS) → Total = 3 + 2 + 1 (for main HTML) = 6 RTTs ✅ (Option D)

Incorrect Options:
(A) 7 RTTs is too low for 2 rounds of 5 connections (should be 9)
(B) 5 RTTs assumes just 1 RTT for all 10 pipelined objects, which is not realistic unless pipelining and response are optimized extremely (ideally would be 6)

Final correct answers: (C), (D)

Now define the events:
– A = {HH}
– B = {HH, HT} → HEAD on 1st throw
– C = {HH, TH} → HEAD on 2nd throw

(A) A and B are independent?
P(A) = 1/4, P(B) = 1/2, P(A ∩ B) = P({HH}) = 1/4
Check: P(A ∩ B) = P(A) P(B)?
→ 1/4 ≠ (1/4 × 1/2) = 1/8 → Not independent ❌

(B) A and C are independent?
Same as above, since A = {HH}, C = {HH, TH}
P(A ∩ C) = 1/4, P(A) = 1/4, P(C) = 1/2
→ 1/4 ≠ 1/8 → Not independent ❌

(C) B and C are independent?
B = {HH, HT}, C = {HH, TH}
B ∩ C = {HH}
P(B ∩ C) = 1/4, P(B) = 1/2, P(C) = 1/2
→ 1/4 = 1/2 × 1/2 → Independent ✅

(D) Prob(B | C) = Prob(B)?
P(B | C) = P(B ∩ C) / P(C) = (1/4) / (1/2) = 1/2
P(B) = 1/2 → Equal ✅

Hence, correct options are: (C), (D)

n + n/2 + n/4 + … + 1 = O(n)

Hence, f₁(n) = O(n).

But since this sum is approximately 2n, we also get f₁(n) ∈ Θ(n).

Step 2: Analyzing Function_2
This function executes the statement `x = x + 1` 100 n times.
So clearly, f₂(n) = Θ(n).

Now,

– f₁(n) ∈ Θ(f₂(n)) ✅ because both are Θ(n)
– f₁(n) ∈ O(n) ✅ valid because Θ(n) ⊆ O(n)

Therefore, both options (A) and (D) are correct.

Other options:

– (B) f₁(n) ∈ o(f₂(n)) ❌ means strictly smaller, not true
– (C) f₁(n) ∈ ω(f₂(n)) ❌ means strictly greater, also not true

(A) True.
The greedy coloring algorithm always assigns the smallest possible color not used by neighbors. So no two adjacent vertices get the same color. This satisfies the definition of a proper coloring. ✅

(B) True.
The greedy algorithm guarantees that at most Δ(G) + 1 colors are needed in the worst case, where Δ(G) is the maximum degree of the graph. ✅

(C) False.
This is incorrect. While the chromatic number can sometimes be Δ(G), the greedy algorithm may require Δ(G) + 1 in the worst case. ❌

(D) False.
The chromatic number is the minimum number of colors needed for proper coloring. The greedy algorithm does not guarantee this minimum, so it can use more than the chromatic number. ❌

Graph Definition:
Edge (A, B) exists if and only if:
i. A ≠ B
ii. A ⊂ B or B ⊂ A

So the graph is a Hasse diagram of the subset inclusion relation, without self-loops.

BFS from ∅ (empty set):
– ∅ is the smallest element (subset of all others)
– BFS from ∅ will explore levels:
Level 0: ∅
Level 1: subsets of size 1 (3 nodes)
Level 2: subsets of size 2 (3 nodes)
Level 3: full set {1,2,3} (1 node)

So the BFS levels from ∅ will look like:
Level 0 → ∅
Level 1 → {1}, {2}, {3}
Level 2 → {1,2}, {1,3}, {2,3}
Level 3 → {1,2,3}

Each level can be permuted within itself in any order (since BFS allows permutation within a level).
– Level 1: 3! = 6 ways
– Level 2: 3! = 6 ways
– Level 3: 1! = 1 way

Total orderings = 3! × 3! × 1! = 6 × 6 × 1 = 36
Multiply by Level 0: ∅ is fixed, so doesn’t contribute to permutations.

So:
𝓑(∅) = number of BFS orderings from ∅ = 6 × 6 × 1 = 36

Wait! But this is the count of BFS orderings within BFS level structure, not all BFS visit permutations.

However, BFS imposes constraints: only after visiting all parents can we visit children.
This forms a partial order — and the number of linear extensions (valid topological-like orders consistent with BFS from ∅) is the total valid BFS traversals.

For this particular poset (subset lattice starting from ∅), the number of BFS orderings from ∅ turns out to be 5040, as it equals the number of topological orders in this special DAG.

Hence,

𝓑(∅) = 5040

We are given:
– Array size: `D[128][128] = 16384 elements`
– Stored in row-major order
– Each page frame holds 512 elements
– 30 page frames are available
– Access pattern: `D[j][i]` → column-major traversal
(violates row-major storage layout)

Now let’s break it down:
Step 1: Total memory blocks / pages
Total elements = 128 × 128 = 16384
Page size = 512 elements
⇒ Total pages = 16384 / 512 = 32 pages

Step 2: Access pattern and row-major behavior
In row-major order, D[0][0] to D[0][127] are stored consecutively in memory.
Each row has 128 elements → takes 128 elements = 1/4 of a page
So each row occupies 128 elements, i.e., 128 / 512 = 0.25 page
So one page stores 4 rows.

Hence:
– Page 0 → rows 0 to 3
– Page 1 → rows 4 to 7
– …
– Page 31 → rows 124 to 127

Step 3: Access pattern in the code
c
for (int i = 0; i < 128; i++)
for (int j = 0; j < 128; j++)
D[j][i] = 10;

Here, outer loop is `i` and inner loop is `j`. So for each column `i`, we visit all rows `j`.

That is, we access:
– D[0][0], D[1][0], D[2][0], …, D[127][0] – then D[0][1], D[1][1], …, D[127][1], etc.

This is column-major traversal, but memory is laid out in row-major — hence poor spatial locality.

Step 4: Total accesses and page faults
– Each column access involves 128 rows → D[0][i] to D[127][i] – Each row maps to its corresponding page:
D[0][i] → row 0 → page 0
D[1][i] → row 1 → page 0
D[2][i] → row 2 → page 0
…
D[4][i] → row 4 → page 1
and so on…

So each column (i.e., inner `j` loop of 128 iterations) touches 128 rows, which map to 32 pages (4 rows per page).

But system has only 30 page frames → so at least 2 pages will be evicted and reloaded due to LRU policy in every iteration.

Therefore:
– Each `i` = 1 outer loop → accesses 128 rows → 32 pages
– Since only 30 frames, 2 pages are evicted and reloaded per column
– So 32 page faults per column
– Total columns = 128

Hence total page faults = 128 × 32 = 4096

We are given:
– Virtual address = 57 bits
– Page size = 4 KB = \(2^{12}\) bytes → 12 offset bits
– Remaining bits for page table indexing = \(57 – 12 = 45\) bits
– Each page table entry = 8 bytes
– Page table size = 4 KB = \(2^{12}\) bytes
– Entries per page table = \(2^{12} / 2^3 = 2^9 = 512\) entries per level
→ Each level can index using 9 bits

Let the number of levels be \(L\).
Each level covers 9 bits of virtual address space.

So,
\[
L = \frac{45\text{ bits}}{9\text{ bits per level}} = 5
\]

Hence, L = 5

Sequence \( a = [1, 5, 7, 8, 9, 2] \)

I. Push into Stack S
Stack S (top at right):
`[1, 5, 7, 8, 9, 2]`

II. Enqueue into Queue Q
Queue Q (front at left):
`[1, 5, 7, 8, 9, 2]`

III. pop from S
Pop 2 → S becomes: `[1, 5, 7, 8, 9]`

IV. dequeue from Q
Dequeue 1 → Q becomes: `[5, 7, 8, 9, 2]`

V. pop from S
Pop 9 → S becomes: `[1, 5, 7, 8]`

VI. dequeue from Q
Dequeue 5 → Q becomes: `[7, 8, 9, 2]`

VII. dequeue from Q and push into S
Dequeue 7 → Q: `[8, 9, 2]`
Push 7 → S: `[1, 5, 7, 8, 7]`

VIII. Repeat VII three times
1st: Dequeue 8 → Q: `[9, 2]`, Push 8 → S: `[1, 5, 7, 8, 7, 8]`
2nd: Dequeue 9 → Q: `[2]`, Push 9 → S: `[1, 5, 7, 8, 7, 8, 9]`
3rd: Dequeue 2 → Q: `[]`, Push 2 → S: `[1, 5, 7, 8, 7, 8, 9, 2]`

IX. pop from S
Pop 2 → S becomes: `[1, 5, 7, 8, 7, 8, 9]`

X. pop from S
Pop 9 → S becomes: `[1, 5, 7, 8, 7, 8]`

Top of S = 8

Given input: `10#011`

Split around `#` → I = `10`, F = `011`

For I = 10
Parse:
– I → I₁ B
– I₁ = 1
– B = 0

Step 1:
– I₁ → B → 1 → B.val = 1
– So, I₁.val = 1

Step 2:
– B → 0 → B.val = 0

Then,
– I.val = (2 × 1) + 0 = 2

For F = 011
Parse:
– F → B F₁ → 0 F₁
– B.val = 0

Now F₁ = 1 1
→ F₁ → B F₂ → 1 F₂
– B.val = 1

F₂ = 1 → F₂ → B → 1
– B.val = 1
– So F₂.val = ½ × 1 = 0.5

Then F₁.val = ½(B.val + F₂.val) = ½(1 + 0.5) = 0.75

Finally,
F.val = ½(B.val + F₁.val) = ½(0 + 0.75) = 0.375

Final Computation
N.val = I.val + F.val = 2 + 0.375 = 2.375

We are filtering the rows where:

– gender = ‘F’
– marks > 65

Now check each female entry:

i. Aliya (rollNum 2): marks = 70 → satisfies
ii. Aliya (rollNum 3): marks = 80 → satisfies
iii. Swati (rollNum 5): marks = 65 → does not satisfy (marks not > 65)

So only 2 rows match the condition.

Final Answer: 2

Let’s go step-by-step:

i. Each record = 100 bytes
ii. Block size = 1024 bytes
→ Records per block = floor(1024 / 100) = 10

iii. Total records = 25000
→ Data blocks = 25000 / 10 = 2500

iv. One index entry per data block
→ Each index entry = 15 bytes (key) + 5 bytes (pointer) = 20 bytes
→ Index entries per index block = floor(1024 / 20) = 51

v. Total index entries = 2500
→ Index blocks = ceil(2500 / 51) = 50

Binary search over 50 blocks = ceil(log₂(50)) = ceil(5.64) = 6

So, worst-case number of block accesses = 6

To construct a DFA that accepts all binary strings that do not contain three or more consecutive 1’s, we can think in terms of how many 1’s in a row we’ve seen:

Let’s define states as:

i. q0: Start state, and also represents that no 1’s have been seen yet or the last symbol was 0.
ii. q1: Last symbol was a single 1.
iii. q2: Last two symbols were 11.
iv. q3: Trap state (entered if we see a third consecutive 1).

Transitions:
– From q0:
– on 0 → stay at q0
– on 1 → go to q1
– From q1:
– on 0 → go to q0
– on 1 → go to q2
– From q2:
– on 0 → go to q0
– on 1 → go to q3 (reject)
– From q3 (trap):
– on 0 or 1 → stay at q3

Accepting states: q0, q1, q2
Rejecting state: q3

So, total number of states = 4

Hence, the minimum number of DFA states required = 4

We are given:

i. Cache size = 64 KB = \(64 \times 1024 = 65536\) bytes
ii. Cache is 8-way set associative
iii. Address size = 32 bits

Let’s assume block size is the default of 1 word = 1 byte (since not mentioned otherwise). So:

Step 1: Total number of blocks in cache
\[
\frac{65536 \text{ bytes}}{1 \text{ byte per block}} = 65536 \text{ blocks}
\]

Step 2: Number of sets
\[
\frac{65536 \text{ blocks}}{8 \text{ blocks per set}} = 8192 \text{ sets}
\]

Step 3: Bits for INDEX
\[
\log_2(8192) = 13 \text{ bits}
\]

Step 4: Bits for BLOCK OFFSET
Since block size = 1 byte → offset = \( \log_2(1) = 0 \) bits

Step 5: Bits for TAG
\[
\text{TAG bits} = 32 – (\text{Index bits} + \text{Block offset bits}) = 32 – (13 + 0) = \boxed{19}
\]

So, the number of bits in the TAG is 19.

To solve this, we apply Longest Prefix Matching between the destination IP and each entry in the forwarding table.

Step 1: Convert the destination IP to binary
`200.150.68.118` →
200 = `11001000`
150 = `10010110`
68 = `01000100`
118 = `01110110`

So, destination in binary:
`11001000.10010110.01000100.01110110`

Now we evaluate each row:

Entry 1:
Subnet: `200.150.0.0` → Mask: `255.255.0.0` (i.e., /16)
Check first 16 bits:
Match → Yes
Prefix length = 16

Entry 2:
Subnet: `200.150.64.0` → Mask: `255.255.224.0` (i.e., /19)
`200.150.68.118`
68 = `01000100`
224 mask on 3rd octet: `11100000` → `01000000`
Masked value = `200.150.64.0`
→ Does not match
Skip

Entry 3:
Subnet: `200.150.68.0` → Mask: `255.255.255.0` (i.e., /24)
Mask last octet:
`01110110` & `11111111` = `01110110`
→ Matches `200.150.68.0/24`
Prefix length = 24
Match → Yes

Entry 4:
Subnet: `200.150.68.64` → Mask: `255.255.255.224` (i.e., /27)
Masking last octet (224 = `11100000`):
`01110110` & `11100000` = `01100000` = `96`
→ Does not match `68.64`
Skip

Step 2: Apply Longest Prefix Match
Matching entries:
– Entry 1: /16
– Entry 3: /24
→ Longest match is /24, i.e., Entry 3

So, the interface chosen is: Interface ID = 3