Programming, Data Structures and Algorithms using Python · End Term · May 2026 · FN

**1. Understand the loop inside `f(m, n)`:** We are given the Python function: ```python def f(m, n): ans = 1 count = 0 while (ans <= m): count = count + 1 ans = ans * n return count ``` When called as `f(1000, 2)`, we start with `ans = 1 = 2^0` and `count = 0`. In each iteration of the `while` loop, as long as `ans <= 1000`, `count` increases by `1` and `ans` is multiplied by `2`. **2. Count how many powers of 2 are at most 1000:** The loop runs for every integer power \(2^k \le 1000\) starting from \(k = 0\): - \(k = 0: 2^0 = 1 \le 1000 \implies \text{count} = 1,\; \text{ans} = 2\) - \(k = 1: 2^1 = 2 \le 1000 \implies \text{count} = 2,\; \text{ans} = 4\) - ... - \(k = 9: 2^9 = 512 \le 1000 \implies \text{count} = 10,\; \text{ans} = 1024\) When `ans` reaches \(2^{10} = 1024 > 1000\), the `while` loop terminates and returns `count = 10`. **Answer: 10.**

**1. Understand the `Queue` class and `do_something(L)`:** The `Queue` class implements a standard First-In-First-Out (FIFO) queue: - `enqueue(v)` appends `v` to the end of `self.queue`. - `dequeue()` removes and returns the element at the front (`self.queue[0]`). In `do_something([2, 9, 12, 61, 55, 31])`: 1. The first `for` loop enqueues all \(6\) elements of `L` in order: `self.queue` becomes `[2, 9, 12, 61, 55, 31]`. 2. The second `for` loop runs `len(L) - 1 = 5` times, calling `Q.dequeue()` each time and discarding the first \(5\) elements (`2, 9, 12, 61, 55`). 3. Finally, `return(Q.dequeue())` dequeues and returns the last remaining element in the queue, which is `31`. **Answer: 31.**

**1. List the vertices and weighted edges of the given graph \(G\):** The undirected graph has \(V = 6\) vertices \(\{A, B, C, D, E, F\}\) and the following edge weights: - \((C, F) = 1\) - \((E, F) = 1\) - \((A, B) = 2\) - \((B, D) = 3\) - \((A, D) = 4\) - \((B, E) = 5\) - \((C, E) = 5\) - \((B, C) = 6\) - \((D, E) = 7\) **2. Apply Kruskal's algorithm to build a Minimum Spanning Tree (MST):** Sort the edges in non-decreasing order of weight and add an edge if it does not form a cycle (until \(|V| - 1 = 5\) edges are selected): 1. Add edge \((C, F)\) with weight \(1\). 2. Add edge \((E, F)\) with weight \(1\) (connects \(\{C, E, F\}\)). 3. Add edge \((A, B)\) with weight \(2\). 4. Add edge \((B, D)\) with weight \(3\) (connects \(\{A, B, D\}\)). 5. Next smallest edge is \((A, D) = 4\), which connects \(A\) and \(D\) that are already in \(\{A, B, D\}\) (forms a cycle, so skip). 6. Next smallest edge is \((B, E) = 5\) (or \((C, E)\) which is a cycle, so pick \((B, E) = 5\)), connecting \(\{A, B, D\}\) with \(\{C, E, F\}\). **3. Sum the weights of the 5 MST edges:** \[\text{Total MST weight} = 1 + 1 + 2 + 3 + 5 = 12\] **Answer: 12.**

**1. Insert the elements `[25, 12, 36, 8, 18, 40, 15]` sequentially into an empty BST:** Let the root be at depth \(0\): 1. Insert `25`: becomes the root at depth \(0\). 2. Insert `12`: \(12 < 25 \implies\) becomes the left child of `25` (depth \(1\)). 3. Insert `36`: \(36 > 25 \implies\) becomes the right child of `25` (depth \(1\)). 4. Insert `8`: \(8 < 25\) and \(8 < 12 \implies\) becomes the left child of `12` (depth \(2\)). 5. Insert `18`: \(18 < 25\) and \(18 > 12 \implies\) becomes the right child of `12` (depth \(2\)). 6. Insert `40`: \(40 > 25\) and \(40 > 36 \implies\) becomes the right child of `36` (depth \(2\)). 7. Insert `15`: \(15 < 25 \to 15 > 12 \to 15 < 18 \implies\) becomes the left child of `18` (depth \(3\)). **2. Identify the leaf node at the maximum depth:** The leaves of the resulting BST are `8` (depth 2), `15` (depth 3), and `40` (depth 2). The unique leaf at the maximum depth (depth 3) is `15`. **Answer: 15.**

**1. Understand the greedy coin-change strategy vs. the optimal solution:** We have coin denominations \(\{1, 3, 4, 5\}\). For each target value \(V > 0\), the greedy strategy repeatedly picks the largest coin \(\le\) the remaining value. **2. Test integer values \(V = 1, 2, 3, \dots\) in increasing order:** - \(V = 1..5\): Greedy uses 1 coin (for 1, 3, 4, 5) or 2 coins for \(V = 2 = 1 + 1\) (optimal). - \(V = 6\): Greedy picks \(5 + 1\) (2 coins). Optimal is \(3 + 3\) or \(5 + 1\) (2 coins). Greedy is still optimal! - \(V = 7\): - **Greedy choice:** Picks \(5\) first (leaving \(7 - 5 = 2\)), then must pick \(1 + 1\), using \(5 + 1 + 1 = 3\) coins. - **Optimal choice:** Picks \(3 + 4 = 7\), using only **2 coins**! Since \(3 > 2\), the smallest integer target value \(V > 0\) for which the greedy strategy fails is \(V = 7\). **Answer: 7.**

