Programming, Data Structures and Algorithms using Python · End Term · Sep 2025 · FN

**1. Identify the Bug in `bad_count_even(L)`:** - Inside the `for i in L:` loop, when an odd number is encountered (`else:`), the function executes **`break`**, which **immediately terminates the entire loop** instead of continuing to check the remaining elements after the odd number! - Therefore, `bad_count_even(L)` only counts the even numbers that appear **before the first odd number**: - **Option A (`[56, 4, 70, 40]`):** All 4 numbers are even; returns `4` (correct). - **Option B (`[6, 8, 34, 13, 5, 9]`):** All even numbers (`6, 8, 34`) appear before the first odd number (`13`); returns `3` (correct). - **Option C (`[6, 11, 4, 30]`):** Has **3** even numbers (`6, 4, 30`), but the loop hits `11` at index 1 and `break`s early, returning `1` instead of `3` (**Incorrect output**). - **Option D (`[6, 4, 2, 30]`):** All 4 numbers are even; returns `4` (correct). **Answer: [6,11,4,30] (Option C).** A: **Incorrect:** Since `[56, 4, 70, 40]` contains no odd numbers, `break` never triggers and it returns the correct count `4`. B: **Incorrect:** Since all even numbers (`6, 8, 34`) precede the first odd number (`13`), breaking at `13` still returns the correct count `3`. C: **Correct:** The loop breaks at the odd number `11`, missing the subsequent even numbers `4` and `30` and returning `1` instead of `3`. D: **Incorrect:** All elements in `[6, 4, 2, 30]` are even, so it returns the correct count `4`.

**1. Determine the Dominant Term (Big-O Complexity) for Each Function:** - **1) \( f_1(n) = 5n^2 + 3n \):** Dominant term is \( 5n^2 \implies O(n^2) \) (**b**). - **2) \( f_2(n) = 3n + \log n \):** Dominant term is \( 3n \implies O(n) \) (**c**). - **3) \( f_3(n) = n \log n + \log n \):** Dominant term is \( n \log n \implies O(n \log n) \) (**d**). - **4) \( f_4(n) = 6 \log n \):** Constant factor 6 is dropped \( \implies O(\log n) \) (**e**). - **5) \( f_5(n) = 2^n + 3n \):** Dominant term is exponential \( 2^n \implies O(2^n) \) (**a**). **Answer: 1-b, 2-c, 3-d, 4-e, 5-a (Option A).** A: **Correct:** Matches `1-b` (\( O(n^2) \)), `2-c` (\( O(n) \)), `3-d` (\( O(n \log n) \)), `4-e` (\( O(\log n) \)), and `5-a` (\( O(2^n) \)). B: **Incorrect:** Swaps `1` and `5`. C: **Incorrect:** Swaps `3` and `4`. D: **Incorrect:** Swaps both `1`/`5` and `3`/`4`.

**1. Trace `selectionsort(L)` on `L = [15, 12, 18, 13, 11]`:** - **Initial List:** `[15, 12, 18, 13, 11]` - **Pass 1 (`i = 0`):** - Finds the minimum element in `L[0..4]`, which is `11` at index `4`. - Swaps `L[0]` (`15`) with `L[4]` (`11`), yielding: `[11, 12, 18, 13, 15]` - **Pass 2 (`i = 1`):** - Finds the minimum element in `L[1..4]` (`[12, 18, 13, 15]`), which is `12` already at index `1`. - Swaps `L[1]` (`12`) with itself, so the list after the second pass remains: **`[11, 12, 18, 13, 15]`** **Answer: [11, 12, 18, 13, 15] (Option C).** A: **Incorrect:** Swaps `11` with `12` instead of `15` during the first pass. B: **Incorrect:** This is the unsorted initial list. C: **Correct:** Pass 1 swaps `15` and `11` to give `[11, 12, 18, 13, 15]`, and Pass 2 keeps `12` at index 1. D: **Incorrect:** This is the fully sorted list after all passes, not after the second pass.

