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

In the **Floyd-Warshall** all-pairs shortest path algorithm, the diagonal entry \(D[i][i]\) represents the shortest path distance from vertex \(i\) back to itself. Initially, \(D[i][i] = 0\). If \(D[i][i] < 0\) after running the algorithm, it means there exists a directed cycle passing through vertex \(i\) whose total edge weight is negative—that is, **the graph has a negative-weight cycle**. **Answer: A (The graph has a negative-weight cycle.)** A: **Correct:** A negative entry on the diagonal \(D[i][i] < 0\) indicates a path from vertex \(i\) to itself with total weight less than 0, which is a negative-weight cycle. B: **Incorrect:** Negative-weight edges without a negative cycle cannot reduce the distance from a vertex back to itself below 0. C: **Incorrect:** In an acyclic graph (DAG), no vertex can reach itself via a non-empty path, so \(D[i][i]\) remains 0. D: **Incorrect:** Disconnected components leave distances between unreachable vertices as \(+\infty\), not negative diagonal values.

**Step 1: Initialize distances from source vertex `P` and trace Dijkstra's algorithm.** - **Step 1 (Visit `P`, dist = 0)**: - Outgoing edges from `P`: `P -> Q` (weight 1), `P -> S` (weight 6), `P -> T` (weight 7). - Tentative distances: `d[Q] = 1`, `d[S] = 6`, `d[T] = 7`, `d[R] = inf`, `d[U] = inf`. - **Step 2 (Visit `Q`, dist = 1)**: - Outgoing edges from `Q`: `Q -> R` (weight 1 \(\implies d[R] = 1 + 1 = 2\)), `Q -> S` (weight 4 \(\implies d[S] = \min(6, 1 + 4) = 5\)). - **Step 3 (Visit `R`, dist = 2)**: - Outgoing edges from `R`: `R -> S` (weight 2 \(\implies d[S] = \min(5, 2 + 2) = 4\)), `R -> U` (weight 1 \(\implies d[U] = 2 + 1 = 3\)). - **Step 4 (Visit `U`, dist = 3)**: - Outgoing edges from `U`: none (edges `(S, U)` and `(T, U)` point *into* `U`). - Remaining unvisited vertices: `S` (`d[S] = 4`) and `T` (`d[T] = 7`). - **Step 5 (Visit `S`, dist = 4)**: - Outgoing edges from `S`: `S -> U` (already visited), `S -> T` (weight 3 \(\implies d[T] = \min(7, 4 + 3) = 7\)). - **Step 6 (Visit `T`, dist = 7)**: - All vertices visited! Thus, the order in which vertices are visited is **P, Q, R, U, S, T**. **Answer: D (P, Q, R, U, S, T)** A: **Incorrect:** After visiting `U` (distance 3), `S` has distance 4 while `T` has distance 7, so `S` is visited before `T`. B: **Incorrect:** `U` is reached via `P -> Q -> R -> U` with distance \(1 + 1 + 1 = 3\), which is smaller than `d[S] = 4`. C: **Incorrect:** `d[U] = 3 < d[S] = 4`, so `U` is visited before `S`. D: **Correct:** The shortest path distances from `P` are `P(0), Q(1), R(2), U(3), S(4), T(7)`, giving the order `P, Q, R, U, S, T`.

**Step 1: Analyze the max-heap property for the set `{10, 5, 15, 3, 8, 12}`.** - In any max-heap, the **maximum element (`15`)** must be at the **root** (index 1). - The **second-largest element (`12`)** cannot be a descendant of any element smaller than itself (since every parent in a max-heap must be greater than its children). Because `15` is the only element larger than `12`, **`12` must be a direct child of the root `15`** in every valid max-heap formed from these elements! **Answer: C (12)** A: **Incorrect:** `10` could be placed as a child of `12` rather than a direct child of `15`. B: **Incorrect:** `5` can be placed at a lower level as a child of `12` or `10`. C: **Correct:** The second-largest element (`12`) can only have the maximum element (`15`) as its parent, so `12` is guaranteed to be a child of `15`. D: **Incorrect:** `8` can be placed as a child of `12` or `10`.

