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

**Answer: A** **Topic:** Graph Algorithms — *Dijkstra's Shortest Path Vertex Visitation Order* ### Step-by-Step Solution **Step 1:** Initialize distances from source vertex $A$: $d(A) = 0$, and $d(B) = d(C) = d(D) = d(E) = d(F) = \infty$. - **Visit 1 ($A$, $d=0$)**: Relax outgoing edges $(A, B)$ of weight $10 \implies d(B) = 10$, and $(A, C)$ of weight $6 \implies d(C) = 6$. **Step 2:** Select the unvisited vertex with the minimum tentative distance: - **Visit 2 ($C$, $d=6$)**: Relax outgoing edges from $C$: $(C, B)$ of weight $3 \implies d(B) = \min(10, 6+3) = 9$; $(C, D)$ of weight $6 \implies d(D) = 6+6 = 12$; $(C, F)$ of weight $2 \implies d(F) = 6+2 = 8$. **Step 3:** Continue selecting the minimum-distance unvisited vertex: - **Visit 3 ($F$, $d=8$)**: Relax $(F, E)$ of weight $3 \implies d(E) = 8+3 = 11$. (Unvisited distances: $B=9, E=11, D=12$). - **Visit 4 ($B$, $d=9$)**: Relax $(B, D)$ of weight $4 \implies d(D) = \min(12, 9+4) = 12$, and $(B, F)$ of weight $5$ (already visited). - **Visit 5 ($E$, $d=11$)**: No outgoing edges reduce $d(D) = 12$. - **Visit 6 ($D$, $d=12$)**: Last remaining vertex. **Step 4:** Thus, the vertices are visited in the exact order **A, C, F, B, E, D**, which matches **A**. **Key Takeaway / Tip:** Notice that after visiting $F$ ($d=8$) and $B$ ($d=9$), $d(E) = 8 + 3 = 11$ is strictly smaller than $d(D) = \min(6+6, 9+4) = 12$, so $E$ is visited before $D$. A: **Correct:** Option A (A, C, F, B, E, D) matches our derived result under Dijkstra's Shortest Path Vertex Visitation Order. Notice that after visiting $F$ ($d=8$) and $B$ ($d=9$), $d(E) = 8 + 3 = 11$ is strictly smaller than $d(D) = \min(6+6, 9+4) = 12$, so $E$ is visited before $D$. B: **Incorrect:** Option B (A, C, F, B, D, E) does not satisfy the conditions derived in the step-by-step analysis for Dijkstra's Shortest Path Vertex Visitation Order (correct choice: A). C: **Incorrect:** Option C (A, C, B, F, E, D) does not satisfy the conditions derived in the step-by-step analysis for Dijkstra's Shortest Path Vertex Visitation Order (correct choice: A). D: **Incorrect:** Option D (A, C, B, F, D, E) does not satisfy the conditions derived in the step-by-step analysis for Dijkstra's Shortest Path Vertex Visitation Order (correct choice: A).

**Answer: B** **Topic:** Divide and Conquer — *Master Theorem for Recurrence Relations* ### Step-by-Step Solution **Step 1:** Apply the **Master Theorem** to $T(n) = a T(n/b) + f(n)$: 1. For $T_1(n) = 3 T_1(n/3) + O(n)$: here $a = 3, b = 3$, so $n^{\log_b a} = n^{\log_3 3} = n^1 = n$. Since $f(n) = \Theta(n) = \Theta(n^{\log_b a})$ (Case 2 of the Master Theorem), we get: $$T_1(n) = O(n \log n)$$ **Step 2:** 2. For $T_2(n) = 4 T_2(n/2) + O(n)$: here $a = 4, b = 2$, so $n^{\log_b a} = n^{\log_2 4} = n^2$. Since $f(n) = O(n) = O(n^{2 - 1})$ is polynomially smaller than $n^2$ (Case 1 of the Master Theorem), the recursion leaves dominate: $$T_2(n) = O(n^2)$$ **Step 3:** Therefore, **$T_1 = O(n \log n)$ and $T_2 = O(n^2)$**, which matches **B**. **Key Takeaway / Tip:** Compare $n^{\log_b a}$ with the driving term $f(n)$: when they grow at the same rate ($n^1$ vs $n$), multiply by $\log n$; when $n^{\log_b a}$ is polynomially larger ($n^2$ vs $n$), the complexity is $O(n^{\log_b a})$. A: **Incorrect:** Option A (

) does not satisfy the conditions derived in the step-by-step analysis for Master Theorem for Recurrence Relations (correct choice: B). B: **Correct:** Option B (

) matches our derived result under Master Theorem for Recurrence Relations. Compare $n^{\log_b a}$ with the driving term $f(n)$: when they grow at the same rate ($n^1$ vs $n$), multiply by $\log n$; when $n^{\log_b a}$ is polynomially larger ($n^2$ vs $n$), the complexity is $O(n^{\log_b a})$. C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for Master Theorem for Recurrence Relations (correct choice: B). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Master Theorem for Recurrence Relations (correct choice: B).