**1. Compare Linear Search vs. Binary Search Across the Given Scenarios:** - **Option A (Linked list):** Singly/doubly linked lists do not support \( O(1) \) random access by index, so binary search cannot jump to the middle in \( O(1) \) time; linear search is the standard practical choice (**True**). - **Option B (Unsorted list):** Binary search **requires** the list to be sorted (sorting costs \( O(n \log n) \)), whereas a single linear search on an unsorted list takes only \( O(n) \) (**True**). - **Option C (Very large sorted list):** Binary search takes \( O(\log n) \) time, which is vastly faster than \( O(n) \) linear search (**False**). - **Option D (Target is at the first index `0`):** Linear search checks index `0` first and finds the element in \( O(1) \) (1 comparison), whereas binary search starts at the middle index `n // 2` (**True**). - **Option E (Target is at the last index):** Linear search takes \( n \) comparisons (worst case \( O(n) \)), whereas binary search takes \( O(\log n) \) (**False**). **Answer: Options A, B, and D.** A: **Correct:** Linked lists lack \( O(1) \) random access to the middle element, making linear search more practical. B: **Correct:** Binary search cannot be applied directly to an unsorted list without sorting it first. C: **Incorrect:** On a large sorted array, binary search (\( O(\log n) \)) is much faster than linear search (\( O(n) \)). D: **Correct:** Linear search inspects index 0 on its very first comparison (\( O(1) \)). E: **Incorrect:** The last index is the worst case for linear search (\( n \) comparisons), where binary search takes only \( O(\log n) \).

**1. Apply the Quicksort Partition Property:** - After the first partitioning pass around a pivot \( p \), \( p \) is placed in its final sorted position such that: - **Every element to the left of \( p \)** is \( \le p \), and - **Every element to the right of \( p \)** is \( > p \). - Let us check the given list `[12, 18, 25, 7, 30, 55, 60, 40]`: - **25:** `7` is to the right of `25`, but \( 7 < 25 \) (**Invalid**). - **30:** All elements to its left (`12, 18, 25, 7`) are \( < 30 \), and all elements to its right (`55, 60, 40`) are \( > 30 \) (**Valid**). - **7:** `12, 18, 25` are to the left of `7`, but they are \( > 7 \) (**Invalid**). - **40:** `55` and `60` are to the left of `40`, but they are \( > 40 \) (**Invalid**). **Answer: 30 (Option B).** A: **Incorrect:** `25` has `7` to its right (\( 7 < 25 \)), violating the partition invariant. B: **Correct:** Every element before `30` (`12, 18, 25, 7`) is less than `30`, and every element after `30` (`55, 60, 40`) is greater than `30`. C: **Incorrect:** `7` has larger elements (`12, 18, 25`) to its left. D: **Incorrect:** `40` has larger elements (`55, 60`) to its left.

**1. Exploit the Sorted Order of the Linked List:** - Because the linked list is already in **sorted order**, all duplicate values appear in **adjacent (consecutive) nodes**. - Therefore, we can remove all duplicates in-place in a single pass (\( O(n) \) time and \( O(1) \) auxiliary space) by traversing the list once from `head` and comparing each node's `data` with its immediate successor (`curr.next.data`), bypassing duplicates via `curr.next = curr.next.next`. **Answer: Traverse the linked list once, comparing each node with its immediate successor (Option C).** A: **Incorrect:** A singly linked list cannot be traversed backward from the tail without recursion overhead (\( O(n) \) stack space). B: **Incorrect:** A nested loop takes \( O(n^2) \) time and ignores the fact that the list is already sorted. C: **Correct:** Since duplicates are adjacent in a sorted linked list, a single pass comparing each node with its immediate successor removes all duplicates in \( O(n) \) time and \( O(1) \) space. D: **Incorrect:** Allocating a brand-new linked list uses \( O(n) \) extra space when in-place removal takes \( O(1) \) space.

**1. Trace the Stack Operations Step-by-Step (LIFO - Last In, First Out):** - Initially: `stack = []` - `push(15)` \( \to \) `stack = [15]` - `push(100)` \( \to \) `stack = [15, 100]` - `pop()` \( \to \) removes `100`, leaving `stack = [15]` - `push(150)` \( \to \) `stack = [15, 150]` - `push(200)` \( \to \) `stack = [15, 150, 200]` - `pop()` \( \to \) removes `200`, leaving `stack = [15, 150]` **2. Identify the Top Element:** - The element at the top of the stack is **`150`**. **Answer: 150.**