**Step 1: Insert the numbers `50, 30, 20, 40, 70, 60, 80, 35` one by one into an empty BST.** - **Level 1 (Root)**: `50` - **Level 2**: `30` (left child of `50`), `70` (right child of `50`) - **Level 3**: `20` (left of `30`), `40` (right of `30`), `60` (left of `70`), `80` (right of `70`) - **Level 4**: `35` (since \(35 < 50\), \(35 > 30\), \(35 < 40\), `35` becomes the left child of `40`) **Step 2: Compute the height of the BST (where empty tree has height 0).** Since the longest root-to-leaf path (`50 -> 30 -> 40 -> 35`) contains **4 nodes** (4 levels), and the height of an empty tree is 0 (so a 1-node tree has height 1), the height of the resulting BST is **4**. **Answer: B (4)** A: **Incorrect:** 3 is the number of edges on the longest path, corresponding to height when a single node has height 0 (here an empty tree has height 0). B: **Correct:** The longest root-to-leaf path is `50 -> 30 -> 40 -> 35` (4 levels), so the height is 4. C: **Incorrect:** No path in the BST has 5 nodes. D: **Incorrect:** No path in the BST has 6 nodes.

**Step 1: Construct the BST and check the traversal order `10, 5, 3, 8, 15, 12, 20`.** - In a BST containing `{3, 5, 8, 10, 12, 15, 20}`: - **In-order traversal** always visits keys in sorted ascending order: `3, 5, 8, 10, 12, 15, 20`. - **Pre-order traversal** (`Root -> Left -> Right`) visits the root `10` first, then the left subtree rooted at `5` (`5, 3, 8`), and then the right subtree rooted at `15` (`15, 12, 20`), producing **`10, 5, 3, 8, 15, 12, 20`**. - **Post-order traversal** (`Left -> Right -> Root`) visits the root `10` last (`3, 8, 5, 12, 20, 15, 10`). **Answer: B (Pre-order traversal)** A: **Incorrect:** In-order traversal of a BST always produces the sorted sequence `3, 5, 8, 10, 12, 15, 20`. B: **Correct:** Visiting root `10` first, then left subtree `5, 3, 8`, then right subtree `15, 12, 20` is Pre-order traversal. C: **Incorrect:** Post-order traversal visits the root `10` at the very end, not the beginning.

In the divide-and-conquer algorithm for the **Closest Pair of Points**: 1. **Divide**: Split the sorted point set into left half \(P_L\) and right half \(P_R\) by a vertical dividing line. 2. **Conquer**: 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**: Because the overall closest pair might have one point in \(P_L\) and one point in \(P_R\), we must **consider pairs that span both halves** within a vertical strip of width \(2\delta\) around the dividing line. **Answer: C (Consider pairs that span both halves)** A: **Incorrect:** Taking \(\min(\delta_L, \delta_R)\) directly misses closest pairs where one point lies in the left half and the other in the right half. B: **Incorrect:** Checking all pairs across halves naively takes \(O(n^2)\); the algorithm checks only points within the \(2\delta\) strip. C: **Correct:** The combine step checks pairs of points that straddle the dividing line (within distance \(\delta\) of the line). D: **Incorrect:** Points are sorted by \(x\)- and \(y\)-coordinates, not by pairwise distances.

**Step 1: Apply the Master Theorem to \(T(n) = 4T(n/2) + O(n)\).** For a recurrence of the form \(T(n) = a T(n/b) + f(n)\): - \(a = 4\), \(b = 2\), and \(f(n) = O(n)\). - Compute the critical exponent: \[n^{\log_b a} = n^{\log_2 4} = n^2\] **Step 2: Compare \(f(n) = O(n)\) with \(n^{\log_b a} = n^2\).** Since \(f(n) = O(n^{2 - \epsilon})\) with \(\epsilon = 1 > 0\), Case 1 of the Master Theorem applies: \[T(n) = \Theta(n^2) = O(n^2)\] **Answer: C (\(O(n^2)\))** A: **Incorrect:** The recursion tree has \(4^{\log_2 n} = n^2\) leaves, which dominates the \(O(n)\) work at the root. B: **Incorrect:** \(O(\log n)\) is the complexity of binary search (\(T(n) = T(n/2) + O(1)\)). C: **Correct:** By Case 1 of the Master Theorem, \(T(n) = 4T(n/2) + O(n) = O(n^{\log_2 4}) = O(n^2)\). D: **Incorrect:** \(O(n \log n)\) corresponds to \(T(n) = 2T(n/2) + O(n)\), not \(4T(n/2) + O(n)\).