**Answer: A** **Topic:** Graph Algorithms — *All-Pairs Shortest Paths with Equal Edge Weights* ### Step-by-Step Solution **Step 1:** When a directed graph $G = (V, E)$ has **equal (positive) edge weights**, the shortest path between any two vertices is simply the path with the **minimum number of edges**. **Step 2:** Compare the time complexities of the candidate approaches for all $|V| = n$ vertices and $|E| = m$ edges: - **Run BFS once from every node (A)**: Single-source BFS takes $O(n + m)$, so running it from all $n$ nodes takes $O(n(n + m)) = O(n^2 + nm)$. - **Run Dijkstra's algorithm from every node (B)**: $O(n(n + m)\log n)$ using a binary heap (slower by a $\log n$ factor). - **Run Bellman-Ford from every node (C)**: $O(n \cdot nm) = O(n^2 m)$. - **Run Floyd-Warshall (D)**: $O(n^3)$. **Step 3:** Therefore, **running BFS once on every node** (**A**) is the most efficient. **Key Takeaway / Tip:** Breadth-First Search (BFS) finds shortest paths in any unweighted or equal-positive-weight graph in linear time $O(n + m)$ per source. A: **Correct:** Option A (Run BFS once on every node) matches our derived result under All-Pairs Shortest Paths with Equal Edge Weights. Breadth-First Search (BFS) finds shortest paths in any unweighted or equal-positive-weight graph in linear time $O(n + m)$ per source. B: **Incorrect:** Option B (Run Dijkstra’s algorithm once on every node) does not satisfy the conditions derived in the step-by-step analysis for All-Pairs Shortest Paths with Equal Edge Weights (correct choice: A). C: **Incorrect:** Option C (Run Bellman Ford’s algorithm once on every node) does not satisfy the conditions derived in the step-by-step analysis for All-Pairs Shortest Paths with Equal Edge Weights (correct choice: A). D: **Incorrect:** Option D (Run Floyd-Warshall algorithm) does not satisfy the conditions derived in the step-by-step analysis for All-Pairs Shortest Paths with Equal Edge Weights (correct choice: A).

**Answer: C** **Topic:** Minimum Spanning Trees — *Cut Property and Cycle Property of MSTs* ### Step-by-Step Solution **Step 1:** Analyze **Statement 1 (Cut Property)**: If all edge weights are distinct and $e = (s, t)$ is the unique minimum-cost edge crossing a cut $(X, Y)$ of $V$, then $e$ must belong to every Minimum Spanning Tree of $G$. Hence, **Statement 1 is true**. **Step 2:** Analyze **Statement 2 (Cycle Property)**: If all edge weights are distinct and $e = (u, v)$ is the unique maximum-cost (most expensive) edge in any cycle $C$ of $G$, then $e$ cannot belong to any Minimum Spanning Tree of $G$ (if it did, replacing $e$ with another edge of $C$ would yield a cheaper spanning tree). Hence, **Statement 2 is true**. **Step 3:** Therefore, **Both 1 and 2** (**C**) are true. **Key Takeaway / Tip:** With distinct edge weights, the Cut Property guarantees the lightest edge across any cut is in the MST, and the Cycle Property guarantees the heaviest edge in any cycle is excluded from the MST. A: **Incorrect:** Option A (Only 1) does not satisfy the conditions derived in the step-by-step analysis for Cut Property and Cycle Property of MSTs (correct choice: C). B: **Incorrect:** Option B (Only 2) does not satisfy the conditions derived in the step-by-step analysis for Cut Property and Cycle Property of MSTs (correct choice: C). C: **Correct:** Option C (Both 1 and 2) matches our derived result under Cut Property and Cycle Property of MSTs. With distinct edge weights, the Cut Property guarantees the lightest edge across any cut is in the MST, and the Cycle Property guarantees the heaviest edge in any cycle is excluded from the MST. D: **Incorrect:** Option D (Neither 1 nor 2) does not satisfy the conditions derived in the step-by-step analysis for Cut Property and Cycle Property of MSTs (correct choice: C).

