Programming, Data Structures and Algorithms using Python · Quiz 2 · Sep 2024

**Answer: A** **Topic:** Storage Systems — *Calculating Average Rotational Latency of a Disk* ### Step-by-Step Solution **Step 1:** For an 8000 RPM disk (from the preceding AppDev1 disk parameters where 1 full revolution takes $\frac{60,000\text{ ms}}{8000} = 7.5\text{ ms}$), the **average rotational latency** is the time taken for **half a revolution**: $$\text{Average Rotational Latency} = \frac{1}{2} \times \frac{60,000\text{ ms}}{8000} = \frac{7.5\text{ ms}}{2} = 3.75\text{ ms}$$ **Step 2:** Note that rotational latency depends only on the rotational speed of the platter and is independent of the $3\text{ ms}$ seek time. **Step 3:** Therefore, **A** (`3.75 ms`) is correct. **Key Takeaway / Tip:** Average rotational latency is half of one full rotation time ($7.5\text{ ms} / 2 = 3.75\text{ ms}$), whereas maximum rotational latency is one full rotation ($7.5\text{ ms}$). A: **Correct:** Option A (3.75 ms) matches our derived result under Calculating Average Rotational Latency of a Disk. Average rotational latency is half of one full rotation time ($7.5\text{ ms} / 2 = 3.75\text{ ms}$), whereas maximum rotational latency is one full rotation ($7.5\text{ ms}$). B: **Incorrect:** Option B (7.5 ms) does not satisfy the conditions derived in the step-by-step analysis for Calculating Average Rotational Latency of a Disk (correct choice: A). C: **Incorrect:** Option C (6.75 s) does not satisfy the conditions derived in the step-by-step analysis for Calculating Average Rotational Latency of a Disk (correct choice: A). D: **Incorrect:** Option D (10.5 s       **PDSA** **Section Id :** 64065373857 **Section Number :** 3 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :** 17 **Number o...) does not satisfy the conditions derived in the step-by-step analysis for Calculating Average Rotational Latency of a Disk (correct choice: A).

**Answer: A** **Topic:** Graph Algorithms — *Matching Shortest-Path and MST Algorithms to Their Properties* ### Step-by-Step Solution **Step 1:** Match each graph algorithm (A–D) to its exact description (I–IV): - **A. Dijkstra's Algorithm**: Finds the shortest path from a single source vertex to all other vertices in a weighted graph with **non-negative** edge weights $\to$ **II** (`A-II`). - **B. Floyd-Warshall Algorithm**: Finds the shortest path between **all pairs** of vertices in a graph with positive or negative weights (no negative weight cycle) $\to$ **I** (`B-I`). - **C. Bellman-Ford Algorithm**: Finds the shortest path from a **single source** vertex to all other vertices in a weighted graph with positive or negative weights (no negative weight cycle) $\to$ **III** (`C-III`). - **D. Prim's Algorithm**: Finds a Minimum Spanning Tree (subset of edges connecting all vertices without cycles and with minimum total edge weight) $\to$ **IV** (`D-IV`). **Step 2:** Thus, the correct matching is **A-II, B-I, C-III, D-IV**, which matches **A**. **Key Takeaway / Tip:** Distinguish single-source non-negative (Dijkstra: II), single-source with negative weights (Bellman-Ford: III), and all-pairs (Floyd-Warshall: I). A: **Correct:** Option A (A-II, B-I, C-III, D-IV) matches our derived result under Matching Shortest-Path and MST Algorithms to Their Properties. Distinguish single-source non-negative (Dijkstra: II), single-source with negative weights (Bellman-Ford: III), and all-pairs (Floyd-Warshall: I). B: **Incorrect:** Option B (A-II, B-I, C-IV, D-III) does not satisfy the conditions derived in the step-by-step analysis for Matching Shortest-Path and MST Algorithms to Their Properties (correct choice: A). C: **Incorrect:** Option C (A-I, B-II, C-III, D-IV) does not satisfy the conditions derived in the step-by-step analysis for Matching Shortest-Path and MST Algorithms to Their Properties (correct choice: A). D: **Incorrect:** Option D (A-III, B-II, C-IV, D-I) does not satisfy the conditions derived in the step-by-step analysis for Matching Shortest-Path and MST Algorithms to Their Properties (correct choice: A).

