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

**1. Understand what `fun(m, n)` computes:** The given recursive function repeatedly subtracts the smaller number from the larger number until both numbers become equal (`m == n`), and then returns that common value: ```python def fun(m, n): if m == n: return n else: if m > n: return fun(m - n, n) else: return fun(m, n - m) ``` This is Euclid's subtraction-based algorithm for the **Greatest Common Divisor (GCD)** of `m` and `n`. **2. Trace `fun(48, 18)` step by step:** \[\text{fun}(48, 18) \to \text{fun}(30, 18) \to \text{fun}(12, 18) \to \text{fun}(12, 6) \to \text{fun}(6, 6) = 6\] **Answer: 6.**

**1. Relate the node counts by degree in a binary tree:** Let: - \(n_0\) = number of leaf nodes (nodes with 0 children) - \(n_1\) = number of nodes with exactly 1 child - \(n_2\) = number of nodes with exactly 2 children We are given the total number of nodes \(N = n_0 + n_1 + n_2 = 28\), and \(n_2 = 10\). **2. Use the binary tree leaf-count property \(n_0 = n_2 + 1\):** In any non-empty binary tree, the number of leaf nodes is always one more than the number of nodes with two children: \[n_0 = n_2 + 1 = 10 + 1 = 11\] (Proof: Total edges \(= N - 1 = n_0 + n_1 + n_2 - 1\), and total edges also equals the sum of out-degrees \(0\cdot n_0 + 1\cdot n_1 + 2\cdot n_2\). Equating the two gives \(n_0 = n_2 + 1\).) **3. Solve for \(n_1\):** Substitute \(n_0 = 11\) and \(n_2 = 10\) into \(n_0 + n_1 + n_2 = 28\): \[11 + n_1 + 10 = 28 \implies n_1 = 28 - 21 = 7\] **Answer: 7.**

**1. Trace the insertion of `60, 30, 50, 55, 80, 90, 65, 70, 10` into an empty BST:** Let the root be at depth \(0\): 1. `60`: root (depth 0). 2. `30`: left child of `60` (depth 1). 3. `50`: \(50 < 60, 50 > 30 \implies\) right child of `30` (depth 2). 4. `55`: \(55 < 60, 55 > 30, 55 > 50 \implies\) right child of `50` (depth 3). 5. `80`: \(80 > 60 \implies\) right child of `60` (depth 1). 6. `90`: \(90 > 60, 90 > 80 \implies\) right child of `80` (depth 2). 7. `65`: \(65 > 60, 65 < 80 \implies\) left child of `80` (depth 2). 8. `70`: \(70 > 60, 70 < 80, 70 > 65 \implies\) right child of `65` (depth 3). 9. `10`: \(10 < 60, 10 < 30 \implies\) left child of `30` (depth 2). **2. Identify all elements at the maximum depth and sum them:** The maximum depth in the BST is **depth 3**, which contains two elements: `55` (along `60 -> 30 -> 50 -> 55`) and `70` (along `60 -> 80 -> 65 -> 70`). Their sum is: \[55 + 70 = 125\] **Answer: 125.**

**1. Construct the Huffman tree for the given character probabilities:** We have 5 characters with probabilities: - \(E: 0.10\), \(D: 0.15\), \(C: 0.17\), \(B: 0.18\), \(A: 0.40\) Repeatedly merge the two nodes with the smallest probabilities: 1. **Step 1:** Merge \(E(0.10)\) and \(D(0.15)\) into \(N_1(DE) = 0.25\). Remaining probabilities: \(\{C: 0.17,\; B: 0.18,\; N_1(DE): 0.25,\; A: 0.40\}\). 2. **Step 2:** Merge \(C(0.17)\) and \(B(0.18)\) into \(N_2(BC) = 0.35\). Remaining probabilities: \(\{N_1(DE): 0.25,\; N_2(BC): 0.35,\; A: 0.40\}\). 3. **Step 3:** Merge \(N_1(DE)(0.25)\) and \(N_2(BC)(0.35)\) into \(N_3(BCDE) = 0.60\). Remaining probabilities: \(\{A: 0.40,\; N_3(BCDE): 0.60\}\). 4. **Step 4:** Merge \(A(0.40)\) and \(N_3(BCDE)(0.60)\) into the root \(R(1.00)\). **2. Find the bit length (depth) of each character and sum for the message `"ABCDE"`:** - \(A\): depth \(1\) (1 bit) - \(B\): \(R \to N_3 \to N_2 \to B\), depth \(3\) (3 bits) - \(C\): \(R \to N_3 \to N_2 \to C\), depth \(3\) (3 bits) - \(D\): \(R \to N_3 \to N_1 \to D\), depth \(3\) (3 bits) - \(E\): \(R \to N_3 \to N_1 \to E\), depth \(3\) (3 bits) Since the message `"ABCDE"` contains each of the 5 characters exactly once, the total number of bits is: \[1 + 3 + 3 + 3 + 3 = 13\] **Answer: 13.**