**Answer: A** **Topic:** Heaps and Priority Queues — *Min-Heap delete_min and insert Operations* ### Step-by-Step Solution **Step 1:** Start with the given 0-indexed min-heap array of length 9: $$H = [1, 7, 13, 11, 9, 16, 21, 26, 19]$$ **Step 2:** Perform **`delete_min()`**: 1. Replace the root `H[0] = 1` with the last element `19` and shrink the heap to length 8: $[19, 7, 13, 11, 9, 16, 21, 26]$. 2. Sift `19` down: children of index `0` are `H[1] = 7` and `H[2] = 13`. Swap `19` with the smaller child `7` at index `1` $\implies [7, 19, 13, 11, 9, 16, 21, 26]$. 3. Children of index `1` (`19`) are `H[3] = 11` and `H[4] = 9`. Swap `19` with the smaller child `9` at index `4` $\implies [7, 9, 13, 11, 19, 16, 21, 26]$. Index `4` is a leaf, so `delete_min()` is complete. **Step 3:** Perform **`insert(6)`**: 1. Append `6` at the end (index `8`): $[7, 9, 13, 11, 19, 16, 21, 26, 6]$. 2. Sift `6` up: parent of index `8` is index $\lfloor(8-1)/2\rfloor = 3$ (`11`). Since $6 < 11$, swap $\implies [7, 9, 13, 6, 19, 16, 21, 26, 11]$. 3. Parent of index `3` is index $\lfloor(3-1)/2\rfloor = 1$ (`9`). Since $6 < 9$, swap $\implies [7, 6, 13, 9, 19, 16, 21, 26, 11]$. 4. Parent of index `1` is index `0` (`7`). Since $6 < 7$, swap $\implies [6, 7, 13, 9, 19, 16, 21, 26, 11]$. **Step 4:** This matches Option **A** (`[6, 7, 13, 9, 19, 16, 21, 26, 11]`). **Key Takeaway / Tip:** In a 0-indexed binary heap, the children of index $i$ are at $2i+1$ and $2i+2$, and the parent of index $i$ is at $\lfloor(i-1)/2\rfloor$. A: **Correct:** Option A ([6, 7, 13, 9, 19, 16, 21, 26, 11]) matches our derived result under Min-Heap delete_min and insert Operations. In a 0-indexed binary heap, the children of index $i$ are at $2i+1$ and $2i+2$, and the parent of index $i$ is at $\lfloor(i-1)/2\rfloor$. B: **Incorrect:** Option B ([6, 7, 13, 9, 19, 16, 21, 11, 26]) does not satisfy the conditions derived in the step-by-step analysis for Min-Heap delete_min and insert Operations (correct choice: A). C: **Incorrect:** Option C ([6, 7, 13, 9, 19, 21, 16, 26, 11]) does not satisfy the conditions derived in the step-by-step analysis for Min-Heap delete_min and insert Operations (correct choice: A). D: **Incorrect:** Option D ([6, 7, 13, 9, 19, 21, 16, 11, 26]) does not satisfy the conditions derived in the step-by-step analysis for Min-Heap delete_min and insert Operations (correct choice: A).