**1. Understand the Median-of-Medians (`MoM`) function:** Given the 20-element list: `L = [12, 44, 5, 16, 3, 11, 18, 9, 2, 13, 9, 5, 6, 8, 21, 7, 20, 18, 28, 32]` The function splits `L` into consecutive blocks `X` of 5 elements, sorts each block `X`, and appends `X[len(X)//2]` (`X[2]`, the 3rd element in 0-based indexing) to `M`. **2. Find the median of each 5-element block:** - **Block 1:** `[12, 44, 5, 16, 3]` \(\xrightarrow{\text{sort}}\) `[3, 5, 12, 16, 44]` \(\implies X[2] = 12\) - **Block 2:** `[11, 18, 9, 2, 13]` \(\xrightarrow{\text{sort}}\) `[2, 9, 11, 13, 18]` \(\implies X[2] = 11\) - **Block 3:** `[9, 5, 6, 8, 21]` \(\xrightarrow{\text{sort}}\) `[5, 6, 8, 9, 21]` \(\implies X[2] = 8\) - **Block 4:** `[7, 20, 18, 28, 32]` \(\xrightarrow{\text{sort}}\) `[7, 18, 20, 28, 32]` \(\implies X[2] = 20\) Thus, the list of block medians is `M = [12, 11, 8, 20]`. **3. Evaluate the recursive call `MoM(M)`:** Since `len(M) = 4 <= 5`, `MoM(M)` sorts `M` in ascending order: `M = [8, 11, 12, 20]` and returns `M[len(M)//2] = M[4//2] = M[2] = 12`. **Answer: 12.**

**1. Count the total number of unrestricted grid paths from \((0, 0)\) to \((4, 4)\):** Moving only 1 step right (R) or 1 step up (U) from \((0, 0)\) to \((x, y)\) takes \(x + y\) steps, choosing \(x\) right steps in \(\binom{x+y}{x}\) ways. Without blockages, the total number of paths from \((0, 0)\) to \((4, 4)\) is: \[\binom{4 + 4}{4} = \binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70\] **2. Count the paths passing through the blocked points \(B_1 = (1, 3)\) and \(B_2 = (2, 2)\):** - **Paths passing through \(B_1 = (1, 3)\):** From \((0, 0)\) to \((1, 3)\) is \(\binom{1+3}{1} = \binom{4}{1} = 4\) ways, and from \((1, 3)\) to \((4, 4)\) is \(\binom{(4-1)+(4-3)}{4-1} = \binom{4}{3} = 4\) ways: \[N(B_1) = 4 \times 4 = 16\] - **Paths passing through \(B_2 = (2, 2)\):** From \((0, 0)\) to \((2, 2)\) is \(\binom{2+2}{2} = \binom{4}{2} = 6\) ways, and from \((2, 2)\) to \((4, 4)\) is \(\binom{4}{2} = 6\) ways: \[N(B_2) = 6 \times 6 = 36\] - **Paths passing through both \(B_1(1, 3)\) and \(B_2(2, 2)\):** Because \(1 < 2\) while \(3 > 2\), a path moving only right and up can never reach \((2, 2)\) after \((1, 3)\) or \((1, 3)\) after \((2, 2)\). Thus, \(N(B_1 \cap B_2) = 0\). **3. Subtract the blocked paths from the total paths:** \[\text{Valid paths} = 70 - 16 - 36 = 18\] **Answer: 18.**

**1. Recall Gallai's Identity relating Vertex Cover and Independent Set:** In any simple graph \(G = (V, E)\) with \(n = |V|\) vertices, a subset of vertices \(S \subseteq V\) is an **independent set** (no two vertices in \(S\) share an edge) if and only if its complement \(V \setminus S\) is a **vertex cover** (every edge has at least one endpoint in \(V \setminus S\)). Therefore, the size of a maximum independent set \(\alpha(G)\) and the size of a minimum vertex cover \(\beta(G)\) always sum to the total number of vertices \(n\): \[\alpha(G) + \beta(G) = n\] **2. Substitute the given values:** We are given \(\beta(G) = 8\) and \(\alpha(G) = 9\): \[n = 8 + 9 = 17\] **Answer: 17.**