**Step 1: Trace Prim's algorithm starting from vertex `a`.** At each step, Prim's algorithm adds the minimum-weight edge connecting a visited vertex to an unvisited vertex: 1. Start at **`a`**. Incident edges from `{a}`: `(a, e) = 1`, `(a, b) = 2`, `(a, d) = 5`, `(a, c) = 7`. 2. Minimum edge is `(a, e) = 1` \(\implies\) visit **`e`**. 3. From `{a, e}`, minimum edge to unvisited is `(a, b) = 2` \(\implies\) visit **`b`**. 4. From `{a, e, b}`, candidate edges are `(b, c) = 4`, `(a, d) = 5`, `(a, c) = 7`, `(e, g) = 8`, `(b, d) = 9`. Minimum is `(b, c) = 4` \(\implies\) visit **`c`**. 5. From `{a, e, b, c}`, candidate edges are `(a, d) = 5`, `(e, g) = 8`, `(b, d) = 9`, `(c, g) = 15`. Minimum is `(a, d) = 5` \(\implies\) visit **`d`**. 6. From `{a, e, b, c, d}`, candidate edges are `(e, g) = 8`, `(d, f) = 11`, `(c, g) = 15`. Minimum is `(e, g) = 8` \(\implies\) visit **`g`**. 7. From `{a, e, b, c, d, g}`, candidate edges are `(g, h) = 3`, `(d, f) = 11`. Minimum is `(g, h) = 3` \(\implies\) visit **`h`**. 8. From `{a, e, b, c, d, g, h}`, candidate edges to `{f}` are `(h, f) = 6`, `(d, f) = 11`. Minimum is `(h, f) = 6` \(\implies\) visit **`f`**. Thus, the vertices are visited in the exact order: **a, e, b, c, d, g, h, f**. **Answer: A (a, e, b, c, d, g, h, f)** A: **Correct:** Selecting edges of weights 1 (`e`), 2 (`b`), 4 (`c`), 5 (`d`), 8 (`g`), 3 (`h`), and 6 (`f`) visits `a, e, b, c, d, g, h, f`. B: **Incorrect:** Edge `(a, d) = 5` is cheaper than `(e, g) = 8`, so `d` is visited before `g`. C: **Incorrect:** Edge `(b, c) = 4` is cheaper than `(a, d) = 5`, so `c` is visited before `d`. D: **Incorrect:** `c` is visited before `d` (`4 < 5`), and `h` is visited before `f` (`3 < 11`).

Let us evaluate each statement about **Huffman coding and Huffman trees**: - **A is correct**: Huffman's greedy bottom-up algorithm merges the lowest-probability symbols first (placing them deepest in the tree) and merges higher-probability symbols last, so **symbols with higher probabilities are closer to the root** (receiving shorter codewords). - **B is incorrect**: Symbols with lower probabilities are placed farthest from the root (receiving longer codewords). - **C is incorrect**: A Huffman tree is always a **full (strict) binary tree** (every internal node has 2 children), but it is generally **not** a complete binary tree (leaves can be at very different depths, e.g., a skewed tree). - **D is correct**: Because all symbols are placed at the **leaf nodes** of the Huffman tree, no codeword is a prefix of another codeword (**prefix code**). **Answer: A, D** A: **Correct:** Frequent symbols are merged near the end of construction, placing them closer to the root with shorter bit codes. B: **Incorrect:** Rare symbols are merged first and end up deepest in the tree. C: **Incorrect:** A Huffman tree is a full binary tree (0 or 2 children per node), not necessarily a complete binary tree. D: **Correct:** Since symbols reside only at leaves, no symbol's path from the root is a prefix of another symbol's path.