**Answer: C** **Topic:** Graph Algorithms — *Dijkstra's Shortest Path Visitation Order from Source B* ### Step-by-Step Solution **Step 1:** Initialize distances from source vertex $B$: $d(B) = 0$, and all other vertices at $\infty$. - **Visit 1 ($B$, $d=0$)**: Outgoing edges from $B$ are $(B, F)$ of weight $5 \implies d(F) = 5$, and $(B, E)$ of weight $3 \implies d(E) = 3$. **Step 2:** Repeatedly visit the unvisited vertex with minimum tentative distance and relax its outgoing edges: - **Visit 2 ($E$, $d=3$)**: Outgoing edges from $E$ are $(E, F)$ of weight $1 \implies d(F) = \min(5, 3+1) = 4$, and $(E, C)$ of weight $5 \implies d(C) = 3+5 = 8$. - **Visit 3 ($F$, $d=4$)**: Outgoing edge $(F, A)$ of weight $5 \implies d(A) = 4+5 = 9$. (Unvisited distances: $C = 8, A = 9$). - **Visit 4 ($C$, $d=8$)**: Outgoing edges from $C$ are $(C, G)$ of weight $2 \implies d(G) = 8+2 = 10$, and $(C, D)$ of weight $4 \implies d(D) = 8+4 = 12$. (Unvisited distances: $A = 9, G = 10, D = 12$). - **Visit 5 ($A$, $d=9$)**: Outgoing edges $(A, E)$ and $(A, C)$ go to already visited vertices. - **Visit 6 ($G$, $d=10$)**: Outgoing edge $(G, D)$ of weight $1 \implies d(D) = \min(12, 10+1) = 11$. - **Visit 7 ($D$, $d=11$)**: Final vertex. **Step 3:** Thus, the visitation order is **B, E, F, C, A, G, D**, which matches **C**. **Key Takeaway / Tip:** Notice that $(E, C)$ has weight $5$, giving $d(C) = 3 + 5 = 8$, which is smaller than $d(A) = 4 + 5 = 9$, so $C$ is visited before $A$. A: **Incorrect:** Option A (B, E, C, F, A, D, G) does not satisfy the conditions derived in the step-by-step analysis for Dijkstra's Shortest Path Visitation Order from Source B (correct choice: C). B: **Incorrect:** Option B (B, E, F, A, C, G, D) does not satisfy the conditions derived in the step-by-step analysis for Dijkstra's Shortest Path Visitation Order from Source B (correct choice: C). C: **Correct:** Option C (B, E, F, C, A, G, D) matches our derived result under Dijkstra's Shortest Path Visitation Order from Source B. Notice that $(E, C)$ has weight $5$, giving $d(C) = 3 + 5 = 8$, which is smaller than $d(A) = 4 + 5 = 9$, so $C$ is visited before $A$. D: **Incorrect:** Option D (B, E, F, A, C, D, G) does not satisfy the conditions derived in the step-by-step analysis for Dijkstra's Shortest Path Visitation Order from Source B (correct choice: C).

**Answer: C** **Topic:** Graph Algorithms — *Time Complexity of Prim's and Dijkstra's Algorithms with a Min-Heap* ### Step-by-Step Solution **Step 1:** In a graph with $n = |V|$ vertices and $m = |E|$ edges represented using adjacency lists: - **Statement 1 (Prim's Algorithm)**: Using a binary min-heap (priority queue), we perform $n$ `extract_min` operations ($O(n \log n)$) and at most $m$ `decrease_key` / heap updates ($O(m \log n)$), improving the time complexity from $O(n^2)$ to **$O((m + n)\log n)$** — **Correct**. - **Statement 2 (Dijkstra's Algorithm)**: Using a binary min-heap with adjacency lists similarly performs $n$ extractions and at most $m$ edge relaxations/updates, improving the time complexity from $O(n^2)$ to **$O((m + n)\log n)$** — **Correct**. **Step 2:** Therefore, **Both statements are correct** (**C**). **Key Takeaway / Tip:** Replacing a linear array scan ($O(n^2)$) with a binary min-heap reduces both Prim's and Dijkstra's algorithms to $O((m + n)\log n)$. A: **Incorrect:** Option A (Only statement 1 is correct.) does not satisfy the conditions derived in the step-by-step analysis for Time Complexity of Prim's and Dijkstra's Algorithms with a Min-Heap (correct choice: C). B: **Incorrect:** Option B (Only statement 2 is correct.) does not satisfy the conditions derived in the step-by-step analysis for Time Complexity of Prim's and Dijkstra's Algorithms with a Min-Heap (correct choice: C). C: **Correct:** Option C (Both statements are correct.) matches our derived result under Time Complexity of Prim's and Dijkstra's Algorithms with a Min-Heap. Replacing a linear array scan ($O(n^2)$) with a binary min-heap reduces both Prim's and Dijkstra's algorithms to $O((m + n)\log n)$. D: **Incorrect:** Option D (Both statements are incorrect.) does not satisfy the conditions derived in the step-by-step analysis for Time Complexity of Prim's and Dijkstra's Algorithms with a Min-Heap (correct choice: C).