**1. Express \(f(n) = n^2 \log n\) and the target bounds using exponents:** We are given \(f(n) = n^2 \log n\). Notice that for all large \(n\), \(1 \le \log n \le n^{0.5}\). Now let us write each comparison function in terms of powers of \(n\): - \(n\sqrt{n} = n^{1.5}\) - \(n^2\sqrt{n} = n^{2.5}\) - \(n^3\) **2. Check each asymptotic statement:** - **(i) Is \(f(n) = O(n\sqrt{n}) = O(n^{1.5})\)?** No! Since \(n^2 \log n\) grows much faster than \(n^{1.5}\) (\(\lim_{n\to\infty} \frac{n^2 \log n}{n^{1.5}} = \lim_{n\to\infty} n^{0.5} \log n = \infty\)), statement (i) is **not true**. - **(ii) Is \(f(n) = O(n^2\sqrt{n}) = O(n^{2.5})\)?** Yes! Since \(\log n = O(n^{0.5})\), multiplying both sides by \(n^2\) gives \(n^2 \log n = O(n^{2.5})\). Thus, statement (ii) is **true**. - **(iii) Is \(f(n) = O(n^3)\)?** Yes! Since \(\log n = O(n)\), multiplying by \(n^2\) gives \(n^2 \log n = O(n^3)\). Thus, statement (iii) is **true**. **Answer: B — (ii) and (iii) are true but (i) is not true.** A: **Incorrect:** Statements (ii) and (iii) are both true because \(n^2 \log n\) is asymptotically bounded above by both \(n^{2.5}\) and \(n^3\). B: **Correct:** Because \(\log n = o(n^{0.5})\), \(n^2 \log n\) is \(O(n^{2.5})\) and \(O(n^3)\), but grows strictly faster than \(n^{1.5}\). C: **Incorrect:** Statement (iii) is also true since \(n^2 \log n \le n^3\) for all \(n \ge 1\). D: **Incorrect:** Statement (i) is false because \(n^2 \log n\) grows faster than \(n^{1.5}\).

**1. Understand what a stable sort on the third coordinate requires:** We are sorting the list of 3D tuples in **ascending order of their 3rd coordinate**: `[(2, 8, 1), (3, 7, 5), (1, 4, 1), (6, 9, 5), (8, 5, 2), (9, 9, 0)]` A sorting algorithm is **stable** if whenever two elements have the **same key** (here, the same 3rd coordinate), they appear in the sorted output in the **exact same relative order** as they appeared in the original input list. **2. Group the input tuples by their 3rd coordinate in original input order:** - **3rd coordinate = 0:** `(9, 9, 0)` - **3rd coordinate = 1:** `(2, 8, 1)` appears at index 0, followed by `(1, 4, 1)` at index 2. So `(2, 8, 1)` must come before `(1, 4, 1)`. - **3rd coordinate = 2:** `(8, 5, 2)` - **3rd coordinate = 5:** `(3, 7, 5)` appears at index 1, followed by `(6, 9, 5)` at index 3. So `(3, 7, 5)` must come before `(6, 9, 5)`. **3. Combine the groups in ascending order of the 3rd coordinate (`0, 1, 2, 5`):** `[(9, 9, 0), (2, 8, 1), (1, 4, 1), (8, 5, 2), (3, 7, 5), (6, 9, 5)]` **Answer: D — [(9, 9, 0), (2, 8, 1), (1, 4, 1), (8, 5, 2), (3, 7, 5), (6, 9, 5)].** A: **Incorrect:** This swaps `(2, 8, 1)` and `(1, 4, 1)`, violating stability for key `1`. B: **Incorrect:** This swaps `(3, 7, 5)` and `(6, 9, 5)`, violating stability for key `5`. C: **Incorrect:** This list is not sorted by the third coordinate at all. D: **Correct:** All third coordinates are in non-decreasing order (`0, 1, 1, 2, 5, 5`), and both tied pairs (`(2,8,1)` before `(1,4,1)` and `(3,7,5)` before `(6,9,5)`) preserve their input order.

**1. Understand the quadratic probing hash function:** The hash table has size \(m = 7\) (indices `0` to `6`), and uses quadratic probing: \[h(k, i) = \big((k \bmod 7) + i^2\big) \bmod 7 \quad \text{for } i = 0, 1, 2, \dots\] We insert the keys `14, 21, 35` sequentially. Notice that all three keys are multiples of \(7\), so \(k \bmod 7 = 0\) for each key! **2. Trace each insertion step by step:** - **Insert `14`:** - \(i = 0:\; h(14, 0) = (0 + 0^2) \bmod 7 = 0\). Index `0` is empty \(\implies\) place `14` at **Index 0**. - **Insert `21`:** - \(i = 0:\; h(21, 0) = (0 + 0^2) \bmod 7 = 0\) (occupied by `14` — collision!). - \(i = 1:\; h(21, 1) = (0 + 1^2) \bmod 7 = 1\). Index `1` is empty \(\implies\) place `21` at **Index 1**. - **Insert `35`:** - \(i = 0:\; h(35, 0) = (0 + 0^2) \bmod 7 = 0\) (occupied by `14` — collision!). - \(i = 1:\; h(35, 1) = (0 + 1^2) \bmod 7 = 1\) (occupied by `21` — collision!). - \(i = 2:\; h(35, 2) = (0 + 2^2) \bmod 7 = 4\). Index `4` is empty \(\implies\) place `35` at **Index 4**. **Answer: C — Index 0: 14, Index 1: 21, Index 4: 35.** A: **Incorrect:** `14` is inserted first at Index `0` (not `35`), and `35` uses quadratic probing (`i^2 = 4`), not linear probing (`Index 2`). B: **Incorrect:** Placing `35` at Index `2` corresponds to linear probing (`0 + 2`), whereas quadratic probing jumps to `0 + 2^2 = 4`. C: **Correct:** Since \(14, 21, 35 \equiv 0 \pmod 7\), they probe offsets \(0^2 = 0\), \(1^2 = 1\), and \(2^2 = 4\), landing at indices `0`, `1`, and `4`. D: **Incorrect:** The second key `21` succeeds on its first retry (`i = 1`, Index `1`), while the third key `35` lands at Index `4` (`i = 2`).