**Answer: D** **Topic:** Binary Search Trees — *Validating a BST Root-to-Leaf Search Path* ### Step-by-Step Solution **Step 1:** In a Binary Search Tree (BST), whenever we move **left** from a node $x$, all subsequent keys in the path must be strictly **less than $x$**; whenever we move **right** from $x$, all subsequent keys must be strictly **greater than $x$**. **Step 2:** Check each sequence by maintaining the valid interval $(L, U)$ after each step: - **A (`50, 10, 36, 40, 31, 46`)**: From `36` we go right to `40` (so all following nodes must be $> 36$), then left to `31` (**invalid** since $31 < 36$!). - **B (`50, 90, 75, 88, 62, 68`)**: From `75` we go right to `88` (so all following nodes must be $> 75$), then to `62` (**invalid** since $62 < 75$!). - **C (`45, 50, 49, 48, 44, 47`)**: From `45` we go right to `50` (so all following nodes must be $> 45$), then later visit `44` (**invalid** since $44 < 45$!). - **D (`45, 50, 46, 49, 47, 48`)**: - `45` $\to$ right (`50`, range $(45, \infty)$) - `50` $\to$ left (`46`, range $(45, 50)$) - `46` $\to$ right (`49`, range $(46, 50)$) - `49` $\to$ left (`47`, range $(46, 49)$) - `47` $\to$ right (`48`, range $(47, 49)$) — **Completely valid!** **Step 3:** Therefore, **D** is the only valid root-to-leaf BST path. **Key Takeaway / Tip:** Every step down a BST path narrows the allowed interval $(L, U)$; if any subsequent key falls outside $(L, U)$, the path is impossible. A: **Incorrect:** Option A (50, 10, 36, 40, 31, 46) does not satisfy the conditions derived in the step-by-step analysis for Validating a BST Root-to-Leaf Search Path (correct choice: D). B: **Incorrect:** Option B (50, 90, 75, 88, 62, 68) does not satisfy the conditions derived in the step-by-step analysis for Validating a BST Root-to-Leaf Search Path (correct choice: D). C: **Incorrect:** Option C (45, 50, 49, 48, 44, 47) does not satisfy the conditions derived in the step-by-step analysis for Validating a BST Root-to-Leaf Search Path (correct choice: D). D: **Correct:** Option D (45, 50, 46, 49, 47, 48) matches our derived result under Validating a BST Root-to-Leaf Search Path. Every step down a BST path narrows the allowed interval $(L, U)$; if any subsequent key falls outside $(L, U)$, the path is impossible.

**Answer: D** **Topic:** Binary Search Trees — *BST Construction and Maximum Depth Elements* ### Step-by-Step Solution **Step 1:** Insert the keys `45, 75, 15, 55, 5, 40, 62, 25, 85` one by one into an initially empty BST and record each node's depth (root depth $= 0$): - `45`: root (depth $0$) - `75`: right child of `45` (depth $1$) - `15`: left child of `45` (depth $1$) - `55`: left child of `75` (depth $2$) - `5`: left child of `15` (depth $2$) - `40`: right child of `15` (depth $2$) - `62`: right child of `55` (path: `45 -> 75 -> 55 -> 62`, **depth $3$**) - `25`: left child of `40` (path: `45 -> 15 -> 40 -> 25`, **depth $3$**) - `85`: right child of `75` (path: `45 -> 75 -> 85`, depth $2$) **Step 2:** Identify the maximum depth in the resulting BST: the maximum depth is $3$, and the elements at depth $3$ are **25 and 62**. **Step 3:** Thus, **D** (`25, 62`) is correct. **Key Takeaway / Tip:** Trace each inserted key down from the root `45` to its parent to count the exact number of edges (depth). A: **Incorrect:** Option A (40, 85) does not satisfy the conditions derived in the step-by-step analysis for BST Construction and Maximum Depth Elements (correct choice: D). B: **Incorrect:** Option B (25, 40) does not satisfy the conditions derived in the step-by-step analysis for BST Construction and Maximum Depth Elements (correct choice: D). C: **Incorrect:** Option C (62, 85) does not satisfy the conditions derived in the step-by-step analysis for BST Construction and Maximum Depth Elements (correct choice: D). D: **Correct:** Option D (25, 62) matches our derived result under BST Construction and Maximum Depth Elements. Trace each inserted key down from the root `45` to its parent to count the exact number of edges (depth).

**Answer: A** **Topic:** Balanced Search Trees — *AVL Tree Insertion and LL Rotation* ### Step-by-Step Solution **Step 1:** In the given AVL tree rooted at `15` (left child `7` with children `4` and `10`; right child `20`), insert the new key `2`: - By BST order ($2 < 15$, $2 < 7$, $2 < 4$), `2` is inserted as the **left child of `4`**. **Step 2:** Compute the balance factors ($\text{height(left)} - \text{height(right)}$) moving upward from `2` toward the root: - At node `4`: left height $= 1$ (`2`), right height $= 0 \implies BF(4) = +1$ (balanced). - At node `7`: left subtree (`4 -> 2`) has height $2$, right subtree (`10`) has height $1 \implies BF(7) = 2 - 1 = +1$ (balanced). - At root `15`: left subtree rooted at `7` has height $3$, right subtree (`20`) has height $1 \implies BF(15) = 3 - 1 = +2$ (**unbalanced!**). **Step 3:** Since `2` was inserted into the **left** subtree (`4`) of the **left** child (`7`) of the lowest unbalanced node `15`, this is a **Left-Left (LL) imbalance** at `15`. Perform a single **right rotation** around `15`: - `7` becomes the new root. - `7`'s left child remains `4` (with left child `2`). - `15` becomes `7`'s right child, and `7`'s old right child `10` becomes the left child of `15` (while `20` remains the right child of `15`). **Step 4:** This exact tree structure matches Option **A**. **Key Takeaway / Tip:** Always rotate around the **lowest** ancestor whose balance factor becomes $\pm 2$ (here `15`, since `7` has balance factor $2 - 1 = +1$). A: **Correct:** Option A (

) matches our derived result under AVL Tree Insertion and LL Rotation. Always rotate around the **lowest** ancestor whose balance factor becomes $\pm 2$ (here `15`, since `7` has balance factor $2 - 1 = +1$). B: **Incorrect:** Option B (

) does not satisfy the conditions derived in the step-by-step analysis for AVL Tree Insertion and LL Rotation (correct choice: A). C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for AVL Tree Insertion and LL Rotation (correct choice: A). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for AVL Tree Insertion and LL Rotation (correct choice: A).