**1. Understand the definition of a significant inversion:** For the list `L = [14, 3, 8, 1, 6, 2, 5]`, a pair `(L[i], L[j])` with `i < j` is a **significant inversion** if: \[L[i] > 2 \times L[j]\] **2. Check each element `L[i]` against all subsequent elements `L[j]` (`j > i`):** - **For `L[0] = 14`** (need \(14 > 2 L[j] \iff L[j] < 7\)): The elements after `14` are `3, 8, 1, 6, 2, 5`. Those strictly less than `7` are `3, 1, 6, 2, 5` \(\implies \mathbf{5}\) significant inversions: `(14,3), (14,1), (14,6), (14,2), (14,5)`. - **For `L[1] = 3`** (need \(3 > 2 L[j] \iff L[j] < 1.5\)): Among `8, 1, 6, 2, 5`, only `1` is less than `1.5` \(\implies \mathbf{1}\) significant inversion: `(3,1)`. - **For `L[2] = 8`** (need \(8 > 2 L[j] \iff L[j] < 4\)): Among `1, 6, 2, 5`, those strictly less than `4` are `1, 2` \(\implies \mathbf{2}\) significant inversions: `(8,1), (8,2)`. - **For `L[3] = 1`** (need \(L[j] < 0.5\)): **0** significant inversions. - **For `L[4] = 6`** (need \(6 > 2 L[j] \iff L[j] < 3\)): Among `2, 5`, only `2` is less than `3` \(\implies \mathbf{1}\) significant inversion: `(6,2)`. - **For `L[5] = 2`** (need \(L[j] < 1\) among `[5]`): **0** significant inversions. **3. Sum the significant inversions:** \[5 + 1 + 2 + 0 + 1 + 0 = 9\] **Answer: 9.**

**1. Identify the dominant asymptotic growth term of each function:** - \(f_1(n) = 3n^2 + 2n = \Theta(n^2)\) (quadratic) - \(f_2(n) = 3n + (\log n)^2 = \Theta(n)\) (linear, since \((\log n)^2 = o(n)\)) - \(f_3(n) = \log(\log n) = \Theta(\log \log n)\) (double logarithmic) - \(f_4(n) = 10 \log n = \Theta(\log n)\) (logarithmic) - \(f_5(n) = 3n \log n = \Theta(n \log n)\) (linearithmic) **2. Order the growth rates from slowest-growing to fastest-growing:** Recall the standard hierarchy of asymptotic growth rates as \(n \to \infty\): \[\log(\log n) \ll \log n \ll n \ll n \log n \ll n^2\] Matching these to the given functions gives the increasing order: \[f_3(n),\; f_4(n),\; f_2(n),\; f_5(n),\; f_1(n)\] **Answer: D — f3(n), f4(n), f2(n), f5(n), f1(n).** A: **Incorrect:** This places \(f_1(n) = \Theta(n^2)\) before \(f_5(n) = \Theta(n \log n)\), whereas \(n \log n\) grows slower than \(n^2\). B: **Incorrect:** \(f_4(n) = 10 \log n\) grows much slower than linear \(f_2(n)\), linearithmic \(f_5(n)\), and quadratic \(f_1(n)\). C: **Incorrect:** \(f_3(n) = \log(\log n)\) grows strictly slower than \(f_4(n) = 10 \log n\). D: **Correct:** The growth rates satisfy \(\log(\log n) < \log n < n < n \log n < n^2\), corresponding to \(f_3, f_4, f_2, f_5, f_1\).

**1. Count the number of string comparisons in Merge Sort:** When sorting a list of \(n\) elements using Merge Sort, the recursion tree has height \(\lceil \log_2 n \rceil\), and each level performs at most \(n\) comparisons during the merge step. Thus, Merge Sort performs \(O(n \log n)\) **string comparisons** in the worst case. **2. Multiply by the cost of each string comparison:** Unlike comparing two integers in \(O(1)\) time, comparing two strings of length \(n\) lexicographically (character by character) takes \(O(n)\) time in the worst case. Multiplying the number of comparisons \(O(n \log n)\) by the cost per comparison \(O(n)\) gives the total time complexity: \[O(n \log n) \times O(n) = O(n^2 \log n)\] **Answer: B — O(n^2 log n).** A: **Incorrect:** \(O(n \log n)\) is the number of string comparisons, neglecting the \(O(n)\) cost of comparing two length-\(n\) strings. B: **Correct:** Merge Sort performs \(O(n \log n)\) comparisons, and each comparison between two strings of length \(n\) takes \(O(n)\) time, giving \(O(n^2 \log n)\) total time. C: **Incorrect:** Merge Sort takes \(\Theta(n \log n)\) comparisons, so with \(O(n)\)-time comparisons the bound includes the \(\log n\) factor. D: **Incorrect:** Even reading the input requires \(\Omega(n^2)\) time.