**1. Analyze the given degree sequence of a 6-vertex simple undirected graph:** We are given \(n = 6\) vertices with degree sequence: \[d = (5, 3, 2, 2, 0, 0)\] In a **simple** undirected graph (no self-loops and no parallel multi-edges), the maximum possible degree of any vertex is \(n - 1 = 6 - 1 = 5\). **2. Check the contradiction between degree `5` and degree `0`:** - A vertex of degree \(5\) in a \(6\)-vertex simple graph must be connected by an edge to **every other vertex** in the graph (all \(5\) remaining vertices). - Consequently, every vertex in the graph must have degree **at least \(1\)**. - However, the given sequence claims there are two vertices of degree \(0\) (isolated vertices with no edges at all), which is impossible if a vertex of degree \(5\) is connected to all of them! **Answer: D — Graph G cannot exist because a vertex of degree 5 must be adjacent to every other vertex, which contradicts the presence of a vertex of degree 0.** A: **Incorrect:** Such a simple graph cannot exist, and even if it could, vertices of degree `0` would make it disconnected. B: **Incorrect:** A simple graph on 6 vertices cannot simultaneously have a vertex of degree 5 and a vertex of degree 0. C: **Incorrect:** The sum of the degrees is \(5 + 3 + 2 + 2 + 0 + 0 = 12\), which is even, not odd. D: **Correct:** In a 6-vertex simple graph, a vertex of degree 5 must be connected to all 5 other vertices, making it impossible for any vertex to have degree 0.

**1. Understand how Bellman-Ford behaves on graphs with strictly positive edge weights:** The Bellman-Ford algorithm computes single-source shortest paths in any directed graph without negative-weight cycles by relaxing all \(|E|\) edges across \(|V| - 1\) phases. **2. Compare with Dijkstra's algorithm:** - **Correctness:** Strictly positive edge weights certainly contain no negative cycles, so Bellman-Ford **correctly finds the shortest paths** to all reachable vertices. - **Time complexity:** Bellman-Ford still takes \(O(|V| \cdot |E|)\) worst-case time, which is asymptotically slower than Dijkstra's algorithm (\(O((|V| + |E|)\log |V|)\)), the preferred algorithm when all edge weights are non-negative. **Answer: B — The algorithm will correctly find the shortest paths; however, its worst-case time complexity is higher than that of Dijkstra's algorithm for graphs with non-negative edge weights.** A: **Incorrect:** Bellman-Ford works on *any* graph without negative cycles, including graphs where all edge weights are positive. B: **Correct:** Bellman-Ford accurately computes shortest paths on positive-weight graphs, though its \(O(VE)\) worst-case runtime is slower than Dijkstra's algorithm. C: **Incorrect:** Even with positive edge weights, a shortest path can have up to \(|V| - 1\) edges, requiring up to \(|V| - 1\) relaxation passes depending on edge ordering. D: **Incorrect:** Bellman-Ford only reports a negative cycle if a distance can still be reduced on the \(|V|\)-th pass, which never happens with positive edge weights.

**1. Recall the Full Binary Tree Theorem:** In a strict (full) binary tree, every node has either \(0\) children (a leaf node) or \(2\) children (an internal node). If a strict binary tree has \(L\) leaf nodes, then the number of internal nodes \(I\) is always: \[I = L - 1\] **2. Calculate the total number of nodes \(N\):** We are given \(L = 25\) leaf nodes. - Number of internal nodes: \(I = 25 - 1 = 24\). - Total number of nodes in the tree: \[N = L + I = 25 + 24 = 49\] **Answer: B — 49.** A: **Incorrect:** `24` is only the number of internal nodes (\(L - 1 = 24\)), not the total number of nodes. B: **Correct:** A strict binary tree with \(L = 25\) leaves has \(L - 1 = 24\) internal nodes, giving \(25 + 24 = 49\) total nodes. C: **Incorrect:** In any strict binary tree, the total number of nodes \(2L - 1\) is always odd, so `50` is impossible. D: **Incorrect:** Having `51` total nodes would correspond to \(26\) leaf nodes and \(25\) internal nodes.