**Answer: B** **Topic:** Binary Search Trees — *Finding the k-th Smallest Node via In-Order Traversal* ### Step-by-Step Solution **Step 1:** Recall that in any **Binary Search Tree (BST)**, an **in-order traversal (`Left -> Root -> Right`)** visits the nodes in strictly ascending order of their stored values. **Step 2:** Perform an in-order traversal of the given BST: 1. Left subtree of `A` (rooted at `B`, which has no left child, and right child `D` with children `G` and `H`): - Visit `B` (**1st smallest**) - Traverse `D`: visit left child `G` (**2nd smallest**), visit `D` (**3rd smallest**), visit right child `H` (**4th smallest**) 2. Visit root `A` (**5th smallest**) 3. Right subtree of `A` (rooted at `C`, with left child `E` [which has right child `I`] and right child `F` [which has right child `J`]): - Go to left child of `C`, which is `E` (no left child): visit **`E` (6th smallest!)** - Then `I` (7th), `C` (8th), `F` (9th), `J` (10th). **Step 3:** Thus, the $6$-th smallest node is **`E`**, which matches **B**. **Key Takeaway / Tip:** You don't need to know the numeric keys stored in a BST to rank them—simply run an in-order traversal (`B, G, D, H, A, E, I, C, F, J`) and pick the 6th node (`E`)! A: **Incorrect:** Option A (C) does not satisfy the conditions derived in the step-by-step analysis for Finding the k-th Smallest Node via In-Order Traversal (correct choice: B). B: **Correct:** Option B (E) matches our derived result under Finding the k-th Smallest Node via In-Order Traversal. You don't need to know the numeric keys stored in a BST to rank them—simply run an in-order traversal (`B, G, D, H, A, E, I, C, F, J`) and pick the 6th node (`E`)! C: **Incorrect:** Option C (F) does not satisfy the conditions derived in the step-by-step analysis for Finding the k-th Smallest Node via In-Order Traversal (correct choice: B). D: **Incorrect:** Option D (I) does not satisfy the conditions derived in the step-by-step analysis for Finding the k-th Smallest Node via In-Order Traversal (correct choice: B).

**Answer: A** **Topic:** Greedy Algorithms — *Minimum Steps to Reach n Using Increment and Double Operations* ### Step-by-Step Solution **Step 1:** To reach $n = 725$ from $x = 1$ in the minimum number of steps using `+1` (increment) and `*2` (double), work **backwards** from $725$ down to $1$: - Whenever the current number is **even**, divide by $2$ (`*2` forward). - Whenever the current number is **odd** (and $> 1$), subtract $1$ (`+1` forward). **Step 2:** Trace backwards from $725$ to $1$ (or count binary bits of $725 = 512 + 128 + 64 + 16 + 4 + 1 = 1011010101_2$): - Binary representation of $725$ is `1011010101` ($10$ bits, with $6$ ones and $4$ zeros): - Starting from the leading `1`, each subsequent bit requires **1 doubling step** ($10 - 1 = 9$ doublings total), and each `1` bit after the leading `1` requires **1 increment step** ($6 - 1 = 5$ increments total). **Step 3:** Sum the doublings and increments: $$\text{Minimum Steps} = 9 + 5 = 14$$ which matches **A** (`14`). **Key Takeaway / Tip:** Binary shortcut: for any positive integer $n$, the minimum number of `+1` and `*2` steps to reach $n$ from $1$ is $(\text{number of bits in } n - 1) + (\text{number of 1-bits in } n - 1) = (10 - 1) + (6 - 1) = 14$! A: **Correct:** Option A (14) matches our derived result under Minimum Steps to Reach n Using Increment and Double Operations. Binary shortcut: for any positive integer $n$, the minimum number of `+1` and `*2` steps to reach $n$ from $1$ is $(\text{number of bits in } n - 1) + (\text{number of 1-bits in } n - 1) = (10 - 1) + (6 - 1) = 14$! B: **Incorrect:** Option B (15) does not satisfy the conditions derived in the step-by-step analysis for Minimum Steps to Reach n Using Increment and Double Operations (correct choice: A). C: **Incorrect:** Option C (16) does not satisfy the conditions derived in the step-by-step analysis for Minimum Steps to Reach n Using Increment and Double Operations (correct choice: A). D: **Incorrect:** Option D (17) does not satisfy the conditions derived in the step-by-step analysis for Minimum Steps to Reach n Using Increment and Double Operations (correct choice: A).