**Step 1: Insert `19` into the given AVL tree as in a standard BST.** - Compare with `38`: \(19 < 38 \to\) go left to `14`. - Compare with `14`: \(19 > 14 \to\) go right to `23`. - Compare with `23`: \(19 < 23 \to\) go left to `18`. - Compare with `18`: \(19 > 18 \to\) insert `19` as the **right child of `18`**. **Step 2: Compute the subtree heights and slopes (\(|h_L - h_R|\)) of all nodes after inserting `19` (with empty tree height = 0):** - **Node `18`**: Left subtree empty (\(h_L = 0\)), right subtree `{19}` (\(h_R = 1\)) \(\implies \text{slope}(18) = |0 - 1| = 1\), height \(= 2\). - **Node `23`**: Left subtree rooted at `18` (\(h_L = 2\)), right subtree empty (\(h_R = 0\)) \(\implies \text{slope}(23) = |2 - 0| = 2 > 1\), height \(= 3\). - **Node `14`**: Left subtree `{8}` (\(h_L = 1\)), right subtree rooted at `23` (\(h_R = 3\)) \(\implies \text{slope}(14) = |1 - 3| = 2 > 1\), height \(= 4\). - **Node `56`**: Left `{45}` (\(h_L = 1\)), right `{82 -> 70}` (\(h_R = 2\)) \(\implies \text{slope}(56) = |1 - 2| = 1\), height \(= 3\). - **Node `38`**: Left rooted at `14` (\(h_L = 4\)), right rooted at `56` (\(h_R = 3\)) \(\implies \text{slope}(38) = |4 - 3| = 1\). Thus, the nodes whose slopes become strictly greater than 1 are **`14` and `23`**. **Answer: C, E (14 and 23)** A: **Incorrect:** Node `38` has left height 4 and right height 3, so its slope is \(|4 - 3| = 1\). B: **Incorrect:** Node `56` is unaffected by the insertion in the left subtree and retains slope \(|1 - 2| = 1\). C: **Correct:** Node `14` has left height 1 (`{8}`) and right height 3 (`23 -> 18 -> 19`), giving slope \(|1 - 3| = 2 > 1\). D: **Incorrect:** Node `18` has left height 0 and right height 1 (`{19}`), giving slope \(|0 - 1| = 1\). E: **Correct:** Node `23` has left height 2 (`18 -> 19`) and right height 0, giving slope \(|2 - 0| = 2 > 1\).

Let us evaluate each statement about QuickSelect and Median of Medians (MoM): - **A is incorrect**: Standard QuickSelect (without Median-of-Medians pivot selection) has an *average-case* running time of \(O(n)\), but its **worst-case** running time (when bad pivots are chosen repeatedly) is **\(O(n^2)\)**. - **B is correct**: The deterministic **Median of Medians (MoM)** algorithm finds the median (or any \(k\)-th order statistic) in guaranteed **\(O(n)\)** worst-case time. - **C is correct**: **QuickSelect** partitions the array around a pivot and recurses on the side containing the \(k\)-th element, which is a classic **divide-and-conquer** (specifically decrease-and-conquer) algorithm. - **D is incorrect**: Fast Select (QuickSelect using Median of Medians for pivot selection) guarantees a **worst-case running time of \(O(n)\)**, not \(O(n^2)\). **Answer: B, C** A: **Incorrect:** Standard QuickSelect has worst-case complexity \(O(n^2)\) when pivots are consistently extreme. B: **Correct:** The Median of Medians algorithm finds the median of an unsorted list in worst-case \(O(n)\) time. C: **Correct:** QuickSelect partitions the problem into a smaller subproblem using the divide-and-conquer paradigm. D: **Incorrect:** Using Median of Medians for pivot selection reduces the worst-case time of QuickSelect from \(O(n^2)\) to \(O(n)\).

The graph has 4 vertices \(\{A, B, C, D\}\) and 5 edges forming two triangles sharing the diagonal edge \(BC\) (weight \(w_3\)): - Lower triangle \(ABC\) has edges \(w_1, w_2, w_3\). - Upper triangle \(DBC\) has edges \(w_3, w_4, w_5\). Let us check when the Minimum Spanning Tree (MST, which has \(4 - 1 = 3\) edges) is **unique**: - **A is correct**: A fundamental theorem of graph theory states that if all edge weights in a connected graph are **distinct**, the MST is **unique**. - **B is incorrect**: If \(w_1 = w_2\) are the **largest** weights among all 5 edges, then in the lower triangle \(ABC\), both \(w_1\) and \(w_2\) are strictly larger than \(w_3, w_4, w_5\). To connect vertex \(A\) to the rest of the graph \(\{B, C, D\}\), the MST must include **either \(w_1\) or \(w_2\)** (along with the two smallest edges from \(\{w_3, w_4, w_5\}\)). Since \(w_1 = w_2\), we get **2 distinct MSTs** of the same minimum weight! - **C is correct**: If \(w_1 = w_3\) are the **largest** weights among all 5 edges, then \(w_2, w_4, w_5\) are strictly smaller than \(w_1\) and \(w_3\). The edges corresponding to \(w_2 (AC)\), \(w_4 (CD)\), and \(w_5 (DB)\) form a spanning tree of all 4 vertices without cycles! Thus, neither \(w_1\) nor \(w_3\) is included, and the **unique MST** is \(\{w_2, w_4, w_5\}\). - **D is correct**: If \(w_1 = w_4\) are the **smallest** weights among all 5 edges, Kruskal's algorithm includes **both** \(w_1 (AB)\) and \(w_4 (CD)\) first (no cycle), and then adds the unique minimum among the remaining distinct weights \(\{w_2, w_3, w_5\}\) to connect \(\{A, B\}\) and \(\{C, D\}\). Thus, the MST is **unique**! **Answer: A, C, D** A: **Correct:** Distinct edge weights always guarantee a unique Minimum Spanning Tree. B: **Incorrect:** Since vertex `A` only has edges `w1` and `w2`, if `w1 = w2` are the largest weights, either `w1` or `w2` can be chosen to connect `A`, yielding 2 different MSTs. C: **Correct:** If `w1 = w3` are the largest weights, both are excluded and the remaining three edges `{w2, w4, w5}` form the unique MST. D: **Correct:** If `w1 = w4` are the smallest weights, both are included in the MST along with the unique smallest edge from `{w2, w3, w5}`.