**1. Understand the initial min-heap structure:** The initial min-heap array of length 6 is: `[10, 25, 15, 40, 50, 30]` Using 0-based indexing (where parent of index `i` is `(i - 1) // 2`): - Index 0: `10` (root) - Index 1: `25` (left child of `10`), Index 2: `15` (right child of `10`) - Index 3: `40` (left child of `25`), Index 4: `50` (right child of `25`), Index 5: `30` (left child of `15`) **2. Trace the first insertion: `insert(12)`:** 1. Append `12` at Index 6 (right child of Index 2, which holds `15`): `[10, 25, 15, 40, 50, 30, 12]` 2. Bubble up `12` (at Index 6): - Compare with parent at Index `(6 - 1)//2 = 2` (`15`): since \(12 < 15\), swap Index 6 and Index 2: `[10, 25, 12, 40, 50, 30, 15]` - Compare `12` (now at Index 2) with parent at Index `0` (`10`): since \(12 > 10\), stop! **3. Trace the second insertion: `insert(5)`:** 1. Append `5` at Index 7 (left child of Index 3, which holds `40`): `[10, 25, 12, 40, 50, 30, 15, 5]` 2. Bubble up `5` (at Index 7): - Compare with parent at Index `(7 - 1)//2 = 3` (`40`): since \(5 < 40\), swap Index 7 and Index 3: `[10, 25, 12, 5, 50, 30, 15, 40]` - Compare with parent at Index `(3 - 1)//2 = 1` (`25`): since \(5 < 25\), swap Index 3 and Index 1: `[10, 5, 12, 25, 50, 30, 15, 40]` - Compare with parent at Index `(1 - 1)//2 = 0` (`10`): since \(5 < 10\), swap Index 1 and Index 0: `[5, 10, 12, 25, 50, 30, 15, 40]` **Answer: D — [5, 10, 12, 25, 50, 30, 15, 40].** A: **Incorrect:** `12` was never bubbled up past `15` during the first insertion. B: **Incorrect:** `5` is inserted at index 7 (left child of `40` at index 3), so it bubbles up along indices `7 -> 3 -> 1 -> 0`, not along the right branch. C: **Incorrect:** During `insert(12)`, `12` swaps with its parent `15` at index 2, and during `insert(5)`, `5` swaps with `40` at index 3 and `25` at index 1. D: **Correct:** Inserting `12` swaps `12` and `15` to give `[10, 25, 12, 40, 50, 30, 15]`, and inserting `5` at index 7 bubbles it up through indices `3 (40)`, `1 (25)`, and `0 (10)` to yield `[5, 10, 12, 25, 50, 30, 15, 40]`.

**1. List the given character frequencies:** We have 5 characters with frequencies: - \(E: 5\), \(D: 10\), \(C: 11\), \(B: 12\), \(A: 17\) **2. Build the Huffman Tree step by step by repeatedly merging the two smallest frequencies:** 1. **Step 1:** Merge the two smallest frequencies \(E(5)\) and \(D(10)\) into internal node \(N_1(DE)\) with frequency \(5 + 10 = 15\). Remaining frequencies: \(\{C: 11,\; B: 12,\; N_1(DE): 15,\; A: 17\}\). 2. **Step 2:** Merge the two smallest frequencies \(C(11)\) and \(B(12)\) into internal node \(N_2(BC)\) with frequency \(11 + 12 = 23\). Remaining frequencies: \(\{N_1(DE): 15,\; A: 17,\; N_2(BC): 23\}\). 3. **Step 3:** Merge the two smallest frequencies \(N_1(DE)(15)\) and \(A(17)\) into internal node \(N_3(ADE)\) with frequency \(15 + 17 = 32\). Remaining frequencies: \(\{N_2(BC): 23,\; N_3(ADE): 32\}\). 4. **Step 4:** Merge \(N_2(BC)(23)\) and \(N_3(ADE)(32)\) into the root node \(R(55)\). **3. Determine the code length (depth) of letter `E`:** Tracing the path from the root \(R\) down to leaf \(E\): \[R(55) \to N_3(32) \to N_1(15) \to E(5)\] This path has **3 edges** (depth 3), so **3 bits** are used to encode the letter `E`. **Answer: C — 3.** A: **Incorrect:** No character in this 5-letter alphabet has a 1-bit code because even the highest-frequency letter `A(17)` is merged at depth 2. B: **Incorrect:** Letters `A`, `B`, and `C` are at depth 2 (2 bits), whereas `D` and `E` are one level deeper at depth 3. C: **Correct:** Merging `(E:5, D:10) -> 15`, `(C:11, B:12) -> 23`, `(15, A:17) -> 32`, and `(23, 32) -> 55` places `E` at depth 3, requiring 3 bits. D: **Incorrect:** Because `(C:11, B:12)` merge with each other rather than with `N_1(15)`, the tree is balanced enough that `E` is at depth 3, not depth 4.

**1. Compute all pairwise Euclidean distances among the 3 points:** We have 3 points in the brute-force base case of the closest-pair-of-points algorithm: \[P_1 = (0, 0), \quad P_2 = (0, 3), \quad P_3 = (4, 0)\] For \(n = 3\) points, there are \(\binom{3}{2} = 3\) unique pairs of points to check: 1. \(d(P_1, P_2) = \sqrt{(0 - 0)^2 + (3 - 0)^2} = 3\) 2. \(d(P_1, P_3) = \sqrt{(4 - 0)^2 + (0 - 0)^2} = 4\) 3. \(d(P_2, P_3) = \sqrt{(4 - 0)^2 + (0 - 3)^2} = \sqrt{16 + 9} = 5\) **2. Find the minimum distance \(\delta\) and the number of distance calculations:** - The minimum distance among the three pairs is \(\delta = \min(3, 4, 5) = 3\). - Because the brute-force base case must check every pair among the 3 points to guarantee finding the minimum, it performs **3 distance calculations**. **Answer: B — delta = 3, performed using 3 distance calculations.** A: **Incorrect:** Checking only 2 pairs could miss the closest pair if it happened to be the third pair; all \(\binom{3}{2} = 3\) pairs must be evaluated. B: **Correct:** The three pairwise distances are \(3, 4, 5\), so the minimum is \(\delta = 3\), found by evaluating all \(\binom{3}{2} = 3\) pairs. C: **Incorrect:** The distance between \(P_1(0,0)\) and \(P_2(0,3)\) is \(3 < 4\), so \(\delta = 3\), not \(4\). D: **Incorrect:** For 3 points, 3 pairwise distances must be checked and the minimum distance is 3, not 5.