**Answer: B** **Topic:** Divide and Conquer — *Matching Recurrence Relations to Time Complexities* ### Step-by-Step Solution **Step 1:** Solve each recurrence relation (A–D): - **A. $T(n) = 2T(n/8) + O(n)$**: Here $a = 2, b = 8 \implies n^{\log_8 2} = n^{1/3}$. Since $f(n) = O(n)$ dominates $n^{1/3}$ (Case 3 of Master Theorem), $T(n) = O(n)$ $\to$ **2** (`A-2`). - **B. $T(n) = 4T(n/4) + O(n)$**: Here $a = 4, b = 4 \implies n^{\log_4 4} = n^1$. By Case 2 of Master Theorem, $T(n) = O(n \log n)$ $\to$ **3** (`B-3`). - **C. $T(n) = T(n - 1) + O(n)$**: Unrolling gives $\sum_{k=1}^n O(k) = O(n^2)$ $\to$ **4** (`C-4`). - **D. $T(n) = T(n/2) + O(1)$**: Binary search recurrence ($a = 1, b = 2, f(n) = O(1)$) gives $O(\log n)$ $\to$ **1** (`D-1`). **Step 2:** Thus, the correct matching is **A-2, B-3, C-4, D-1**, which matches **B**. **Key Takeaway / Tip:** For $T(n) = 2T(n/8) + O(n)$, work per level shrinks geometrically ($n + n/4 + n/16 + \dots$), so the root level $O(n)$ dominates (`A-2`). A: **Incorrect:** Option A (A-2, B-4, C-3, D-1) does not satisfy the conditions derived in the step-by-step analysis for Matching Recurrence Relations to Time Complexities (correct choice: B). B: **Correct:** Option B (A-2, B-3, C-4, D-1) matches our derived result under Matching Recurrence Relations to Time Complexities. For $T(n) = 2T(n/8) + O(n)$, work per level shrinks geometrically ($n + n/4 + n/16 + \dots$), so the root level $O(n)$ dominates (`A-2`). C: **Incorrect:** Option C (A-2, B-3, C-1, D-4) does not satisfy the conditions derived in the step-by-step analysis for Matching Recurrence Relations to Time Complexities (correct choice: B). D: **Incorrect:** Option D (A-3, B-2, C-4, D-1) does not satisfy the conditions derived in the step-by-step analysis for Matching Recurrence Relations to Time Complexities (correct choice: B).

**Answer: C** **Topic:** Divide and Conquer — *Combine Step in Closest Pair of Points Algorithm* ### Step-by-Step Solution **Step 1:** In the classic $O(n \log n)$ divide-and-conquer algorithm for the **Closest Pair of Points** in 2D: 1. Divide the points by the median x-coordinate into left half $P_L$ and right half $P_R$. 2. Recursively find the minimum distance $\delta_L$ in $P_L$ and $\delta_R$ in $P_R$, and let $\delta = \min(\delta_L, \delta_R)$. 3. **Combine step**: Checkwhether there is any pair of points $(p, q)$ with $p \in P_L$ and $q \in P_R$ (within a vertical strip of width $2\delta$ around the dividing line) whose distance is $< \delta$. **Step 2:** Therefore, the required additional step is to **consider pairs that span both halves** (**C**). **Key Takeaway / Tip:** The closest pair overall might have one point in the left half and one point in the right half, so we must check cross-boundary pairs within the $\pm \delta$ strip. A: **Incorrect:** Option A (Combine the results directly) does not satisfy the conditions derived in the step-by-step analysis for Combine Step in Closest Pair of Points Algorithm (correct choice: C). B: **Incorrect:** Option B (Perform a linear search for the closest pair) does not satisfy the conditions derived in the step-by-step analysis for Combine Step in Closest Pair of Points Algorithm (correct choice: C). C: **Correct:** Option C (Consider pairs that span both halves) matches our derived result under Combine Step in Closest Pair of Points Algorithm. The closest pair overall might have one point in the left half and one point in the right half, so we must check cross-boundary pairs within the $\pm \delta$ strip. D: **Incorrect:** Option D (Sort the points by their distances) does not satisfy the conditions derived in the step-by-step analysis for Combine Step in Closest Pair of Points Algorithm (correct choice: C).