**1. Analyze Quicksort on a reverse-sorted array of size \(n\):** Suppose the input list is sorted in strictly decreasing (reverse) order: \(a_1 > a_2 > \dots > a_n\). - **Case I (Pivot = First element):** The first element \(a_1\) is the **maximum** element of the array. Partitioning puts the remaining \(n - 1\) elements into the left subarray (which remains in reverse order) and \(0\) elements into the right subarray. This produces the recurrence \(T(n) = T(n - 1) + \Theta(n)\), which solves to **\(O(n^2)\)**. - **Case II (Pivot = Last element):** The last element \(a_n\) is the **minimum** element of the array. Partitioning puts \(0\) elements into the left subarray and the remaining \(n - 1\) elements into the right subarray. This also produces the recurrence \(T(n) = T(n - 1) + \Theta(n)\), which solves to **\(O(n^2)\)**. **Answer: B — I : O(n^2) and II : O(n^2).** A: **Incorrect:** Picking the last element on a reverse-sorted array always selects the minimum element, which also degrades to \(O(n^2)\) time. B: **Correct:** On a reverse-sorted array, the first element is always the maximum and the last element is always the minimum; both choices create maximally unbalanced \((n-1, 0)\) splits and take \(O(n^2)\) time. C: **Incorrect:** Neither the first nor the last element gives a balanced split on a reverse-sorted input. D: **Incorrect:** Picking the first element on a reverse-sorted array selects the maximum element at every step, taking \(O(n^2)\) time.

**1. Analyze the singly linked list structure (with only a `head` pointer):** Each `Node` has a `next` pointer (`self.next`), and the list maintains **only a `head` pointer** to the first node (no `tail` pointer and no `prev` pointers). **2. Determine the time complexity of each of the 4 operations on an \(n\)-node list:** 1. **Insertion at the first position:** Create the new node, set `new_node.next = head`, and update `head = new_node`. This takes **\(O(1)\)** time. 2. **Insertion at the last position:** Because there is no `tail` pointer, we must traverse all \(n\) nodes starting from `head` to reach the last node before appending. This takes **\(O(n)\)** time. 3. **Deletion of the first node:** Simply update `head = head.next`. This takes **\(O(1)\)** time. 4. **Deletion of the last node:** Even if we had a `tail` pointer, in a singly linked list we must find the **second-to-last node** (to set its `next = None`), which requires traversing \(n - 1\) nodes from `head`. This takes **\(O(n)\)** time. Thus, the respective complexities are \(O(1),\; O(n),\; O(1),\; O(n)\). **Answer: B — O(1), O(n), O(1), O(n).** A: **Incorrect:** Without a `tail` pointer, inserting at the end of a singly linked list requires traversing all \(n\) nodes from `head` in \(O(n)\) time. B: **Correct:** Updating `head` (insert/delete at front) takes \(O(1)\) time, while reaching the end of the list (insert/delete at end) requires an \(O(n)\) traversal from `head`. C: **Incorrect:** Inserting a node at the front (`head`) only updates two pointers in \(O(1)\) time. D: **Incorrect:** Deleting the first node only updates `head = head.next` in \(O(1)\) time.

**1. Trace the Breadth-First Search (BFS) level by level starting from `A`:** We visit neighbors in alphabetical order using a FIFO queue: - **Start at `A` (Level 0):** Visited: `A`. Neighbors of `A` in alphabetical order are `B, D, E`. Queue: `[B, D, E]`. - **Dequeue `B`:** Visited: `A, B`. Unvisited neighbors of `B`: `C` (and `E` is already in queue). Queue: `[D, E, C]`. - **Dequeue `D`:** Visited: `A, B, D`. Unvisited neighbors of `D`: `F, G`. Queue: `[E, C, F, G]`. - **Dequeue `E`:** Visited: `A, B, D, E`. Unvisited neighbors of `E`: `H` (`C` and `F` are already in queue). Queue: `[C, F, G, H]`. - **Dequeue `C`:** Visited: `A, B, D, E, C`. Unvisited neighbors of `C`: `I` (`H` is already in queue). Queue: `[F, G, H, I]`. - **Dequeue `F`:** Visited: `A, B, D, E, C, F`. Unvisited neighbors of `F`: `J` (`G, H` already in queue). Queue: `[G, H, I, J]`. - **Dequeue `G, H, I, J`:** None have any remaining unvisited neighbors. **2. Write out the complete BFS traversal sequence:** `A, B, D, E, C, F, G, H, I, J`. **Answer: A — A, B, D, E, C, F, G, H, I, J.** A: **Correct:** Starting at `A`, Level 1 visits `B, D, E`; their unvisited neighbors enqueued in order are `C` (from `B`), `F, G` (from `D`), and `H` (from `E`), followed by `I` (from `C`) and `J` (from `F`). B: **Incorrect:** `B` is dequeued before `D`, so `B`'s neighbor `C` is enqueued and visited before `D`'s neighbor `F`. C: **Incorrect:** This order (`A, B, C, H, J, ...`) corresponds to a Depth-First Search (DFS), not a Breadth-First Search (BFS). D: **Incorrect:** Both `F` and `G` are neighbors of `D` (which is dequeued before `E`), so `G` is enqueued before `E`'s neighbor `H`.