**1. Trace the dynamic programming recurrence in `mystery(L)`:** We are given: ```python def mystery(L): n = len(L) dp = [1] * n for i in range(1, n): for j in range(0, i): if L[i] > L[j] and dp[i] < dp[j] + 1: dp[i] = dp[j] + 1 return max(dp) ``` **2. Interpret `dp[i]`:** - Every `dp[i]` is initialized to `1` (representing a subsequence of length 1 consisting of `L[i]` alone). - For each index `i`, the inner loop checks **all earlier indices** `j` from `0` to `i - 1` (not just `i - 1`). Whenever `L[i] > L[j]`, we can append `L[i]` to any increasing subsequence ending at `L[j]`, updating `dp[i] = max(dp[i], dp[j] + 1)`. - Therefore, `dp[i]` stores the length of the **longest increasing subsequence** ending at index `i`, and `max(dp)` returns the length of the **longest increasing subsequence (LIS)** in `L`. **Answer: B — It finds the length of the longest increasing subsequence in L.** A: **Incorrect:** A contiguous subarray would only compare `L[i]` with the immediately preceding element `L[i - 1]`, whereas the inner loop checks all `j` from `0` to `i - 1`. B: **Correct:** By checking all `0 <= j < i` with `L[i] > L[j]` and setting `dp[i] = max(dp[i], dp[j] + 1)`, this is the classic \(O(n^2)\) dynamic programming algorithm for the Longest Increasing Subsequence (LIS). C: **Incorrect:** `dp` stores subsequence lengths (initialized to `1` and incremented by `1`), not element values. D: **Incorrect:** The condition `L[i] > L[j]` requires each subsequent element to be strictly *greater* than the previous one (increasing, not decreasing).

**1. Formulate the Linear Programming constraints from the problem statement:** Let \(x\) be the number of tablets and \(y\) be the number of smartphones assembled per week: - **Electronic testing lab time (600 hours available):** Each tablet requires \(1\) hour and each smartphone requires \(2\) hours: \[x + 2y \le 600\] (This matches **Option A**, so Option A is valid.) - **Precision welding line time (900 hours available):** Each tablet requires \(3\) hours and each smartphone requires \(1.5\) hours: \[3x + 1.5y \le 900\] (This matches **Option B**, so Option B is valid.) **2. Check equivalent scaled forms of the welding constraint:** - Multiplying \(3x + 1.5y \le 900\) by \(2\) gives: \[6x + 3y \le 1800\] (This matches **Option D**, so Option D is also valid!) - Option C writes \(3x + 2y \le 450\), which neither matches the testing constraint nor the welding constraint (dividing \(3x + 1.5y \le 900\) by \(2\) would give \(1.5x + 0.75y \le 450\)). Thus, **Option C is NOT a valid constraint**. **Answer: C — 3x + 2y <= 450.** A: **Incorrect:** \(x + 2y \le 600\) is the valid testing time constraint (so do not select it). B: **Incorrect:** \(3x + 1.5y \le 900\) is the valid welding time constraint (so do not select it). C: **Correct:** \(3x + 2y \le 450\) is NOT a valid constraint for this problem, so it is the correct choice. D: **Incorrect:** \(6x + 3y \le 1800\) is simply the valid welding constraint \(3x + 1.5y \le 900\) multiplied by \(2\) (so do not select it).

**1. Recall the formal definition of the complexity class NP (Nondeterministic Polynomial time):** - The class **P** consists of decision problems that can be *solved* by a deterministic algorithm in polynomial time. - The class **NP** consists of decision problems for which any proposed `"yes"` certificate (solution) can be **verified** by a deterministic algorithm in **polynomial time** (equivalently, solved by a non-deterministic Turing machine in polynomial time). - Notice that \(\text{P} \subseteq \text{NP}\), so NP includes easy polynomial-time problems as well, not "problems that can never be solved in polynomial time". **Answer: B — It is the class of decision problems for which a proposed solution can be verified by a deterministic algorithm in polynomial time.** A: **Incorrect:** This defines the complexity class **P**, not **NP**. B: **Correct:** A decision problem belongs to **NP** if and only if a candidate solution (certificate) can be checked for correctness in polynomial time by a deterministic verifier. C: **Incorrect:** All problems in **P** also belong to **NP** (\(\text{P} \subseteq \text{NP}\)), so many problems in NP can be solved in polynomial time. D: **Incorrect:** NP is defined over decision problems via polynomial-time verification, not optimization problems requiring non-polynomial greedy strategies.