**Step 1: Recall the relationship between nodes and leaves in a binary tree.** To maximize the number of leaf nodes (degree-0 nodes \(n_0\)) in a binary tree with \(N = 21\) total nodes, we should minimize the number of internal nodes with only 1 child (\(n_1 = 0\)), making the tree a **full (strict) binary tree** where every internal node has 2 children. **Step 2: Use \(N = n_0 + n_2\) and \(n_0 = n_2 + 1\).** \[21 = n_0 + (n_0 - 1) = 2n_0 - 1 \implies 2n_0 = 22 \implies n_0 = 11\] Thus, the maximum number of leaves possible in a 21-node binary tree is **11**. **Answer: 11**

**Step 1: Count the inversions \((L[i], L[j])\) with \(i < j\) and \(L[i] > L[j]\) for \(L = [1, 3, 5, 7, 9, 8, 6, 4, 2]\).** For each element \(L[i]\), count how many elements to its right are strictly smaller than \(L[i]\): - `1`: none \(\implies 0\) - `3`: `(3, 2)` \(\implies 1\) - `5`: `(5, 4), (5, 2)` \(\implies 2\) - `7`: `(7, 6), (7, 4), (7, 2)` \(\implies 3\) - `9`: `(9, 8), (9, 6), (9, 4), (9, 2)` \(\implies 4\) - `8`: `(8, 6), (8, 4), (8, 2)` \(\implies 3\) - `6`: `(6, 4), (6, 2)` \(\implies 2\) - `4`: `(4, 2)` \(\implies 1\) - `2`: none \(\implies 0\) **Step 2: Sum the counts.** \[\text{Total inversions} = 0 + 1 + 2 + 3 + 4 + 3 + 2 + 1 + 0 = 16\] **Answer: 16**

**Step 1: Sort the 7 activities in ascending order of their finish (end) times.** Given activities `[(1, 4), (3, 5), (0, 2), (2, 3), (5, 8), (8, 9), (5, 7)]`: Sorted by end time: 1. `(0, 2)` (ends at 2) 2. `(2, 3)` (starts at 2 \(\ge 2\), ends at 3) 3. `(1, 4)` (ends at 4) 4. `(3, 5)` (starts at 3 \(\ge 3\), ends at 5) 5. `(5, 7)` (starts at 5 \(\ge 5\), ends at 7) 6. `(5, 8)` (ends at 8) 7. `(8, 9)` (starts at 8 \(\ge 7\), ends at 9) **Step 2: Greedily select non-overlapping activities.** 1. Select `(0, 2)` 2. Select `(2, 3)` (since \(2 \ge 2\)) 3. Skip `(1, 4)` (since \(1 < 3\)) 4. Select `(3, 5)` (since \(3 \ge 3\)) 5. Select `(5, 7)` (since \(5 \ge 5\)) 6. Skip `(5, 8)` (since \(5 < 7\)) 7. Select `(8, 9)` (since \(8 \ge 7\)) Thus, at most **5** activities can be scheduled: `[(0, 2), (2, 3), (3, 5), (5, 7), (8, 9)]`. **Answer: 5**