**1. Recall the DFS `pre` and `post` interval conditions for edge types in a directed graph:** During a Depth-First Search (DFS), each vertex \(x\) has a discovery time `pre[x]` and a finishing time `post[x]`, defining the interval \([\text{pre}[x], \text{post}[x]]\): - **Tree / Forward edge \((u, v)\):** \(u\) is an ancestor of \(v\), so \(v\)'s interval is nested inside \(u\)'s interval: \[\text{pre}[u] < \text{pre}[v] < \text{post}[v] < \text{post}[u]\] - **Back edge \((u, v)\):** \(v\) is an ancestor of \(u\), so \(u\)'s interval is nested inside \(v\)'s interval: \[\text{pre}[v] < \text{pre}[u] < \text{post}[u] < \text{post}[v]\] - **Cross edge \((u, v)\):** \(v\) was completely visited and finished *before* \(u\) was even discovered, so their intervals are **disjoint** with \(v\)'s interval coming strictly before \(u\)'s interval: \[\text{pre}[v] < \text{post}[v] < \text{pre}[u] < \text{post}[u]\] **2. Check the four options:** - **Option A:** `pre[v] = 3 < post[v] = 6 < pre[u] = 8 < post[u] = 9`. The intervals `[3, 6]` and `[8, 9]` are disjoint with `v` finishing before `u` starts \(\implies\) **Cross edge!** - **Option B:** `[5, 8]` is inside `[2, 11]` \(\implies\) Tree or Forward edge. - **Option C:** `[6, 7]` is inside `[1, 12]` \(\implies\) Back edge. - **Option D:** `[4, 7]` is inside `[3, 10]` \(\implies\) Tree or Forward edge. **Answer: A — pre[u] = 8, post[u] = 9, pre[v] = 3, post[v] = 6.** A: **Correct:** Since `pre[v] = 3 < post[v] = 6 < pre[u] = 8 < post[u] = 9`, node `v` finished completely before `u` was discovered, which is the exact condition for a cross edge. B: **Incorrect:** Here `pre[u] = 2 < pre[v] = 5 < post[v] = 8 < post[u] = 11`, meaning `v` is a descendant of `u` (a tree or forward edge). C: **Incorrect:** Here `pre[v] = 1 < pre[u] = 6 < post[u] = 7 < post[v] = 12`, meaning `v` is an ancestor of `u` (a back edge). D: **Incorrect:** Here `pre[u] = 3 < pre[v] = 4 < post[v] = 7 < post[u] = 10`, which is a tree or forward edge.

**1. Understand why shortest paths fail to exist in the presence of reachable negative cycles:** Suppose a graph contains a reachable cycle \(C\) whose edge weights sum to a strictly negative number (\(w(C) < 0\)). Any walk from the source \(s\) to a vertex \(v\) that passes through \(C\) can traverse the cycle \(C\) an arbitrary number of times \(k \to \infty\), reducing the total path weight by \(|w(C)|\) on every loop toward \(-\infty\). **2. Conclude:** Because there is no minimum possible walk weight (the infimum is \(-\infty\)), **the notion of a shortest path is not well-defined** when negative cycles are present. **Answer: B — The notion of the shortest path is not well-defined if there are negative cycles.** A: **Incorrect:** Running Bellman-Ford for more iterations would never converge because traversing the negative cycle keeps decreasing the distance indefinitely. B: **Correct:** When a negative-weight cycle is reachable, going around the cycle repeatedly drives the path cost to \(-\infty\), so no finite shortest path exists. C: **Incorrect:** If simple paths (no repeated vertices) are required, finding the shortest simple path with negative cycles is NP-hard, not why Bellman-Ford stops; Bellman-Ford's unrestricted shortest walk is simply \(-\infty\). D: **Incorrect:** All-pairs shortest paths (like Floyd-Warshall) also fail when negative cycles exist for the exact same reason.

**1. Trace the AVL tree insertions for `8, 4, 1, 3, 9, 2, 11` step by step:** 1. **Insert `8, 4, 1`:** `8 -> left 4 -> left 1` causes an LL imbalance at `8`. A right rotation makes `4` the root, with left child `1` and right child `8`. 2. **Insert `3`:** `3 < 4` and `3 > 1`, so `3` becomes the right child of `1`. (Tree is balanced: root `4`, left `1` with right child `3`, right `8`.) 3. **Insert `9`:** `9 > 4` and `9 > 8`, so `9` becomes the right child of `8`. (Tree is balanced at depth 2.) 4. **Insert `2`:** `2 < 4, 2 > 1, 2 < 3`, so `2` becomes the left child of `3`. Now node `1` has left height 0 and right height 2 (`3 -> 2`), causing a **Right-Left (RL) imbalance at node `1`**! Performing an RL rotation on `1 -> 3 -> 2` makes `2` the new left child of root `4`, with `1` as the left child of `2` and `3` as the right child of `2`. 5. **Insert `11`:** `11 > 4, 11 > 8, 11 > 9`, so `11` is inserted as the right child of `9`. This causes an **RR imbalance at node `8`** (`8 -> 9 -> 11`). Performing a left rotation at `8` makes `9` the new right child of root `4`, with `8` as the left child of `9` and `11` as the right child of `9`. **2. Identify the leaf nodes of the final AVL tree:** The final AVL tree has: - Root: `4` - Left child of `4`: `2` (with leaf children `1` and `3`) - Right child of `4`: `9` (with leaf children `8` and `11`) Thus, the leaf elements are **1, 3, 8, 11**. **Answer: A — 1, 3, 8, 11.** A: **Correct:** After the RL rotation at `1` (making `2` the parent of leaves `1` and `3`) and the RR rotation at `8` (making `9` the parent of leaves `8` and `11`), the leaves are `1, 3, 8, 11`. B: **Incorrect:** Inserting `11` triggers a left rotation at `8 -> 9 -> 11`, making `9` an internal node and `8` a leaf. C: **Incorrect:** The RL rotation at `1 -> 3 -> 2` makes `2` an internal node with leaf children `1` and `3`. D: **Incorrect:** `2` becomes the parent of `1` and `3` after the RL rotation, so `3` (not `2`) is a leaf.