**Answer: B** **Topic:** Divide and Conquer — *Worst-Case Complexity of QuickSelect vs. FastSelect (Median of Medians)* ### Step-by-Step Solution **Step 1:** Evaluate both statements: - **Statement 1**: Standard QuickSelect (without Median of Medians) can suffer bad pivots on every recursive call (e.g., reducing the array size by only 1 each step), resulting in a worst-case running time of **$O(n^2)$**, NOT $O(n \log n)$ — **Statement 1 is incorrect**. - **Statement 2**: FastSelect (QuickSelect using the **Median of Medians [MoM]** strategy to guarantee a balanced pivot in the 30th–70th percentile) satisfies $T(n) \le T(n/5) + T(7n/10) + O(n)$, achieving a deterministic **worst-case running time of $O(n)$** — **Statement 2 is correct**. **Step 2:** Therefore, **Only statement 2 is correct** (**B**). **Key Takeaway / Tip:** Standard QuickSelect has $O(n)$ average time but $O(n^2)$ worst-case time; Median-of-Medians (FastSelect) improves the worst-case time to $O(n)$. A: **Incorrect:** Option A (Only statement 1 is correct.) does not satisfy the conditions derived in the step-by-step analysis for Worst-Case Complexity of QuickSelect vs. FastSelect (Median of Medians) (correct choice: B). B: **Correct:** Option B (Only statement 2 is correct.) matches our derived result under Worst-Case Complexity of QuickSelect vs. FastSelect (Median of Medians). Standard QuickSelect has $O(n)$ average time but $O(n^2)$ worst-case time; Median-of-Medians (FastSelect) improves the worst-case time to $O(n)$. C: **Incorrect:** Option C (Both statements are correct.) does not satisfy the conditions derived in the step-by-step analysis for Worst-Case Complexity of QuickSelect vs. FastSelect (Median of Medians) (correct choice: B). D: **Incorrect:** Option D (Both statements are incorrect.) does not satisfy the conditions derived in the step-by-step analysis for Worst-Case Complexity of QuickSelect vs. FastSelect (Median of Medians) (correct choice: B).

**Answer: 12** **Topic:** Minimum Spanning Trees — *Computing Minimum Spanning Tree Weight via Kruskal's Algorithm* ### Step-by-Step Solution **Step 1:** List the edges of the 7-vertex graph (`s, a, b, c, d, e, f`) in non-decreasing order of weight: 1. $(a, d)$: weight **`1`** (connects `a, d`) 2. $(b, e)$: weight **`1`** (connects `b, e`) 3. $(s, c)$: weight **`2`** (connects `s, c`) 4. $(a, c)$: weight **`2`** (connects `{a, d}` with `{s, c}` $\to \{s, a, c, d\}$) 5. $(f, e)$: weight **`2`** (connects `f` with `{b, e}` $\to \{b, e, f\}$) 6. Next smallest edges: $(s, a)$ has weight `3` (cycle in `{s, a, c, d}` — skip!); $(c, d)$ has weight `3` (cycle in `{s, a, c, d}` — skip!). 7. $(d, e)$: weight **`4`** (connects `{s, a, c, d}` with `{b, e, f}` — now all 7 vertices are connected!). **Step 2:** Sum the weights of the $7 - 1 = 6$ MST edges: $$\text{MST Weight} = 1 + 1 + 2 + 2 + 2 + 4 = 12$$ **Key Takeaway / Tip:** Be careful to skip both weight-3 edges $(s, a)$ and $(c, d)$ because $s, a, c, d$ are already connected via $(a, d)=1, (a, c)=2, (s, c)=2$!