**1. Identify Articulation Points (Cut Vertices) in the Network Graph:** - A network stays connected when any single node fails if and only if the graph is **2-vertex-connected** (has no articulation points / cut vertices). - In the given graph: - Node `0` is a degree-1 leaf connected only to node `1` (making `1` an articulation point whose failure disconnects `0`). - Node `7` is a degree-1 leaf connected only to node `6` (making `6` an articulation point whose failure disconnects `7`). - Adding the edge **`(0, 7)`** connects the two degree-1 endpoints `0` and `7`, creating a cycle through `0 - 1 - {2,3,4,5} - 6 - 7 - 0` so that removing **any** single node leaves all remaining 7 nodes connected. **Answer: (0,7) (Option D).** A: **Incorrect:** Adding `(4, 7)` leaves node `0` attached only to node `1`, so if node `1` goes down, node `0` is disconnected. B: **Incorrect:** Adding `(5, 7)` still leaves node `1` as an articulation point for node `0`. C: **Incorrect:** Adding `(0, 3)` leaves node `7` attached only to node `6`, so if node `6` goes down, node `7` is disconnected. D: **Correct:** Adding `(0, 7)` eliminates both articulation points (`1` and `6`), making the entire graph 2-vertex-connected.

**1. Identify the Directed Edges and In-Degrees of the DAG:** - Directed edges from the figure: - From `0`: \( 0 \to 1, 0 \to 2, 0 \to 3 \) - From `1`: \( 1 \to 3 \) - From `2`: \( 2 \to 3 \) - From `3`: \( 3 \to 4 \) **2. Find All Valid Topological Orderings:** - Node `0` has in-degree `0` and is an ancestor of every other node, so `0` **must** come first. - After removing `0`, nodes `1` and `2` both have in-degree `0` and have no edge between them, so they can be ordered as either `1, 2` or `2, 1`. - Node `3` depends on `0, 1, 2`, so `3` must come after both `1` and `2`. - Node `4` depends on `3`, so `4` must come last. - Thus, there are exactly **2** valid topological sorts: `[0, 1, 2, 3, 4]` and `[0, 2, 1, 3, 4]`. **Answer: 2.**

**1. Fundamental Property of BFS Levels in an Undirected Graph:** - Let \( d(x) \) denote the shortest-path distance (level in the BFS tree \( T \) rooted at \( s \)) from the root \( s \) to vertex \( x \). - In an **undirected graph**, when BFS explores a vertex \( u \) at level \( d(u) \), any adjacent vertex \( v \) via an edge \( (u, v) \) can be at most one level away from \( u \) (either in the previous level \( d(u) - 1 \), the same level \( d(u) \), or the next level \( d(u) + 1 \)). - Therefore, for every non-tree edge \( (u, v) \), the difference between their BFS levels satisfies: \[ |d(u) - d(v)| \le 1 \] **Answer: \( |d(u) - d(v)| \le 1 \) (Option A).** A: **Correct:** In an undirected graph, every edge (including every non-tree edge) connects vertices in either the same BFS level (\( |d(u) - d(v)| = 0 \)) or adjacent BFS levels (\( |d(u) - d(v)| = 1 \)), so \( |d(u) - d(v)| \le 1 \). B: **Incorrect:** \( |d(u) - d(v)| \) can never equal 2 in a BFS tree of an undirected graph. C: **Incorrect:** Non-tree edges can connect two vertices in the *same* BFS level, where \( |d(u) - d(v)| = 0 \). D: **Incorrect:** \( |d(u) - d(v)| \) is never \( \ge 2 \) in BFS on an undirected graph.