**1. Recall the Earliest Deadline First (EDF) greedy algorithm for minimizing maximum lateness:** To minimize the maximum lateness \(L_{\max} = \max_i \max(0, f_i - D_i)\) when scheduling single-server activities without preemption starting at \(t = 0\), Jackson's theorem proves that scheduling tasks in **non-decreasing order of their deadlines \(D_i\)** (Earliest Deadline First) is always optimal! **2. Sort the 7 activities by their deadlines \(D_i\):** From the given table: - \(A_6\): Duration \(T_6 = 2\), Deadline \(D_6 = 2\) - \(A_2\): Duration \(T_2 = 2\), Deadline \(D_2 = 4\) - \(A_4\): Duration \(T_4 = 4\), Deadline \(D_4 = 7\) - \(A_3\): Duration \(T_3 = 1\), Deadline \(D_3 = 9\) - \(A_7\): Duration \(T_7 = 5\), Deadline \(D_7 = 12\) - \(A_1\): Duration \(T_1 = 4\), Deadline \(D_1 = 14\) - \(A_5\): Duration \(T_5 = 3\), Deadline \(D_5 = 19\) **3. Compute the completion time \(f_i\) and lateness \(L_i = \max(0, f_i - D_i)\) for each activity:** - **\(A_6\):** finishes at \(f_6 = 0 + 2 = 2\). Lateness \(= 2 - 2 = 0\). - **\(A_2\):** finishes at \(f_2 = 2 + 2 = 4\). Lateness \(= 4 - 4 = 0\). - **\(A_4\):** finishes at \(f_4 = 4 + 4 = 8\). Lateness \(= 8 - 7 = 1\). - **\(A_3\):** finishes at \(f_3 = 8 + 1 = 9\). Lateness \(= 9 - 9 = 0\). - **\(A_7\):** finishes at \(f_7 = 9 + 5 = 14\). Lateness \(= 14 - 12 = 2\). - **\(A_1\):** finishes at \(f_1 = 14 + 4 = 18\). Lateness \(= 18 - 14 = 4\). - **\(A_5\):** finishes at \(f_5 = 18 + 3 = 21\). Lateness \(= 21 - 19 = 2\). The maximum lateness in this optimal EDF schedule is \(\max(0, 0, 1, 0, 2, 4, 2) = 4\). **Answer: C — 4.** A: **Incorrect:** The first six tasks (\(A_6, A_2, A_4, A_3, A_7, A_1\)) all have deadlines \(\le 14\), and their total duration is \(2 + 2 + 4 + 1 + 5 + 4 = 18\), so the last of them must finish at \(t \ge 18\) and be late by at least \(18 - 14 = 4\). B: **Incorrect:** Since the 6 tasks with deadline \(\le 14\) require \(18\) units of time, at least one task has lateness \(\ge 18 - 14 = 4\). C: **Correct:** Scheduling by Earliest Deadline First (`A6, A2, A4, A3, A7, A1, A5`) yields completion times `2, 4, 8, 9, 14, 18, 21` and maximum lateness \(18 - 14 = 4\). D: **Incorrect:** A lateness of 4 is achievable using the Earliest Deadline First schedule.

**1. Apply the Master Theorem to \(T(n) = 4T(n/2) + n^2\):** For a divide-and-conquer recurrence of the form \(T(n) = aT(n/b) + f(n)\): - \(a = 4\) (number of subproblems) - \(b = 2\) (factor by which input size shrinks) - \(f(n) = n^2\) (work done outside recursive calls) **2. Compare \(f(n)\) with \(n^{\log_b a}\):** Compute the critical exponent: \[\log_b a = \log_2 4 = 2 \implies n^{\log_b a} = n^2\] Since \(f(n) = n^2 = \Theta(n^{\log_b a})\), this falls into **Case 2 of the Master Theorem** (each of the \(\log_2 n\) levels of the recursion tree contributes \(\Theta(n^2)\) work). Therefore: \[T(n) = O(n^2 \log n)\] **Answer: C — O(n^2 log n).** A: **Incorrect:** Even the top level of recursion performs \(n^2\) work, so \(O(n)\) is impossible. B: **Incorrect:** \(O(n \log n)\) corresponds to \(T(n) = 2T(n/2) + n\), not \(4T(n/2) + n^2\). C: **Correct:** By Case 2 of the Master Theorem, \(n^{\log_2 4} = n^2 = \Theta(f(n))\), giving \(T(n) = O(n^2 \log n)\). D: **Incorrect:** \(O(n^2)\) overlooks the \(\log_2 n\) levels of recursion, each costing \(n^2\).