**Answer: 88** **Topic:** Balanced Search Trees — *Minimum Number of Nodes in an AVL Tree of Given Height* ### Step-by-Step Solution **Step 1:** Recall the recurrence relation for the minimum number of nodes $N(h)$ in an AVL tree of height $h$ (given that the empty tree has height $0$, so a single root node has height $1$ and $2$ nodes have height $2$): $$N(0) = 0, \quad N(1) = 1, \quad N(h) = 1 + N(h - 1) + N(h - 2)$$ **Step 2:** Compute $N(h)$ iteratively from $h = 1$ up to $h = 9$: - $N(1) = 1$ - $N(2) = 1 + 1 + 0 = 2$ - $N(3) = 1 + 2 + 1 = 4$ - $N(4) = 1 + 4 + 2 = 7$ - $N(5) = 1 + 7 + 4 = 12$ - $N(6) = 1 + 12 + 7 = 20$ - $N(7) = 1 + 20 + 12 = 33$ - $N(8) = 1 + 33 + 20 = 54$ - $N(9) = 1 + 54 + 33 = 88$ **Step 3:** Therefore, the minimum number of nodes in an AVL tree of height $9$ is **88**. **Key Takeaway / Tip:** Notice the Fibonacci identity: when $N(0) = 0$ and $N(1) = 1$, $N(h) = F_{h+2} - 1$, so $N(9) = F_{11} - 1 = 89 - 1 = 88$!

**Answer: 5** **Topic:** Greedy Algorithms — *Interval Partitioning (Minimum Number of Rooms)* ### Step-by-Step Solution **Step 1:** Recall that the minimum number of rooms required to schedule all activities without overlap equals the **maximum depth (maximum number of simultaneously active intervals)** at any point in time. **Step 2:** Maintain a running counter of active rooms (`+1` at each start event $X_s$, `-1` at each end event $X_e$) across the chronological sequence: `A_s(+1=1), B_s(+1=2), C_s(+1=3), A_e(-1=2), C_e(-1=1), D_s(+1=2), E_s(+1=3), B_e(-1=2), F_s(+1=3), G_s(+1=4), H_s(+1=5), E_e(-1=4), I_s(+1=5), D_e(-1=4), F_e(-1=3), G_e(-1=2), H_e(-1=1), I_e(-1=0)` **Step 3:** Find the peak value reached by the active room counter: - At $H_s$, activities `D, E, F, G, H` are all simultaneously active (**5** rooms). - After $E_e$ and $I_s$, activities `D, F, G, H, I` are all simultaneously active (**5** rooms). **Step 4:** Thus, the minimum number of rooms required is **5**. **Key Takeaway / Tip:** Simply scan the chronological sequence from left to right, adding $1$ for every `s` (start) subscript and subtracting $1$ for every `e` (end) subscript; the maximum running sum is the exact room count ($5$).

**Answer: 136** **Topic:** Divide and Conquer — *Maximum Possible Inversions in an Array of Size n* ### Step-by-Step Solution **Step 1:** In an array $A$ of size $n$, the maximum number of inversion pairs $(i, j)$ with $i < j$ and $A[i] > A[j]$ occurs when the array is sorted in strictly **descending** order. **Step 2:** In a strictly descending array of $n = 17$ elements, **every pair** of indices $(i, j)$ with $0 \le i < j < 17$ forms an inversion: $$\text{Max Inversions} = \binom{17}{2} = \frac{17 \times 16}{2} = 136$$ **Key Takeaway / Tip:** The maximum number of inversions in an array of size $n$ is always $\binom{n}{2} = \frac{n(n-1)}{2}$.

**Answer: A, B** **Topic:** Minimum Spanning Trees — *Minimum-Weight Edge Properties When Weights Are Not Distinct* ### Step-by-Step Solution **Step 1:** Let $w$ be the global minimum edge weight in a connected undirected graph $G$, and let $e$ be a specific edge of weight $w$ (note that multiple edges may share the same minimum weight $w$): - **A is true**: Starting Kruskal's algorithm by picking $e$ first is always safe (by the Cut Property), so **there is at least one MST containing $e$**. - **B is true**: Suppose an MST $T$ does *not* contain $e = (u, v)$. Adding $e$ to $T$ creates a unique cycle $C$ in $T \cup \{e\}$. No edge in $C$ can have weight $< w$ (since $w$ is the global minimum weight in $G$), and no edge in $C \setminus \{e\}$ can have weight $> w$ (otherwise we could swap it with $e$ to get a spanning tree of weight strictly less than $T$, contradicting that $T$ is an MST!). Therefore, **all edges in that cycle must have the exact same weight $w$**. - **C and D are false**: If three edges of weight $w$ form a triangle, any 2 of them can be in an MST while the 3rd is excluded, so $e$ is in *some* MSTs (A) but not necessarily *every* MST (C). **Step 2:** Therefore, **A and B** are true. **Key Takeaway / Tip:** When minimum edge weights are not unique (e.g., a triangle of weight-$w$ edges), a specific minimum-weight edge $e$ belongs to *at least one* MST, and if omitted from some MST $T$, its fundamental cycle in $T$ consists entirely of weight-$w$ edges. A: **Correct:** Option A (

) matches our derived result under Minimum-Weight Edge Properties When Weights Are Not Distinct. When minimum edge weights are not unique (e.g., a triangle of weight-$w$ edges), a specific minimum-weight edge $e$ belongs to *at least one* MST, and if omitted from some MST $T$, its fundamental cycle in $T$ consists entirely of weight-$w$ edges. B: **Correct:** Option B (

) matches our derived result under Minimum-Weight Edge Properties When Weights Are Not Distinct. When minimum edge weights are not unique (e.g., a triangle of weight-$w$ edges), a specific minimum-weight edge $e$ belongs to *at least one* MST, and if omitted from some MST $T$, its fundamental cycle in $T$ consists entirely of weight-$w$ edges. C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for Minimum-Weight Edge Properties When Weights Are Not Distinct (correct choice: A, B). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Minimum-Weight Edge Properties When Weights Are Not Distinct (correct choice: A, B).