**1. Run Shortest Path (Dijkstra's Algorithm) from Node 0 to Node 5:** - Edges and weights from the graph: - From `0`: `(0, 1) = 4`, `(0, 2) = 2`, `(0, 3) = 6` - From `2` (distance `2`): `(2, 1) = 1`, `(2, 3) = 3`, `(2, 4) = 7`, `(2, 5) = 6` - Distance to `1` via `0 -> 2 -> 1`: \( 2 + 1 = 3 \) - Distance to `3` via `0 -> 2 -> 3`: \( 2 + 3 = 5 \) - Distance to `5` via `0 -> 2 -> 5`: \( 2 + 6 = 8 \) - From `3` (distance `5`): `(3, 5) = 2` - Distance to `5` via `0 -> 2 -> 3 -> 5`: \( 2 + 3 + 2 = 7 \) **2. Minimum Distance to Node 5:** - The shortest path from `0` to `5` is `0 -> 2 -> 3 -> 5` with total weight \( 2 + 3 + 2 = 7 \). **Answer: 7 (Option A).** A: **Correct:** The path `0 -> 2 -> 3 -> 5` has total weight \( 2 + 3 + 2 = 7 \), which is the minimum distance. B: **Incorrect:** `8` is the weight of the paths `0 -> 2 -> 5` (\( 2 + 6 = 8 \)) and `0 -> 3 -> 5` (\( 6 + 2 = 8 \)), which are suboptimal. C: **Incorrect:** `9` is the weight of `0 -> 1 -> 2 -> 3 -> 5` (\( 4 + 1 + 3 + 2 = 10 \)) or `0 -> 2 -> 4` (\( 2 + 7 = 9 \)). D: **Incorrect:** `11` is not the shortest path distance.

**1. Compare Time Complexity of Bellman-Ford vs. Dijkstra on Non-Negative Graphs:** - On a graph with \( V \) vertices, \( E \) edges, and non-negative edge weights, both algorithms find the exact same correct shortest paths. - However, **Dijkstra's algorithm** runs in \( O((V + E) \log V) \) (or \( O(V^2) \)) time using a greedy priority queue, whereas the **Bellman-Ford algorithm** relaxes all \( E \) edges \( V - 1 \) times, taking \( O(V \cdot E) \) time. - Therefore, compared to Dijkstra's algorithm, Bellman-Ford will **run slower**. **Answer: Run slower (Option B).** A: **Incorrect:** Bellman-Ford's \( O(VE) \) time complexity is slower than Dijkstra's \( O((V+E)\log V) \). B: **Correct:** Bellman-Ford performs \( V - 1 \) passes over all edges (\( O(VE) \)), running slower than Dijkstra's greedy approach. C: **Incorrect:** Bellman-Ford works on all graphs without negative-weight cycles, including graphs with non-negative weights. D: **Incorrect:** Bellman-Ford only flags *negative-weight* cycles, which cannot exist when all edge weights are non-negative.

**1. Uniqueness Theorem for Minimum Spanning Trees (MSTs):** - A fundamental theorem of graph theory states that if all edge weights in a connected graph \( G \) are **distinct**, then \( G \) has a **unique** Minimum Spanning Tree (so Prim's and Kruskal's algorithms are guaranteed to produce the exact same tree \( MST_P = MST_K \)). - By the contrapositive, if Prim's algorithm and Kruskal's algorithm produce two **different** minimum spanning trees (\( MST_P \neq MST_K \)), then \( G \) has multiple MSTs, which is possible **only if some of the edges in \( G \) have the same weight**. **Answer: Some of the edges in G must have the same weight (Option C).** A: **Incorrect:** If there are multiple edges tied for the minimum weight in a cycle, one MST may pick one while another MST picks the other. B: **Incorrect:** A maximum-cost edge can still belong to every MST if it is a bridge (cut-edge) in \( G \). C: **Correct:** If all edge weights were distinct, the MST would be unique; having \( MST_P \neq MST_K \) requires at least two edges in \( G \) to share the same weight. D: **Incorrect:** Only *some* edges need to share equal weights to create ties, not *all* edges.

**1. Use the Binary Tree Degree Identity:** - In any non-empty binary tree, let: - \( n_0 \) = number of leaf nodes (0 children) - \( n_1 \) = number of nodes with 1 child - \( n_2 \) = number of nodes with 2 children - By the binary tree leaf property, \( n_0 = n_2 + 1 \). - Given \( n_2 = 6 \), the number of leaf nodes is: \[ n_0 = 6 + 1 = 7 \] **2. Solve for \( n_1 \):** - Since the total number of nodes is \( N = n_0 + n_1 + n_2 = 15 \): \[ 7 + n_1 + 6 = 15 \implies n_1 = 15 - 13 = 2 \] **Answer: 2 (Option A).** A: **Correct:** Since \( n_0 = n_2 + 1 = 7 \) and \( n_0 + n_1 + n_2 = 15 \), we get \( n_1 = 15 - 7 - 6 = 2 \). B: **Incorrect:** If \( n_1 = 3 \), total nodes would be \( 7 + 3 + 6 = 16 \neq 15 \). C: **Incorrect:** If \( n_1 = 4 \), total nodes would be \( 17 \neq 15 \). D: **Incorrect:** If \( n_1 = 5 \), total nodes would be \( 18 \neq 15 \).

**1. Perform `delete_max()` on `[89, 62, 31, 45, 51, 29, 30, 42, 34]`:** - Remove the root `89` and move the last element `34` to index 0: `[34, 62, 31, 45, 51, 29, 30, 42]` - Sift `34` down (`heapify-down`): - Children of index 0 (`34`) are index 1 (`62`) and index 2 (`31`). Larger child is `62` at index 1. Swap `34` and `62`: `[62, 34, 31, 45, 51, 29, 30, 42]` - Children of index 1 (`34`) are index 3 (`45`) and index 4 (`51`). Larger child is `51` at index 4. Swap `34` and `51`: `[62, 51, 31, 45, 34, 29, 30, 42]` - Index 4 (`34`) has no children (since \( 2(4) + 1 = 9 \ge 8 \)). **2. Perform `insert(78)`:** - Append `78` at the end (index 8): `[62, 51, 31, 45, 34, 29, 30, 42, 78]` - Sift `78` up (`heapify-up`): - Parent of index 8 is index \( (8 - 1) // 2 = 3 \) (`45`). Since \( 78 > 45 \), swap: `[62, 51, 31, 78, 34, 29, 30, 42, 45]` - Parent of index 3 is index \( (3 - 1) // 2 = 1 \) (`51`). Since \( 78 > 51 \), swap: `[62, 78, 31, 51, 34, 29, 30, 42, 45]` - Parent of index 1 is index \( (1 - 1) // 2 = 0 \) (`62`). Since \( 78 > 62 \), swap: **`[78, 62, 31, 51, 34, 29, 30, 42, 45]`** **Answer: [78, 62, 31, 51, 34, 29, 30, 42, 45] (Option D).** A: **Incorrect:** Places `51` at index 2 and `31` at index 3, which does not follow the binary heap parent-child indices. B: **Incorrect:** Swaps `42` (index 7) and `45` (index 8). C: **Incorrect:** Swaps both `29`/`30` and `42`/`45`. D: **Correct:** After `delete_max()` yields `[62, 51, 31, 45, 34, 29, 30, 42]`, inserting `78` at index 8 bubbles up through indices 8 → 3 (`45`) → 1 (`51`) → 0 (`62`).

**1. Recurrence for the Minimum Number of Nodes \( N(h) \) in an AVL Tree of Height \( h \):** - Given that the empty tree has height \( 0 \) (\( N(0) = 0 \)) and a single-node tree has height \( 1 \) (\( N(1) = 1 \)), an AVL tree of height \( h \) with the minimum number of nodes has one subtree of height \( h - 1 \) and one subtree of height \( h - 2 \): \[ N(h) = 1 + N(h - 1) + N(h - 2) \] **2. Compute \( N(h) \) Up to \( h = 7 \):** - \( N(0) = 0 \) - \( 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 \) **Answer: 33.**

**1. Construct the Huffman Tree Step-by-Step:** - Note that the Weighted Path Length (WPL) of a Huffman tree equals the **sum of the frequencies of all internal (merged) nodes**. - Initial sorted frequencies: `\{2, 4, 6, 9, 16, 20\}` - **Merge 1:** Combine `2` and `4` \( \to \) internal node **`6`**. Remaining: `\{6, 6, 9, 16, 20\}`. - **Merge 2:** Combine `6` and `6` \( \to \) internal node **`12`**. Remaining: `\{9, 12, 16, 20\}`. - **Merge 3:** Combine `9` and `12` \( \to \) internal node **`21`**. Remaining: `\{16, 20, 21\}`. - **Merge 4:** Combine `16` and `20` \( \to \) internal node **`36`**. Remaining: `\{21, 36\}`. - **Merge 5:** Combine `21` and `36` \( \to \) root node **`57`**. **2. Calculate Total Weighted Path Length (WPL):** - Summing the internal nodes (or leaf depths: `2, 4` at depth 4; `6` at depth 3; `9, 16, 20` at depth 2): \[ \text{WPL} = 6 + 12 + 21 + 36 + 57 = 132 \] (Check via leaf depths: \( (2 + 4)\times 4 + 6\times 3 + (9 + 16 + 20)\times 2 = 24 + 18 + 90 = 132 \)). **Answer: 132.**

**1. Test the Greedy Coin Change Strategy for Target Amount = 6:** - **Option A (`{1, 2, 5}`):** Greedy picks `5 + 1` (2 coins), which is optimal. - **Option B (`{1, 3, 4}`):** - **Greedy choice:** Picks the largest coin \( \le 6 \), which is `4`, then must use two `1`s: `4 + 1 + 1 = 6` (**3 coins**). - **Optimal choice:** Uses two `3`s: `3 + 3 = 6` (**2 coins**). - Thus, the greedy strategy **fails** for `{1, 3, 4}`! - **Option C (`{1, 4, 5}`):** Greedy picks `5 + 1` (2 coins), which is optimal. - **Option D (`{1, 2, 3}`):** Greedy picks `3 + 3` (2 coins), which is optimal. **Answer: {1, 3, 4} (Option B).** A: **Incorrect:** For `{1, 2, 5}`, greedy chooses `5 + 1` (2 coins), which is the minimum possible. B: **Correct:** For `{1, 3, 4}`, greedy chooses `4 + 1 + 1` (3 coins) instead of the optimal `3 + 3` (2 coins). C: **Incorrect:** For `{1, 4, 5}`, greedy chooses `5 + 1` (2 coins), which is optimal. D: **Incorrect:** For `{1, 2, 3}`, greedy chooses `3 + 3` (2 coins), which is optimal.

**1. Check All Pairs \( (i, j) \) with \( i < j \) in `L = [5, 4, 1, 2, 3]` for \( L[i] > 2 \times L[j] \):** - **For `L[0] = 5`:** - \( (5, 4) \): \( 5 > 2(4) = 8 \) is False. - \( (5, 1) \): \( 5 > 2(1) = 2 \) is **True** (1st significant inversion). - \( (5, 2) \): \( 5 > 2(2) = 4 \) is **True** (2nd significant inversion). - \( (5, 3) \): \( 5 > 2(3) = 6 \) is False. - **For `L[1] = 4`:** - \( (4, 1) \): \( 4 > 2(1) = 2 \) is **True** (3rd significant inversion). - \( (4, 2) \): \( 4 > 2(2) = 4 \) is False (strict inequality `>`). - \( (4, 3) \): \( 4 > 2(3) = 6 \) is False. - **For `L[2] = 1` and `L[3] = 2`:** No subsequent elements satisfy \( L[i] > 2 \times L[j] \). **2. Total Count:** - There are **3** significant inversions: `(5, 1)`, `(5, 2)`, and `(4, 1)`. **Answer: 3 (Option C).** A: **Incorrect:** There are 5 standard inversions (`L[i] > L[j]`), but only 3 satisfy the strict condition `L[i] > 2 * L[j]`. B: **Incorrect:** `(4, 2)` has `4 == 2 * 2`, which does not satisfy strict inequality `L[i] > 2 * L[j]`. C: **Correct:** The 3 pairs satisfying `i < j` and `L[i] > 2 * L[j]` are `(5, 1)`, `(5, 2)`, and `(4, 1)`. D: **Incorrect:** Misses one of the three valid pairs.

**1. Apply the Master Theorem to \( T(n) = 3T(n/3) + n \):** - Comparing \( T(n) = 3T(n/3) + n \) with \( T(n) = a T(n/b) + f(n) \): - \( a = 3 \), \( b = 3 \), and \( f(n) = n \). - Compute the critical exponent: \[ n^{\log_b a} = n^{\log_3 3} = n^1 = n \] - Since \( f(n) = \Theta(n^{\log_b a}) = \Theta(n) \), Case 2 of the Master Theorem applies: \[ T(n) = \Theta(n \log n) = O(n \log n) \] **Answer: \( O(n \log n) \) (Option D).** A: **Incorrect:** The recursion tree has depth \( \log_3 n \) with \( O(n) \) work per level, not \( O(1) \). B: **Incorrect:** \( O(\log n) \) is the complexity of \( T(n) = T(n/3) + 1 \), not \( 3T(n/3) + n \). C: **Incorrect:** Each of the \( \log_3 n \) levels of the recursion tree performs \( n \) work, giving \( O(n \log n) \). D: **Correct:** By Case 2 of the Master Theorem (\( a = 3, b = 3, f(n) = n \)), \( T(n) = O(n \log n) \).

**1. Partition the 17-Element List into Blocks of 5 and Find Each Block's Median:** - Given list: `[2, 4, 5, 6, 3, 1, 8, 9, 12, 11, 19, 15, 16, 17, 11, 7, 21, 18, 28, 32]` (20 elements total). - Let us split into 4 blocks of 5 elements (`i = 0, 5, 10, 15`), sort each block `X`, and take `X[len(X)//2]` (`X[2]`): - **Block 1:** `[2, 4, 5, 6, 3]` \( \xrightarrow{\text{sort}} \) `[2, 3, 4, 5, 6]` \( \implies X[2] = 4 \) - **Block 2:** `[1, 8, 9, 12, 11]` \( \xrightarrow{\text{sort}} \) `[1, 8, 9, 11, 12]` \( \implies X[2] = 9 \) - **Block 3:** `[19, 15, 16, 17, 11]` \( \xrightarrow{\text{sort}} \) `[11, 15, 16, 17, 19]` \( \implies X[2] = 16 \) - **Block 4:** `[7, 21, 18, 28, 32]` \( \xrightarrow{\text{sort}} \) `[7, 18, 21, 28, 32]` \( \implies X[2] = 21 \) **2. Recursive Call `MoM(M)` on `M = [4, 9, 16, 21]`:** - Since `len(M) = 4 <= 5`, the base case sorts `M = [4, 9, 16, 21]` and returns `M[len(M)//2]` = `M[4 // 2]` = `M[2]` = **`16`**. **Answer: 16.**

**1. Compute Lengths and Longest Common Subsequence (LCS):** - Given strings: `X = 'XYITCRT'` (\( m = \text{len}(X) = 7 \)) and `Y = 'WTXITRY'` (\( n = \text{len}(Y) = 7 \)). - Let us find the Longest Common Subsequence of `'XYITCRT'` and `'WTXITRY'`: - Common subsequences include `'XITR'` (length 4) and `'XYTR'` / `'XITY'` (length 4). - Let us verify if any common subsequence of length 5 exists: `'W'` is not in `X`; `'C'` is not in `Y`; removing `'C'` from `X` leaves `'XYITRT'` (length 6) and removing `'W'` from `Y` leaves `'TXITRY'` (length 6). In `'XYITRT'` vs `'TXITRY'`, matching `'XITR'` has length **4**. - Thus \( l = \text{LCS}(X, Y) = 4 \). **2. Compute `m + n - l` (Shortest Common Supersequence Length):** \[ m + n - l = 7 + 7 - 4 = 10 \] **Answer: 10 (Option A).** A: **Correct:** With \( m = 7 \), \( n = 7 \), and \( l = \text{LCS}(\text{'XYITCRT'}, \text{'WTXITRY'}) = 4 \) (`'XITR'`), `m + n - l = 7 + 7 - 4 = 10`. B: **Incorrect:** Would require an LCS of length 5, which does not exist between the two strings. C: **Incorrect:** Would require an LCS of length 6. D: **Incorrect:** `7` is the length of each input string, not `m + n - l`.

**1. Count Unique Paths on the \( 4 \times 4 \) Grid Using Dynamic Programming (or Inclusion-Exclusion):** - Looking at the grid diagram from \((0, 0)\) to \((4, 4)\), note the coordinates of the two gray blockages (in the figure, one blockage is at \((1, 3)\) and one is at \((2, 2)\), or by symmetry \((3, 1)\) and \((2, 2)\)): - Total unrestricted paths from \((0, 0)\) to \((4, 4)\) = \( \binom{4 + 4}{4} = \binom{8}{4} = 70 \). - Paths passing through \( A = (2, 2) \): \[ N(A) = \binom{2+2}{2} \times \binom{2+2}{2} = 6 \times 6 = 36 \] - Paths passing through \( B = (3, 1) \) (or \((1, 3)\)): \[ N(B) = \binom{3+1}{1} \times \binom{1+3}{3} = 4 \times 4 = 16 \] - Note that no valid right/up path can pass through **both** \((3, 1)\) and \((2, 2)\) because \( 3 > 2 \) while \( 1 < 2 \), so \( N(A \cap B) = 0 \). **2. Subtract Blocked Paths from Total Paths:** \[ \text{Valid Paths} = 70 - 36 - 16 = 18 \] **Answer: 18.**

**1. Formulate Each Resource Constraint for Jackets \( x \) (Type X) and \( y \) (Type Y):** - **Fancy collars for Jacket X:** Only 200 collars per day \( \implies x \le 200 \) (Option A is valid). - **Collars for Jacket Y:** Only 500 collars per day \( \implies y \le 500 \) (Option B is valid). - **Leather supply:** Sufficient for 500 Jackets combined \( \implies x + y \le 500 \). - **Production time:** Each Jacket X takes **twice as much time** as a Jacket Y (1 unit of X = 2 units of Y in time), and the total time available can produce 1,000 Jackets of type Y: \[ 2x + y \le 1000 \] (Option C is valid). - Therefore, **`x + 2y <= 1000` (Option D)** reverses the time ratio and is **not a valid constraint**. **Answer: \( x + 2y \le 1000 \) (Option D).** A: **Incorrect:** \( x \le 200 \) is a valid constraint representing the 200 fancy collars available daily for Jacket X. B: **Incorrect:** \( y \le 500 \) is a valid constraint representing the 500 collars available daily for Jacket Y. C: **Incorrect:** Since Jacket X requires twice the time of Jacket Y, \( 2x + y \le 1000 \) is the valid production time constraint. D: **Correct:** \( x + 2y \le 1000 \) is not a valid constraint because it wrongly assumes Jacket Y takes twice as long as Jacket X.

**1. Analyze the Capacities of the Network Flow Graph:** - Directed edges and capacities: - \( c(s, a) = 10 \), \( c(s, b) = 5 \) - \( c(a, b) = 2 \) - \( c(a, t) = 4 \), \( c(b, t) = 8 \) **2. Find the Maximum Flow (and Minimum Cut) from \( s \) to \( t \):** - **Path 1 (\( s \to a \to t \)):** Send \( 4 \) units of flow (saturating edge \( (a, t) \) of capacity 4). - **Path 2 (\( s \to b \to t \)):** Send \( 5 \) units of flow (saturating edge \( (s, b) \) of capacity 5; remaining capacity on \( (b, t) \) is \( 8 - 5 = 3 \)). - **Path 3 (\( s \to a \to b \to t \)):** Send \( 2 \) units of flow (saturating edge \( (a, b) \) of capacity 2, since \( (s, a) \) has \( 10 - 4 = 6 \) left and \( (b, t) \) has \( 3 \) left). - Total flow = \( 4 + 5 + 2 = 11 \). - **Verify via Min-Cut \( (\{s, a\}, \{b, t\}) \):** \[ \text{Capacity}(\{s, a\}, \{b, t\}) = c(a, t) + c(a, b) + c(s, b) = 4 + 2 + 5 = 11 \] **Answer: 11 (Option C).** A: **Incorrect:** 9 only counts the direct paths \( s \to a \to t \) (4) and \( s \to b \to t \) (5), ignoring the 2 units routed via \( s \to a \to b \to t \). B: **Incorrect:** 10 is less than the min-cut capacity of 11. C: **Correct:** The minimum cut \( S = \{s, a\}, T = \{b, t\} \) has capacity \( c(a, t) + c(a, b) + c(s, b) = 4 + 2 + 5 = 11 \). D: **Incorrect:** Although \( c(a, t) + c(b, t) = 4 + 8 = 12 \), node \( b \) can receive at most \( c(s, b) + c(a, b) = 5 + 2 = 7 \) units of flow, limiting total flow to \( 4 + 7 = 11 \).