**1. Understand the teacher-subject assignment problem:** We have \(n\) teachers \(T_1, \dots, T_n\) and \(2n\) subjects \(S_1, \dots, S_{2n}\). - Each of the \(n\) teachers must teach **exactly 2 subjects**. - Since there are \(n\) teachers each teaching \(2\) subjects and \(2n\) subjects in total, each subject is taught by **exactly 1 teacher**. - Directed edges \((T_i, S_j)\) represent which subjects teacher \(T_i\) is willing/able to teach (each teacher can teach at most 1 copy of a given subject, so internal edge capacities are \(1\)). **2. Set up the capacities in the Maximum Flow formulation:** - Connect a source node \(s\) to every teacher node \(T_i\) with **capacity \(2\)** (so each teacher can be assigned at most 2 subjects). - Connect every subject node \(S_j\) to a sink node \(t\) with **capacity \(1\)** (so each subject is assigned to at most 1 teacher). A valid assignment exists if and only if the maximum \(s\)-\(t\) flow has value \(2n\). **Answer: C — It can be modelled as a network flow problem, where the source node is connected to every teacher node in G with capacity of 2, and every subject node in G is connected to the sink node with capacity of 1.** A: **Incorrect:** Connecting teachers with capacity \(n\) and subjects with capacity \(2n\) would allow one teacher to teach up to \(n\) subjects and a subject to be taught \(2n\) times. B: **Incorrect:** Equal capacities on all edges fail to enforce that each teacher teaches 2 subjects while each subject is taught by only 1 teacher. C: **Correct:** Giving source-to-teacher edges capacity `2` and subject-to-sink edges capacity `1` ensures that a max flow of `2n` assigns exactly 2 distinct subjects to each teacher. D: **Incorrect:** This reverses the capacities, giving each teacher only 1 subject and each subject 2 teachers.

**1. Identify the decision variables and objective function:** Let \(X_1\) be the number of units of gadget A and \(X_2\) be the number of units of gadget B produced per day. Since profit is Rs. 6 per unit of A and Rs. 4 per unit of B, the objective is to: \[\text{Maximize } Z = 6X_1 + 4X_2\] **2. Formulate the machine time constraints (in minutes):** - **Machine M (available for 6 hours = 360 minutes):** One unit of A needs \(2\) minutes and one unit of B needs \(1\) minute: \[2X_1 + X_2 \le 360\] - **Machine N (available for 7 hours = 420 minutes):** One unit of A needs \(1\) minute and one unit of B needs \(2\) minutes: \[X_1 + 2X_2 \le 420\] - **Non-negativity constraints:** \[X_1 \ge 0, \quad X_2 \ge 0\] **Answer: A — Maximize Z = 6X_1 + 4X_2 subject to 2X_1 + X_2 <= 360, X_1 + 2X_2 <= 420, X_1 >= 0, X_2 >= 0.** A: **Correct:** The objective \(6X_1 + 4X_2\) and machine minute constraints \(2X_1 + X_2 \le 360\) and \(X_1 + 2X_2 \le 420\) with \(X_1, X_2 \ge 0\) match all problem specifications. B: **Incorrect:** The coefficients of \(X_1\) and \(X_2\) on Machine M and Machine N are misassigned as `1, 1` and `2, 2`. C: **Incorrect:** This swaps the profit coefficients with the machine availability limits and mixes minutes with hours. D: **Incorrect:** The second constraint uses `>= 420` instead of `<= 420` and omits the non-negativity constraints.

**1. Apply Gallai's Identity for Vertex Cover and Independent Set:** In any simple graph \(G = (V, E)\) with \(n = |V|\) vertices, the complement of a vertex cover is an independent set, and vice versa. Therefore, the size of the minimum vertex cover \(\beta(G)\) and the size of the maximum independent set \(\alpha(G)\) satisfy: \[\alpha(G) + \beta(G) = n\] (Note that the number of edges \(|E| = 50\) is extra information not needed for this identity.) **2. Calculate the size of the maximum independent set:** Given \(n = 25\) vertices and \(\beta(G) = 10\): \[\alpha(G) = 25 - 10 = 15\] **Answer: C — 15.** A: **Incorrect:** An independent set is a subset of the \(25\) vertices, so its size can never exceed \(25\). B: **Incorrect:** `90` exceeds the total number of vertices \(25\). C: **Correct:** By Gallai's identity, \(\alpha(G) = |V| - \beta(G) = 25 - 10 = 15\). D: **Incorrect:** This adds \(25 + 10 = 35\) instead of subtracting \(25 - 10 = 15\).