**Answer: A, B** **Topic:** Heaps and Priority Queues — *Possible Array Indices of the Maximum Element in a Min-Heap* ### Step-by-Step Solution **Step 1:** In a **min-heap** with $n = 45$ distinct elements (0-indexed from `0` to `44`), every internal node is smaller than its children, so the **largest element must be a leaf node**. **Step 2:** Find the range of internal nodes vs. leaf nodes in a 0-indexed binary heap of size $n = 45$: - The last element is at index $44$, whose parent is at index $\lfloor(44 - 1)/2\rfloor = \lfloor 43 / 2 \rfloor = 21$. - Therefore, indices **`0` to `21`** are **internal nodes** (each has at least one child smaller/larger than it), and indices **`22` to `44`** are **leaf nodes**. **Step 3:** Since the largest element *must* be at a leaf (`A[22]` to `A[44]`), it **cannot** be in: - **A (`A[11]` and `A[21]` inclusive)** — internal nodes! - **B (`A[0]` and `A[10]` inclusive)** — internal nodes! **Step 4:** Therefore, **A and B** are correct. **Key Takeaway / Tip:** In a 0-indexed min-heap of size $n$, all internal nodes occupy indices $0$ through $\lfloor n/2 \rfloor - 1 = 21$, and all leaves occupy indices $\lfloor n/2 \rfloor = 22$ through $n - 1 = 44$. A: **Correct:** Option A (A[11] and A[21] (both inclusive)) matches our derived result under Possible Array Indices of the Maximum Element in a Min-Heap. In a 0-indexed min-heap of size $n$, all internal nodes occupy indices $0$ through $\lfloor n/2 \rfloor - 1 = 21$, and all leaves occupy indices $\lfloor n/2 \rfloor = 22$ through $n - 1 = 44$. B: **Correct:** Option B (A[0] and A[10] (both inclusive)) matches our derived result under Possible Array Indices of the Maximum Element in a Min-Heap. In a 0-indexed min-heap of size $n$, all internal nodes occupy indices $0$ through $\lfloor n/2 \rfloor - 1 = 21$, and all leaves occupy indices $\lfloor n/2 \rfloor = 22$ through $n - 1 = 44$. C: **Incorrect:** Option C (A[31] and A[44] (both inclusive)) does not satisfy the conditions derived in the step-by-step analysis for Possible Array Indices of the Maximum Element in a Min-Heap (correct choice: A, B). D: **Incorrect:** Option D (A[22] and A[30] (both inclusive)) does not satisfy the conditions derived in the step-by-step analysis for Possible Array Indices of the Maximum Element in a Min-Heap (correct choice: A, B).