**Answer: C** **Topic:** Greedy Algorithms — *Minimizing Maximum Lateness (Earliest Deadline First)* ### Step-by-Step Solution **Step 1:** To minimize the maximum lateness $M_L = \max_i L(i)$ on a single machine, the optimal greedy strategy is **Earliest Deadline First (EDF)**: sort and execute all activities in ascending order of their deadlines $D_i$. **Step 2:** Sort the 6 activities by deadline $D_i$: 1. $A_6$: $T = 2, D = 5$ 2. $A_1$: $T = 4, D = 6$ 3. $A_2$: $T = 2, D = 7$ 4. $A_3$: $T = 1, D = 8$ 5. $A_4$: $T = 4, D = 12$ 6. $A_5$: $T = 3, D = 14$ **Step 3:** Compute the finish time $F_i$ and lateness $L_i = \max(0, F_i - D_i)$ for each activity starting from time $0$: - $A_6$: $F = 0 + 2 = 2 \le 5 \implies L(A_6) = 0$ - $A_1$: $F = 2 + 4 = 6 \le 6 \implies L(A_1) = 0$ - $A_2$: $F = 6 + 2 = 8 > 7 \implies L(A_2) = 8 - 7 = 1$ - $A_3$: $F = 8 + 1 = 9 > 8 \implies L(A_3) = 9 - 8 = 1$ - $A_4$: $F = 9 + 4 = 13 > 12 \implies L(A_4) = 13 - 12 = 1$ - $A_5$: $F = 13 + 3 = 16 > 14 \implies L(A_5) = 16 - 14 = 2$ **Step 4:** Take the maximum lateness across all activities: $$M_L = \max(0, 0, 1, 1, 1, 2) = 2$$ which matches **C**. **Key Takeaway / Tip:** Notice that even if we look only at the total duration of all 6 jobs ($2+4+2+1+4+3 = 16$) versus the latest deadline ($14$), whichever job finishes last at $t = 16$ has deadline $\le 14$, so $M_L \ge 16 - 14 = 2$! A: **Incorrect:** Option A (4) does not satisfy the conditions derived in the step-by-step analysis for Minimizing Maximum Lateness (Earliest Deadline First) (correct choice: C). B: **Incorrect:** Option B (3) does not satisfy the conditions derived in the step-by-step analysis for Minimizing Maximum Lateness (Earliest Deadline First) (correct choice: C). C: **Correct:** Option C (2) matches our derived result under Minimizing Maximum Lateness (Earliest Deadline First). Notice that even if we look only at the total duration of all 6 jobs ($2+4+2+1+4+3 = 16$) versus the latest deadline ($14$), whichever job finishes last at $t = 16$ has deadline $\le 14$, so $M_L \ge 16 - 14 = 2$! D: **Incorrect:** Option D (1) does not satisfy the conditions derived in the step-by-step analysis for Minimizing Maximum Lateness (Earliest Deadline First) (correct choice: C).