**1. Compute the home hash slot \(h(k) = (2k + 3) \bmod 10\) for each key in the table:** The final table has 7 keys placed at indices `3` through `9`: - Index 3: key `40` \(\implies h(40) = (80 + 3) \bmod 10 = 3\) (at home slot `3`, **0 probes**). - Index 4: key `25` \(\implies h(25) = (50 + 3) \bmod 10 = 3\) (home slot `3`, shifted to `4`; **must be inserted AFTER `40`**). - Index 5: key `21` \(\implies h(21) = (42 + 3) \bmod 10 = 5\) (at home slot `5`, **0 probes**). - Index 6: key `31` \(\implies h(31) = (62 + 3) \bmod 10 = 5\) (home slot `5`, shifted to `6`; **must be inserted AFTER `21`**). - Index 7: key `32` \(\implies h(32) = (64 + 3) \bmod 10 = 7\) (at home slot `7`, **0 probes**). - Index 8: key `27` \(\implies h(27) = (54 + 3) \bmod 10 = 7\) (home slot `7`, shifted to `8`; **must be inserted AFTER `32`**). - Index 9: key `12` \(\implies h(12) = (24 + 3) \bmod 10 = 7\) (home slot `7`, shifted past `7` and `8` to `9`; **must be inserted AFTER both `32` and `27`**). **2. Check the precedence conditions on each option:** We need: (1) `40` before `25`, (2) `21` before `31`, and (3) `32` before `27` before `12` (and the exact 7 keys from the table): - **Option A (`21, 32, 27, 12, 31, 40, 25`):** `40` is before `25`, `21` is before `31`, and `32 -> 27 -> 12` is in order. (**Valid!**) - **Option B (`21, 32, 27, 12, 25, 31, 40`):** `25` is inserted *before* `40`, which would put `25` at Index 3 and `40` at Index 4! (**Invalid.**) - **Option C (`40, 32, 21, 25, 31, 12, 17`):** Contains `17` instead of `27`, and `12` before `17/27` would put `12` at Index 8. (**Invalid.**) - **Option D (`40, 32, 21, 25, 31, 27, 12`):** `40` is before `25`, `21` is before `31`, and `32 -> 27 -> 12` is in order. (**Valid!**) **Answer: A, D — 21, 32, 27, 12, 31, 40, 25 and 40, 32, 21, 25, 31, 27, 12.** A: **Correct:** In this sequence, `40` precedes `25` (filling slots 3 then 4), `21` precedes `31` (filling slots 5 then 6), and `32, 27, 12` appear in order (filling slots 7, 8, then 9). B: **Incorrect:** Here `25` (with \(h(25)=3\)) appears before `40` (with \(h(40)=3\)), so `25` would take slot 3 and `40` would be pushed to slot 4. C: **Incorrect:** This list contains key `17` (which is not in the table) and places `12` before the second key hashing to `7`. D: **Correct:** All three probing chains (`40 -> 25` at 3..4, `21 -> 31` at 5..6, and `32 -> 27 -> 12` at 7..9) are inserted in the required topological order.

**1. Model the prerequisite structure as a Directed Acyclic Graph (DAG):** Since there is no limit on how many modules a student can take in a single term, the minimum number of terms required to complete all 10 modules equals the number of vertices in the **longest prerequisite chain** (critical path) in the DAG. **2. Determine the earliest term \(T(m)\) in which each module \(m\) can be taken:** - **Term 1:** Module 6 has **None** as prerequisite \(\implies T(6) = 1\). - **Term 2:** - Module 1 requires Module 6 \(\implies T(1) = T(6) + 1 = 2\). - Module 2 requires Module 6 \(\implies T(2) = T(6) + 1 = 2\). - **Term 3:** - Module 3 requires Module 1 \(\implies T(3) = T(1) + 1 = 3\). - Module 5 requires Module 2 \(\implies T(5) = T(2) + 1 = 3\). - **Term 4:** - Module 4 requires Module 1 and Module 3 \(\implies T(4) = \max(T(1), T(3)) + 1 = 3 + 1 = 4\). - Module 8 requires Module 5 \(\implies T(8) = T(5) + 1 = 4\). - **Term 5:** - Module 7 requires Module 4 \(\implies T(7) = T(4) + 1 = 5\). - Module 10 requires Module 8 \(\implies T(10) = T(8) + 1 = 5\). - **Term 6:** - Module 9 requires Module 7 \(\implies T(9) = T(7) + 1 = 6\). **3. Conclude:** The longest prerequisite chain is \(6 \to 1 \to 3 \to 4 \to 7 \to 9\), which has length **6**, requiring a minimum of **6 terms**. **Answer: 6.**

**1. Set up the Dynamic Programming recurrence for the Frog Jump problem:** We have 6 stones (indexed \(0\) to \(5\)) with heights: \[h = [10,\; 15,\; 30,\; 20,\; 28,\; 36]\] Let \(\text{dp}[i]\) be the minimum total cost to reach stone \(i\) starting from stone \(0\). Since the frog can jump from \(i - 1\) or \(i - 2\): - \(\text{dp}[0] = 0\) - \(\text{dp}[1] = |h_1 - h_0| = |15 - 10| = 5\) - For \(i \ge 2\): \[\text{dp}[i] = \min\big(\text{dp}[i-1] + |h_i - h_{i-1}|,\; \text{dp}[i-2] + |h_i - h_{i-2}|\big)\] **2. Compute \(\text{dp}[2], \text{dp}[3], \text{dp}[4], \text{dp}[5]\) step by step:** - **Stone 2 (\(h_2 = 30\)):** \[\text{dp}[2] = \min(\text{dp}[1] + |30 - 15|,\; \text{dp}[0] + |30 - 10|) = \min(5 + 15,\; 0 + 20) = 20\] - **Stone 3 (\(h_3 = 20\)):** \[\text{dp}[3] = \min(\text{dp}[2] + |20 - 30|,\; \text{dp}[1] + |20 - 15|) = \min(20 + 10,\; 5 + 5) = 10\] (via \(0 \to 1 \to 3\): \(|15-10| + |20-15| = 5 + 5 = 10\)). - **Stone 4 (\(h_4 = 28\)):** \[\text{dp}[4] = \min(\text{dp}[3] + |28 - 20|,\; \text{dp}[2] + |28 - 30|) = \min(10 + 8,\; 20 + 2) = 18\] (via \(0 \to 1 \to 3 \to 4\): \(10 + 8 = 18\)). - **Stone 5 (\(h_5 = 36\)):** \[\text{dp}[5] = \min(\text{dp}[4] + |36 - 28|,\; \text{dp}[3] + |36 - 20|) = \min(18 + 8,\; 10 + 16) = 26\] (via \(0 \to 1 \to 3 \to 5\) or \(0 \to 1 \to 3 \to 4 \to 5\), both costing \(26\)). **Answer: 26.**