**1. Evaluate each statement about Quicksort:** - **Statement A:** For any deterministic fixed pivot selection rule (e.g., first element, last element, or middle element), an adversary can construct an input permutation where the chosen pivot is always the minimum or maximum element of the current subarray, causing an unbalanced \(0\) and \(n-1\) split at every step and \(O(n^2)\) worst-case running time. (True!) - **Statement B:** If we find the exact median in \(O(n)\) time (e.g., via Median of Medians) and use it as the pivot, the array is split into two halves of size \(\approx n/2\) at every recursive step. The recurrence \(T(n) = 2T(n/2) + O(n)\) solves to \(O(n \log n)\) in the worst case. (True!) - **Statement C:** Both Quicksort (partition around pivot, then recursively sort subarrays) and Merge Sort (split in half, recursively sort, then merge) are classic **divide-and-conquer** algorithms. (True!) - **Statement D:** Randomized Quicksort achieves \(O(n \log n)\) **expected (average)** time, but in the worst case (if random choices happen to repeatedly pick extreme pivots), it can still take \(O(n^2)\) time—it does not *always* terminate in \(O(n \log n)\) time. (False.) - **Statement E:** Standard in-place Quicksort swaps non-adjacent elements across the array during partitioning, which can change the relative order of equal keys, making it an **unstable** sort. (False.) **Answer: A, B, C — Deterministic fixed pivot rules have O(n^2) worst-case inputs, O(n) median finding gives O(n log n) worst-case complexity, and both quicksort and merge sort are divide-and-conquer algorithms.** A: **Correct:** Any fixed deterministic pivot position can be defeated by a worst-case input ordering that forces \(n - 1\) recursive levels and \(O(n^2)\) comparisons. B: **Correct:** Partitioning around the true median in \(O(n)\) time guarantees balanced \(n/2\) subproblems and \(O(n \log n)\) worst-case time. C: **Correct:** Both algorithms divide the array into two subproblems, recursively sort them, and combine the results. D: **Incorrect:** Random pivot selection guarantees \(O(n \log n)\) *expected* time, but an unlucky sequence of random pivots can still take \(\Theta(n^2)\) time. E: **Incorrect:** In-place partitioning swaps distant elements and does not preserve the relative order of equal elements, so standard quicksort is not stable.

**1. Find the maximum number of edges in a disconnected simple graph with \(n = 10\) vertices:** Suppose a simple undirected graph \(G\) with \(n = 10\) vertices is disconnected into at least two connected components of sizes \(k\) and \(10 - k\) (where \(1 \le k \le 9\)). The maximum number of edges occurs when one component is a single isolated vertex (\(k = 1\)) and the other component is a complete graph \(K_9\) on the remaining \(9\) vertices: \[e_{\max} = \binom{9}{2} = \frac{9 \times 8}{2} = 36\] Any number of edges \(e\) satisfying \(0 \le e \le 36\) can be realized by a disconnected simple graph on \(10\) vertices (by simply removing edges from \(K_9 \cup K_1\)). Conversely, any simple graph on \(10\) vertices with \(e > 36\) edges is **guaranteed to be connected**. **2. Check the given options:** - `45` and `37` are strictly greater than `36`, so a 10-vertex simple graph with `45` or `37` edges must be connected. - `36`, `35`, and `33` are all \(\le 36\), so they **can** be the number of edges in a disconnected graph on 10 vertices. **Answer: C, D, E — 36, 35, and 33.** A: **Incorrect:** \(45 = \binom{10}{2}\) is the complete graph \(K_{10}\), which is connected. B: **Incorrect:** Since the maximum edges in a disconnected 10-vertex simple graph is \(\binom{9}{2} = 36\), any graph with `37` edges must be connected. C: **Correct:** A disconnected graph formed by \(K_9\) plus 1 isolated vertex has exactly \(\binom{9}{2} = 36\) edges. D: **Correct:** Removing any 1 edge from \(K_9 \cup K_1\) yields a disconnected 10-vertex graph with `35` edges. E: **Correct:** Removing any 3 edges from \(K_9 \cup K_1\) yields a disconnected 10-vertex graph with `33` edges.