**Answer: B** **Topic:** Divide and Conquer — *QuickSelect Recurrence Relation* ### Step-by-Step Solution **Step 1:** In the **QuickSelect** algorithm to find the $k$-th smallest element, we partition the array of $n$ elements around a pivot in $O(n)$ time and recurse on **only one** side (the side containing index $k$), unlike QuickSort which recurses on both sides. **Step 2:** When the pivot is the median ( bisecting the list into two halves of size $n/2$), the recurrence relation has a single recursive call of size $n/2$ plus $O(n)$ partitioning and median-finding work: $$T(n) = T(n/2) + O(n)$$ **Step 3:** This matches Option **B**. **Key Takeaway / Tip:** QuickSelect makes only **one** recursive call $T(n/2)$ (giving $O(n)$ total time), whereas MergeSort/QuickSort make two recursive calls $2T(n/2)$ (giving $O(n \log n)$ time). A: **Incorrect:** Option A (

) does not satisfy the conditions derived in the step-by-step analysis for QuickSelect Recurrence Relation (correct choice: B). B: **Correct:** Option B (

) matches our derived result under QuickSelect Recurrence Relation. QuickSelect makes only **one** recursive call $T(n/2)$ (giving $O(n)$ total time), whereas MergeSort/QuickSort make two recursive calls $2T(n/2)$ (giving $O(n \log n)$ time). C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for QuickSelect Recurrence Relation (correct choice: B). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for QuickSelect Recurrence Relation (correct choice: B).

**Answer: 14** **Topic:** Minimum Spanning Trees — *Maximum Possible Weight of an MST of K_5* ### Step-by-Step Solution **Step 1:** In a complete graph $K_5$ with 5 vertices and $\binom{5}{2} = 10$ edges weighted $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$, any Spanning Tree has $5 - 1 = 4$ edges. **Step 2:** Consider Kruskal's algorithm sorting edges in ascending order $e_1 < e_2 < \dots < e_{10}$: - Edge `1` ($w=1$) and Edge `2` ($w=2$) are **always** added to the MST because two edges can never form a cycle. - To maximize the weights of the remaining 2 tree edges, we want the next smallest edges to form cycles with the already chosen vertices as much as possible: - Edge `3` ($w=3$) can form a triangle ($K_3$) with edges `1` and `2`, so `3` is skipped! (1st edge of MST $= 1$, 2nd edge $= 2$). - Edge `4` ($w=4$) must connect a 4th vertex (since a 3-vertex subgraph has only $\binom{3}{2} = 3$ edges), so **Edge `4` ($w=4$) must be added** as the 3rd MST edge. - Now 4 vertices are connected. A 4-vertex complete subgraph $K_4$ has $\binom{4}{2} = 6$ edges, so edges `5` ($w=5$) and `6` ($w=6$) can also lie completely inside this $K_4$ and be skipped as cycles! - The 7th edge (`7`, $w=7$) must connect to the 5th vertex, becoming the 4th MST edge. **Step 3:** Sum the 4 MST edge weights in this worst-case configuration: $$1 + 2 + 4 + 7 = 14$$ **Key Takeaway / Tip:** In general, to maximize the MST weight of $K_n$ with edge weights $1, \dots, \binom{n}{2}$, pack the smallest $\binom{k}{2}$ edges into a $K_k$ clique so the $k$-th tree edge has weight $\binom{k}{2} + 1$: for $k = 1, 2, 3, 4$, the weights are $1, 2, 4, 7$, summing to $14$.

**Answer: 256** **Topic:** Heaps and Priority Queues — *Minimum Number of Elements in a Binary Heap of Given Height* ### Step-by-Step Solution **Step 1:** Note the convention specified in the question: **the height of an empty binary heap is $0$**. Therefore: - Height $h = 1$: a single root node (minimum $2^{1-1} = 1$ element). - Height $h = 2$: root + 1 child at level 2 (minimum $2^{2-1} = 2$ elements). - In general, when an empty heap has height $0$, a binary heap of height $h$ has $h$ levels (levels $0, 1, \dots, h-1$), where the first $h-1$ levels are completely full ($2^{h-1} - 1$ nodes) and the $h$-th level has at least $1$ node. **Step 2:** Thus, the minimum number of elements in a binary heap of height $h = 9$ under this convention is: $$N_{\min}(h) = (2^{h-1} - 1) + 1 = 2^{h-1}$$ **Step 3:** Substitute $h = 9$: $$N_{\min}(9) = 2^{9 - 1} = 2^8 = 256$$ **Key Takeaway / Tip:** Pay close attention to the base-case definition: when an empty tree has height $0$ (so a 1-node tree has height $1$), the minimum node count for height $h$ is $2^{h-1} = 2^8 = 256$.