**1. Apply Dijkstra's algorithm to find shortest paths from node `0`:** From the given weighted graph with vertices `0, 1, 2, 3, 4, 5`: - Direct edges from `0`: to `2` (weight `2`) and to `1` (weight `4`). - From `2` (distance `2`): - Edge `(2, 1)` of weight `1` relaxes `dist[1] = min(4, 2 + 1) = 3` (path `0 -> 2 -> 1`, distance **3**). - Edge `(2, 3)` of weight `4` gives `dist[3] = 2 + 4 = 6`. - From `1` (distance `3`): - Edge `(1, 3)` of weight `2` relaxes `dist[3] = min(6, 3 + 2) = 5` (path `0 -> 2 -> 1 -> 3`, distance **5**). - From `3` (distance `5`): - Edge `(3, 5)` of weight `2` gives `dist[5] = 5 + 2 = 7` (path `0 -> 2 -> 1 -> 3 -> 5`, distance **7**). - Edge `(3, 4)` of weight `4` gives `dist[4] = 5 + 4 = 9`. - From `5` (distance `7`): - Edge `(5, 4)` of weight `1` relaxes `dist[4] = min(9, 7 + 1) = 8` (path `0 -> 2 -> 1 -> 3 -> 5 -> 4`, distance **8**). **2. Collect the shortest distances to `(1, 2, 3, 4, 5)` in order:** - `dist[1] = 3` - `dist[2] = 2` - `dist[3] = 5` - `dist[4] = 8` - `dist[5] = 7` Thus, the sequence is **3, 2, 5, 8, 7**. **Answer: C — 3, 2, 5, 8, 7.** A: **Incorrect:** For node `4` and `5`, the path `0 -> 2 -> 1 -> 3 -> 5` gives `dist[5] = 7`, and continuing along `(5, 4)` of weight `1` gives `dist[4] = 8` (not `9, 8`). B: **Incorrect:** Going via `0 -> 2 -> 1` gives `dist[1] = 2 + 1 = 3` (shorter than the direct edge `4`), which also reduces `dist[3]` to `3 + 2 = 5`. C: **Correct:** The shortest distances are `dist[1] = 3` (`0->2->1`), `dist[2] = 2` (`0->2`), `dist[3] = 5` (`0->2->1->3`), `dist[4] = 8` (`0->2->1->3->5->4`), and `dist[5] = 7` (`0->2->1->3->5`). D: **Incorrect:** This swaps the distances of node `4` (`8`) and node `5` (`7`).

**1. Analyze the edges of graph \(G\) to construct its Minimum Spanning Trees (MSTs):** The graph \(G\) has 5 vertices \(\{a, b, c, d, e\}\) (so every spanning tree has \(5 - 1 = 4\) edges). - Notice that edge \((b, e)\) has weight \(1\) (the unique minimum-weight edge incident to \(e\) / cut edge across the minimum cut), so **\((b, e)\) must be part of every MST**. - Edge \((d, e)\) is the heaviest edge on the cycle involving \(d\) and \(e\) (weight \(7\)), so by the **Cycle Property**, **\((d, e)\) can never be part of any MST**. - Summing the 4 edges chosen by Kruskal's/Prim's algorithm gives a total MST weight of **10** (and by uniqueness of MST total weight, **every MST of a connected graph has the exact same total weight of 10**). **2. Conclude:** Statements A, C, and D are correct, while B and E are incorrect. **Answer: A, C, D — The total weight of every MST is 10, edge (d, e) will not be part of any MST, and edge (b, e) will be part of every MST.** A: **Correct:** Kruskal's/Prim's algorithm selects 4 edges whose weights sum to `10`, and all MSTs of a graph share the exact same total weight. B: **Incorrect:** The minimum spanning tree weight is `10`, not `11`. C: **Correct:** By the cycle property of MSTs, `(d, e)` is the unique heaviest edge on its cycle and cannot belong to any MST. D: **Correct:** By the cut property of MSTs, `(b, e)` is the unique lightest edge crossing its cut and must belong to every MST. E: **Incorrect:** Counting the tied-weight edge choices yields a different number of MSTs than 2.