**1. Recall the fundamental property of non-tree edges in an undirected BFS tree:** When Breadth-First Search (BFS) is run on an undirected graph from root `0`, the vertices are partitioned into distance levels \(L_0, L_1, L_2, L_3\) according to their depth in the BFS tree: - **Level 0 (depth 0):** `0` - **Level 1 (depth 1):** `1, 2` - **Level 2 (depth 2):** `3, 4, 5` - **Level 3 (depth 3):** `6, 7, 8` In any undirected graph, every edge \((u, v)\) in the original graph can connect vertices whose BFS levels differ by **at most 1** (i.e., \(|\text{level}(u) - \text{level}(v)| \le 1\)). Furthermore, if \(u\) is at level \(d\) and \(v\) is at level \(d+1\), why wasn't \(v\) discovered directly from an even earlier vertex? Even more simply, let's check the level difference for each candidate edge! **2. Check the level differences of the given edges:** - **Option A `(3, 5)`:** Node `3` is in Level 2 and Node `5` is in Level 2 (\(|2 - 2| = 0 \le 1\)). Same-level cross edges are completely valid in a BFS tree! - **Option B `(1, 7)`:** Node `1` is in Level 1 and Node `7` is in Level 3 (parent is `4` in Level 2). If edge `(1, 7)` existed in the original graph, then when BFS explored Node `1` (at Level 1), it would have discovered `7` immediately and placed `7` in **Level 2**, not Level 3! Thus, `(1, 7)` **cannot be present**. - **Option C `(0, 4)`:** Node `0` is in Level 0 and Node `4` is in Level 2 (\(|0 - 2| = 2 > 1\)). If `(0, 4)` existed, `4` would be in Level 1. Thus, `(0, 4)` **cannot be present**. - **Option D `(6, 2)`:** Node `6` is in Level 3 and Node `2` is in Level 1 (\(|3 - 1| = 2 > 1\)). If `(6, 2)` existed, `6` would have been discovered from `2` and placed in Level 2. Thus, `(6, 2)` **cannot be present**. - **Option E `(7, 8)`:** Both `7` and `8` are in Level 3 (\(|3 - 3| = 0 \le 1\)). Same-level edges can exist in the original graph. **Answer: B, C, D — (1, 7), (0, 4), and (6, 2).** A: **Incorrect:** Nodes `3` and `5` are both at depth 2, and a non-tree edge between two nodes at the same BFS level is valid. B: **Correct:** Node `1` is at depth 1 and node `7` is at depth 3; an edge between them would have placed `7` at depth 2 during BFS. C: **Correct:** Node `0` is at depth 0 and node `4` is at depth 2; an edge `(0, 4)` would have made `4` a depth-1 child of `0`. D: **Correct:** Node `6` is at depth 3 and node `2` is at depth 1; an edge `(6, 2)` would have placed `6` at depth 2. E: **Incorrect:** Nodes `7` and `8` are both at depth 3, so an edge between them does not violate BFS level distances.

**1. Understand the structure of a Left-Right (LR) rotation in an AVL tree:** Before the rotation, we have: - Critical unbalanced node \(X\) (with right subtree \(T_4\)). - \(Y\) is the left child of \(X\) (so \(Y < X\), with left subtree \(T_1\)). - \(Z\) is the right child of \(Y\) (so \(Y < Z < X\)), with original left subtree \(T_2\) and original right subtree \(T_3\). Thus, the in-order ordering of keys and subtrees is: \[T_1 < Y < T_2 < Z < T_3 < X < T_4\] **2. Trace where \(T_2\) and \(T_3\) are attached after \(Z\) becomes the new root:** When the LR double rotation promotes \(Z\) to be the new root of the subtree: - \(Y\) becomes the **left child** of \(Z\), and \(X\) becomes the **right child** of \(Z\). - Because \(Y < T_2 < Z\), \(Z\)'s original left subtree \(T_2\) is attached as the **new right subtree of \(Y\)**. - Because \(Z < T_3 < X\), \(Z\)'s original right subtree \(T_3\) is attached as the **new left subtree of \(X\)**. **Answer: A, C — T_2 is attached as the new right subtree of Y, and T_3 is attached as the new left subtree of X.** A: **Correct:** Since all keys in \(T_2\) satisfy \(Y < T_2 < Z\), \(T_2\) becomes the right subtree of \(Y\) after \(Y\) becomes the left child of \(Z\). B: **Incorrect:** The left subtree of \(Y\) remains its original left subtree \(T_1\) (keys \(< Y\)). C: **Correct:** Since all keys in \(T_3\) satisfy \(Z < T_3 < X\), \(T_3\) becomes the left subtree of \(X\) after \(X\) becomes the right child of \(Z\). D: **Incorrect:** The right subtree of \(X\) remains its original right subtree \(T_4\) (keys \(> X\)).

**1. Understand the definition of an inversion in an array:** Given the array `A = [5, 1, 4, 3, 2]`, a pair of elements `(A[i], A[j])` forms an **inversion** if `A[i]` appears **before** `A[j]` in the array (`i < j`) and `A[i] > A[j]`. **2. Check each given pair against `A = [5, 1, 4, 3, 2]`:** - **Option A `(1, 3)`:** `1` appears before `3`, but \(1 < 3\) (not an inversion). - **Option B `(5, 1)`:** `5` is at index 0, `1` is at index 1 (`0 < 1`), and \(5 > 1\) (**valid inversion!**). - **Option C `(4, 2)`:** `4` is at index 2, `2` is at index 4 (`2 < 4`), and \(4 > 2\) (**valid inversion!**). - **Option D `(3, 4)`:** `4` appears *before* `3` in the array (so the inversion pair in array order is `(4, 3)`, whereas `(3, 4)` has \(3 < 4\)). - **Option E `(3, 2)`:** `3` is at index 3, `2` is at index 4 (`3 < 4`), and \(3 > 2\) (**valid inversion!**). **Answer: B, C, E — (5, 1), (4, 2), and (3, 2).** A: **Incorrect:** Although `1` appears before `3`, \(1 < 3\), so they are in increasing order and do not form an inversion. B: **Correct:** `5` appears at index 0 before `1` at index 1, and \(5 > 1\). C: **Correct:** `4` appears at index 2 before `2` at index 4, and \(4 > 2\). D: **Incorrect:** `3` is smaller than `4` and appears *after* `4` in `[5, 1, 4, 3, 2]`. E: **Correct:** `3` appears at index 3 before `2` at index 4, and \(3 > 2\).