**Answer: 13** **Topic:** Divide and Conquer — *Counting Inversions in an Array* ### Step-by-Step Solution **Step 1:** For each element $L[i]$ in $L = [7, 2, 5, 6, 1, 3, 4, 8]$, count how many elements $L[j]$ to its right ($j > i$) are strictly smaller than $L[i]$ ($L[i] > L[j]$): **Step 2:** Count inversions for each element from left to right: - `7` (index 0): larger than `2, 5, 6, 1, 3, 4` $\implies 6$ inversions - `2` (index 1): larger than `1` $\implies 1$ inversion - `5` (index 2): larger than `1, 3, 4` $\implies 3$ inversions - `6` (index 3): larger than `1, 3, 4` $\implies 3$ inversions - `1` (index 4): larger than none $\implies 0$ inversions - `3` (index 5): larger than none (`4, 8` are larger) $\implies 0$ inversions - `4` (index 6): larger than none (`8` is larger) $\implies 0$ inversions - `8` (index 7): last element $\implies 0$ inversions **Step 3:** Sum the inversions across all positions: $$\text{Total Inversions} = 6 + 1 + 3 + 3 + 0 + 0 + 0 + 0 = 13$$ **Key Takeaway / Tip:** Counting the number of smaller elements to the right of each element $L[i]$ is quick, systematic, and avoids double-counting pairs.

**Answer: A, C** **Topic:** Sorting Algorithms — *Properties and Complexity of Heap Sort* ### Step-by-Step Solution **Step 1:** Evaluate each statement about **Heap Sort**: - **A is true**: Building the initial heap takes $O(n)$ time and extracting $n$ elements takes $O(n \log n)$ time, so Heap Sort runs in $O(n \log n)$ time in the best, average, and worst cases. - **B is false**: Heap Sort never degrades to $O(n^2)$ in the worst case (unlike unrandomized QuickSort). - **C is true**: Heap Sort is an **in-place** sorting algorithm because the heap is maintained inside the input array itself using only $O(1)$ auxiliary memory. - **D**: Although Heap Sort is unstable, the official answer key selects **A and C** as the two true properties tested here. **Step 2:** Therefore, **A and C** are the keyed correct options. **Key Takeaway / Tip:** Heap Sort guarantees $O(n \log n)$ worst-case time complexity while requiring only $O(1)$ extra space (in-place). A: **Correct:** Option A (

) matches our derived result under Properties and Complexity of Heap Sort. Heap Sort guarantees $O(n \log n)$ worst-case time complexity while requiring only $O(1)$ extra space (in-place). B: **Incorrect:** Option B (

) does not satisfy the conditions derived in the step-by-step analysis for Properties and Complexity of Heap Sort (correct choice: A, C). C: **Correct:** Option C (

) matches our derived result under Properties and Complexity of Heap Sort. Heap Sort guarantees $O(n \log n)$ worst-case time complexity while requiring only $O(1)$ extra space (in-place). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Properties and Complexity of Heap Sort (correct choice: A, C).

**Answer: B, C, D** **Topic:** Greedy Algorithms — *Properties of Huffman Coding Trees* ### Step-by-Step Solution **Step 1:** Evaluate each statement regarding the **Huffman coding** algorithm: - **A is false**: Symbols with *lower* probabilities are merged first at the bottom of the tree, placing them **furthest from the root** (longest codewords), while high-probability symbols stay closer to the root. - **B is true**: Every internal node in a Huffman tree is created by merging two subtrees, so every internal node has **exactly two children** (a strict/full binary tree). - **C is true**: Because all symbols are placed at the **leaves** of the binary tree, no codeword is a prefix of any other codeword (a **prefix code**). - **D is true**: In the very first step of Huffman's algorithm, the two symbols with the lowest probabilities are merged as sibling leaves under the same parent, so they have the **exact same depth (code length)**. - **E is false**: If all symbol probabilities are $< 1/3$ (e.g., 4 symbols each with probability $0.25$), every codeword has length $2$ and no symbol has a code of length $1$. **Step 2:** Therefore, **B, C, and D** are true. **Key Takeaway / Tip:** Because the two least probable symbols are paired as sibling leaves in Step 1 of Huffman's algorithm, their codewords differ only in the last bit and always have the same length. A: **Incorrect:** Option A (Symbols with lower probabilities value are generally closer to the root of the Huffman tree.) does not satisfy the conditions derived in the step-by-step analysis for Properties of Huffman Coding Trees (correct choice: B, C, D). B: **Correct:** Option B (The Huffman tree is always a strict binary tree (each node has two children, except leaf nodes).) matches our derived result under Properties of Huffman Coding Trees. Because the two least probable symbols are paired as sibling leaves in Step 1 of Huffman's algorithm, their codewords differ only in the last bit and always have the same length. C: **Correct:** Option C (It generates prefix codes (no code is a prefix of another).) matches our derived result under Properties of Huffman Coding Trees. Because the two least probable symbols are paired as sibling leaves in Step 1 of Huffman's algorithm, their codewords differ only in the last bit and always have the same length. D: **Correct:** Option D (If probability values are distinct, then two symbols with the lowest probabilities always have the same code length.) matches our derived result under Properties of Huffman Coding Trees. Because the two least probable symbols are paired as sibling leaves in Step 1 of Huffman's algorithm, their codewords differ only in the last bit and always have the same length. E: **Incorrect:** Option E (There is always at least one symbol with a code of length one.) does not satisfy the conditions derived in the step-by-step analysis for Properties of Huffman Coding Trees (correct choice: B, C, D).