**Answer: A** **Topic:** Disjoint Set Union — *Tracing Recursive FindSet(u) on a Parent Array* ### Step-by-Step Solution **Step 1:** In the given `FindSet(u)` pseudocode, if `Component[u] == u`, it returns `u`; otherwise it recursively calls `FindSet(Component[u])`. **Step 2:** Trace `FindSet(7)` using the given `Component` table: - `Component[7] = 5` ($\ne 7$) $\implies$ calls `FindSet(5)` - `Component[5] = 4` ($\ne 5$) $\implies$ calls `FindSet(4)` - `Component[4] = 3` ($\ne 4$) $\implies$ calls `FindSet(3)` - `Component[3] = 1` ($\ne 3$) $\implies$ calls `FindSet(1)` - `Component[1] = 1` ($== 1$) $\implies$ base case reached! Returns **`1`**. **Step 3:** Thus, `FindSet(7)` returns **`1`**, which matches **A**. **Key Takeaway / Tip:** Follow the parent pointers `7 -> 5 -> 4 -> 3 -> 1` until you reach the root `1` where `Component[1] == 1`. A: **Correct:** Option A (1) matches our derived result under Tracing Recursive FindSet(u) on a Parent Array. Follow the parent pointers `7 -> 5 -> 4 -> 3 -> 1` until you reach the root `1` where `Component[1] == 1`. B: **Incorrect:** Option B (2) does not satisfy the conditions derived in the step-by-step analysis for Tracing Recursive FindSet(u) on a Parent Array (correct choice: A). C: **Incorrect:** Option C (3) does not satisfy the conditions derived in the step-by-step analysis for Tracing Recursive FindSet(u) on a Parent Array (correct choice: A). D: **Incorrect:** Option D (0) does not satisfy the conditions derived in the step-by-step analysis for Tracing Recursive FindSet(u) on a Parent Array (correct choice: A).

**Answer: D** **Topic:** Greedy Algorithms — *Constructing a Huffman Tree and Computing Codeword Lengths* ### Step-by-Step Solution **Step 1:** Given the 6 characters and their frequencies: `D: 2, B: 5, C: 6, A: 11, E: 12, F: 24`, build the Huffman tree by repeatedly merging the two smallest frequencies: 1. Merge `D(2)` and `B(5)` $\to$ node `DB(7)`. (Remaining: `C:6, DB:7, A:11, E:12, F:24`). 2. Merge `C(6)` and `DB(7)` $\to$ node `CDB(13)`. (Remaining: `A:11, E:12, CDB:13, F:24`). 3. Merge `A(11)` and `E(12)` $\to$ node `AE(23)`. (Remaining: `CDB:13, AE:23, F:24`). 4. Merge `CDB(13)` and `AE(23)` $\to$ node `CDBAE(36)`. (Remaining: `F:24, CDBAE:36`). 5. Merge `F(24)` and `CDBAE(36)` $\to$ Root `(60)`. **Step 2:** Determine the depth (number of bits per character) of each leaf from the Root `(60)`: - **`F`**: child of Root $\implies$ **1 bit** - **`A`, `E`**: children of `AE(23)` under `CDBAE(36)` $\implies$ **3 bits each** - **`C`**: child of `CDB(13)` under `CDBAE(36)` $\implies$ **3 bits** - **`B`, `D`**: children of `DB(7)` under `CDB(13)` under `CDBAE(36)` $\implies$ **4 bits each** **Step 3:** Compute the total bits required to represent the 6-character string `'ABCDEF'` (where each character `A, B, C, D, E, F` appears **once**): $$\text{Bits('ABCDEF')} = L(A) + L(B) + L(C) + L(D) + L(E) + L(F) = 3 + 4 + 3 + 4 + 3 + 1 = 18\text{ bits}$$ which matches **D** (`18 bits`). **Key Takeaway / Tip:** Read the question carefully: it asks for the number of bits to encode the 6-letter string `'ABCDEF'` (sum of codeword lengths $3+4+3+4+3+1 = 18$), not the weighted total over all frequencies! A: **Incorrect:** Option A (15 bits) does not satisfy the conditions derived in the step-by-step analysis for Constructing a Huffman Tree and Computing Codeword Lengths (correct choice: D). B: **Incorrect:** Option B (16 bits) does not satisfy the conditions derived in the step-by-step analysis for Constructing a Huffman Tree and Computing Codeword Lengths (correct choice: D). C: **Incorrect:** Option C (17 bits) does not satisfy the conditions derived in the step-by-step analysis for Constructing a Huffman Tree and Computing Codeword Lengths (correct choice: D). D: **Correct:** Option D (18 bits       **Appdev1** **Section Id :** 64065373858 **Section Number :** 4 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :** 16 **Numb...) matches our derived result under Constructing a Huffman Tree and Computing Codeword Lengths. Read the question carefully: it asks for the number of bits to encode the 6-letter string `'ABCDEF'` (sum of codeword lengths $3+4+3+4+3+1 = 18$), not the weighted total over all frequencies!