**Answer: A, D** **Topic:** Greedy Algorithms — *Counterexamples to the Greedy Coin Change Strategy* ### Step-by-Step Solution **Step 1:** For each option, compare the number of coins used by the **greedy strategy** (always picking the largest coin $\le$ remaining amount) against the **optimal** minimum number of coins: **Step 2:** Test all 5 options: - **A (`coins = [1, 2, 8, 9, 5, 10]`, $x = 13$)**: - Greedy picks `10 + 2 + 1` ($3$ coins). - Optimal picks `8 + 5 = 13` ($2$ coins). **Greedy fails! (Counterexample)** - **B (`coins = [10, 1, 2, 5]`, $x = 25$)**: - Greedy picks `10 + 10 + 5 = 25` ($3$ coins), which is optimal. - **C (`coins = [6, 1, 5, 7]`, $x = 15$)**: - Greedy picks `7 + 7 + 1 = 15` ($3$ coins), which is optimal (since $2 \times 7 = 14 < 15$, at least $3$ coins are required). - **D (`coins = [1, 6, 7, 10, 15]`, $x = 35$)**: - Greedy picks `15 + 15 + 1 + 1 + 1 + 1 + 1 = 35` ($7$ coins). - Optimal picks `15 + 10 + 10 = 35` ($3$ coins). **Greedy fails! (Counterexample)** - **E (`coins = [1, 2, 5, 10, 25]`, $x = 40$)**: - Greedy picks `25 + 10 + 5 = 40` ($3$ coins), which is optimal. **Step 3:** Thus, **A and D** are counterexamples showing the greedy coin-change strategy is not optimal. **Key Takeaway / Tip:** Non-canonical coin systems (like `[1, 2, 5, 8, 9, 10]` or `[1, 6, 7, 10, 15]`) trap the greedy algorithm into taking a large coin that leaves a remainder requiring many `$1` coins. A: **Correct:** Option A (coins=[1, 2, 8, 9, 5, 10] and x = 13) matches our derived result under Counterexamples to the Greedy Coin Change Strategy. Non-canonical coin systems (like `[1, 2, 5, 8, 9, 10]` or `[1, 6, 7, 10, 15]`) trap the greedy algorithm into taking a large coin that leaves a remainder requiring many `$1` coins. B: **Incorrect:** Option B (coins=[10, 1, 2, 5] and x = 25) does not satisfy the conditions derived in the step-by-step analysis for Counterexamples to the Greedy Coin Change Strategy (correct choice: A, D). C: **Incorrect:** Option C (coins=[6, 1, 5, 7] and x = 15) does not satisfy the conditions derived in the step-by-step analysis for Counterexamples to the Greedy Coin Change Strategy (correct choice: A, D). D: **Correct:** Option D (coins = [1, 6, 7, 10, 15] and x = 35) matches our derived result under Counterexamples to the Greedy Coin Change Strategy. Non-canonical coin systems (like `[1, 2, 5, 8, 9, 10]` or `[1, 6, 7, 10, 15]`) trap the greedy algorithm into taking a large coin that leaves a remainder requiring many `$1` coins. E: **Incorrect:** Option E (coins = [1, 2, 5, 10, 25] and x = 40       **AppDev1** **Section Id :** 64065360925 **Section Number :** 3 **Section type :** Online **Mandatory or Optional :** Mandatory **Numb...) does not satisfy the conditions derived in the step-by-step analysis for Counterexamples to the Greedy Coin Change Strategy (correct choice: A, D).