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

We are given the relation \( \text{Library}(\text{BookID}, \text{Title}, \text{Author}, \text{Publisher}, \text{Year}) \) with functional dependencies: - \( \text{BookID} \rightarrow \text{Title}, \text{Author} \) - \( \text{Author}, \text{Year} \rightarrow \text{Publisher} \) - \( \text{Publisher} \rightarrow \text{Year} \) **1. Condition for Lossless Join Decomposition into \( L_1 \) and \( L_2 \):** A decomposition of \( R \) into \( L_1 \) and \( L_2 \) is **lossless** if and only if: 1. \( L_1 \cup L_2 = R \) (all attributes of \( R \) are preserved), and 2. \( (L_1 \cap L_2) \rightarrow L_1 \) or \( (L_1 \cap L_2) \rightarrow L_2 \) holds in \( \mathcal{F}^+ \) (the common attributes form a superkey for at least one of the two relations). **2. Testing Option B:** - \( L_1(\text{BookID}, \text{Title}, \text{Author}) \) and \( L_2(\text{BookID}, \text{Year}, \text{Publisher}) \). - Union: \( L_1 \cup L_2 = \{\text{BookID}, \text{Title}, \text{Author}, \text{Year}, \text{Publisher}\} = \text{Library} \). - Intersection: \( L_1 \cap L_2 = \{\text{BookID}\} \). - Closure of intersection: Since \( \text{BookID} \rightarrow \text{Title}, \text{Author} \), we have \( \{\text{BookID}\}^+ = \{\text{BookID}, \text{Title}, \text{Author}\} = L_1 \). Thus \( L_1 \cap L_2 \rightarrow L_1 \), making Option B a lossless join decomposition! **Answer: L1(BookID, Title, Author), L2(BookID, Year, Publisher) (Option B).** A: **Incorrect:** Here `L1 ∩ L2 = {BookID}`. The closure `{BookID}+ = {BookID, Title, Author}` covers neither `L1(BookID, Author, Year)` nor `L2(Publisher, Title, BookID)`. B: **Correct:** The common attribute is `BookID`, and since `BookID -> Title, Author`, `L1 ∩ L2` is a superkey of `L1(BookID, Title, Author)`, guaranteeing a lossless join. C: **Incorrect:** `L1 ∩ L2 = ∅` (no common attributes), so joining them produces a Cartesian product (lossy). D: **Incorrect:** `L1 ∩ L2 = {Publisher}`. Since `{Publisher}+ = {Publisher, Year}`, it does not determine all of `L1` or `L2` (since `Title` is in `L2`), so it is lossy.

Let us trace **Dijkstra's algorithm** starting from source vertex \( P \) on the given directed weighted graph (breaking ties alphabetically): **Graph Edges:** - From \( P \): \( P \rightarrow S \) (7), \( P \rightarrow R \) (2) - From \( R \): \( R \rightarrow S \) (4), \( R \rightarrow T \) (1), \( R \rightarrow U \) (3) - From \( T \): \( T \rightarrow S \) (2), \( T \rightarrow Q \) (8) - From \( S \): \( S \rightarrow Q \) (5) - From \( U \): \( U \rightarrow Q \) (4), \( U \rightarrow V \) (2) - From \( V \): \( V \rightarrow Q \) (1) **Step-by-Step Distance Updates & Visited Order:** **1. Visit \( P \) (dist = 0):** - Relax edges from \( P \): \( d(R) = 2 \), \( d(S) = 7 \). Unvisited min is \( R \) (2). **2. Visit \( R \) (dist = 2):** - Relax edges from \( R \): \( d(T) = 2 + 1 = 3 \), \( d(U) = 2 + 3 = 5 \), \( d(S) = \min(7, 2 + 4) = 6 \). Unvisited min is \( T \) (3). **3. Visit \( T \) (dist = 3):** - Relax edges from \( T \): \( d(S) = \min(6, 3 + 2) = 5 \), \( d(Q) = 3 + 8 = 11 \). - Now both \( S \) and \( U \) have minimum distance \( 5 \). By alphabetical tie-breaking, \( S \) comes before \( U \)! **4. Visit \( S \) (dist = 5):** - Relax edge from \( S \): \( d(Q) = \min(11, 5 + 5) = 10 \). Next min is \( U \) (5). **5. Visit \( U \) (dist = 5):** - Relax edges from \( U \): \( d(V) = 5 + 2 = 7 \), \( d(Q) = \min(10, 5 + 4) = 9 \). Next min is \( V \) (7). **6. Visit \( V \) (dist = 7) and then \( Q \) (dist = 8):** - Relax \( V \rightarrow Q \): \( d(Q) = \min(9, 7 + 1) = 8 \). Finally visit \( Q \). Thus, the visited order is **P R T S U V Q**. **Answer: P R T S U V Q.** A: **Incorrect:** After visiting `U` (dist 5), `d(V) = 7` and `d(Q) = 9`, so `V` is visited before `Q`. B: **Incorrect:** At step 4, `d(U) = 5` is smaller than `d(Q) = 10`, so `U` and `V` are visited before `Q`. C: **Incorrect:** When `S` and `U` are tied at distance 5, alphabetical order selects `S` before `U`. D: **Correct:** Tracing shortest path distances with alphabetical tie-breaking visits vertices in the order `P R T S U V Q`.

In a rooted binary tree where the height of an empty tree is \( 0 \), a tree with a single root node has height \( H = 1 \). **1. Evaluating Statement (I): \( H - 1 \le L \le 2^{H-1} \):** - What is the **minimum** number of leaf nodes \( L \) in a binary tree of height \( H \)? - Consider a skewed binary tree (a simple chain of \( H \) nodes where each internal node has only 1 child). Regardless of how large \( H \) is (e.g., \( H = 5 \)), such a tree has only **1 leaf node** (\( L = 1 \))! - For \( H = 5 \), \( H - 1 = 4 \not\le 1 \). Therefore, \( H - 1 \le L \) is **false** (the true lower bound is \( 1 \le L \le 2^{H-1} \)). **2. Evaluating Statement (II): \( H \le N \le 2^H - 1 \):** - A tree of height \( H \) must have at least 1 node at each of the \( H \) levels, so the minimum total number of nodes is \( N_{\min} = H \) (a skewed chain). - At most, level \( i \) (for \( i = 1, \dots, H \)) can have \( 2^{i-1} \) nodes, giving a maximum of \( N_{\max} = \sum_{i=1}^H 2^{i-1} = 2^H - 1 \) nodes (a perfect binary tree). - Therefore, \( H \le N \le 2^H - 1 \) is **always true**. **Answer: Only statement II is true.** A: **Incorrect:** Statement I is false because a skewed binary tree of height `H >= 3` has only `L = 1` leaf node, violating `H - 1 <= L`. B: **Correct:** Statement I fails for skewed trees (`L = 1 < H - 1` when `H >= 3`), whereas Statement II (`H <= N <= 2^H - 1`) holds for all binary trees. C: **Incorrect:** Statement I is not always true. D: **Incorrect:** Statement II is always true.

Let us find the minimum and maximum number of nodes in an **AVL tree of height \( H = 9 \)** (where an empty tree has height \( 0 \), so a single node has height \( 1 \)): **1. Minimum Number of Nodes \( N(H) \):** In an AVL tree, the minimum number of nodes of height \( H \) satisfies the recurrence: \[ N(0) = 0, \quad N(1) = 1, \quad N(H) = 1 + N(H-1) + N(H-2) \] Let us compute \( N(H) \) step by step up to \( H = 9 \): - \( 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 \) - \( N(8) = 1 + 33 + 20 = 54 \) - \( N(9) = 1 + 54 + 33 = 88 \) **2. Maximum Number of Nodes:** The maximum occurs when the AVL tree is a complete/perfect binary tree of height \( H = 9 \): \[ N_{\max}(9) = 2^9 - 1 = 512 - 1 = 511 \] **Answer: Minimum: 88, Maximum: 511.** A: **Incorrect:** `255` and `1023` are `2^8 - 1` and `2^10 - 1`, which do not use the AVL minimum node recurrence. B: **Incorrect:** A binary tree with 9 nodes and height 9 is completely skewed and violates the AVL balance property. C: **Correct:** Using `N(H) = 1 + N(H-1) + N(H-2)` with `N(0)=0, N(1)=1` gives `N(9) = 88`, and the maximum is `2^9 - 1 = 511`. D: **Incorrect:** The minimum number of nodes in an AVL tree of height 9 is 88, not 256.

To **minimize the maximum lateness** on a single machine, Jackson's **Earliest Deadline First (EDF)** greedy algorithm is optimal: we schedule the activities in increasing order of their deadlines \( D_i \). **1. Sort Activities by Deadline \( D_i \):** - \( A_6 \): \( T_6 = 2, D_6 = 2 \) - \( A_2 \): \( T_2 = 2, D_2 = 4 \) - \( A_4 \): \( T_4 = 4, D_4 = 7 \) - \( A_3 \): \( T_3 = 1, D_3 = 9 \) - \( A_7 \): \( T_7 = 5, D_7 = 12 \) - \( A_1 \): \( T_1 = 4, D_1 = 14 \) - \( A_5 \): \( T_5 = 3, D_5 = 19 \) **2. Compute Completion Time \( C_i \) and Lateness \( L_i = \max(0, C_i - D_i) \) for Each Activity:** - **\( A_6 \)**: finishes at \( C_6 = 0 + 2 = 2 \). Lateness \( = 2 - 2 = 0 \). - **\( A_2 \)**: finishes at \( C_2 = 2 + 2 = 4 \). Lateness \( = 4 - 4 = 0 \). - **\( A_4 \)**: finishes at \( C_4 = 4 + 4 = 8 \). Lateness \( = 8 - 7 = 1 \). - **\( A_3 \)**: finishes at \( C_3 = 8 + 1 = 9 \). Lateness \( = 9 - 9 = 0 \). - **\( A_7 \)**: finishes at \( C_7 = 9 + 5 = 14 \). Lateness \( = 14 - 12 = 2 \). - **\( A_1 \)**: finishes at \( C_1 = 14 + 4 = 18 \). Lateness \( = 18 - 14 = 4 \). - **\( A_5 \)**: finishes at \( C_5 = 18 + 3 = 21 \). Lateness \( = 21 - 19 = 2 \). **3. Maximum Lateness of the Optimal Schedule:** \[ L_{\max} = \max(0, 0, 1, 0, 2, 4, 2) = 4 \] **Answer: 4.** A: **Incorrect:** Even for the subset `{A6, A2, A4, A3, A7, A1}`, total duration is `2+2+4+1+5+4 = 18` while all their deadlines are `<= 14`, so the last of them must finish at `>= 18`, giving lateness at least `18 - 14 = 4`. B: **Incorrect:** Since 6 activities with deadlines `<= 14` have total duration `18`, at least one of them finishes at time `>= 18`, incurring lateness at least `18 - 14 = 4`. C: **Correct:** Scheduling by Earliest Deadline First (EDF) yields completion time 18 for `A1` (deadline 14), giving the minimum possible maximum lateness of `18 - 14 = 4`. D: **Incorrect:** EDF achieves a smaller maximum lateness of 4.

Let us compare the selection algorithms for finding the \( k^{\text{th}} \) smallest element in an unsorted array of size \( n \): **1. QuickSelect (Hoare's Selection Algorithm):** - QuickSelect partitions the array around a pivot (just like QuickSort) and recurses on only the side containing index \( k \). - **Average-case running time:** \( O(n) \). - **Worst-case running time:** If the chosen pivot is consistently the minimum or maximum element at every step, the partition size only shrinks by 1 each time, leading to the recurrence \( T(n) = T(n-1) + O(n) = O(n^2) \). **2. Fast Select (Median-of-Medians Algorithm):** - Guarantees a good pivot in every step, achieving **worst-case** running time \( O(n) \) (not \( O(n \log n) \)). **3. Max-Heap of Size \( k \):** - Building a max-heap of the first \( k \) elements takes \( O(k) \), and processing the remaining \( n - k \) elements takes \( O((n - k) \log k) \), which is \( O(n \log k) \) in the worst case (not \( O(k) \)). **Answer: Using the Quick select strategy the worst case running time will be O(n^2) (Option C).** A: **Incorrect:** The Fast select (Median-of-Medians) algorithm has a worst-case running time of `O(n)`, not `O(n log n)`. B: **Incorrect:** Using a max-heap of size `k` requires inspecting all `n` elements and takes `O(k + (n - k) log k)` time in the worst case, not `O(k)`. C: **Correct:** QuickSelect has an average-case time of `O(n)` but degrades to `O(n^2)` in the worst case when poor pivots are chosen repeatedly. D: **Incorrect:** `O(n)` is the average-case complexity of QuickSelect, whereas its worst-case complexity is `O(n^2)`.

Let us set up and solve the recurrence relation for Algorithm A using the **Master Theorem**: **1. Formulate the Recurrence Relation:** - Algorithm A divides a problem of size \( n \) into \( a = 5 \) subproblems, each of size \( n / b = n / 2 \) (so \( b = 2 \)). - Combining the solutions takes \( f(n) = O(n) \) time. - Thus, the recurrence is: \[ T(n) = 5T\left(\frac{n}{2}\right) + O(n) \] **2. Apply the Master Theorem:** - Compute the critical exponent \( c_{\text{crit}} = \log_b a = \log_2 5 \approx 2.322 \). - Compare \( n^{\log_2 5} \) with \( f(n) = O(n^1) \): since \( 1 < \log_2 5 \), we are in **Case 1** of the Master Theorem (the work at the leaves dominates). - Therefore: \[ T(n) = \Theta\left(n^{\log_2 5}\right) = O\left(n^{\log_2 5}\right) \] **Answer: O(n^{\log_2 5}).** A: **Incorrect:** `O(n log n)` occurs when `a = b = 2`, i.e., `T(n) = 2T(n/2) + O(n)`. B: **Incorrect:** `O(n^2)` occurs when `a = 4, b = 2`, i.e., `T(n) = 4T(n/2) + O(n)`. C: **Correct:** By Case 1 of the Master Theorem with `a = 5, b = 2`, and `f(n) = O(n)`, the time complexity is `O(n^{\log_2 5})`. D: **Incorrect:** `O(n^{\log_2 3})` corresponds to `a = 3` subproblems (such as Karatsuba multiplication), not `a = 5`.

Let us analyze the recursive function `find_min(L, low, high)` on a list of size \( n \): **1. Non-Recursive Work per Call:** - Checking `if low == high:` takes \( O(1) \). - Computing `mid = (low + high) // 2` takes \( O(1) \). - Computing `return min(min1, min2)` compares two numbers in \( O(1) \) time. **2. Recursive Calls:** - `min1 = find_min(L, low, mid)` solves a subproblem of size \( n/2 \). - `min2 = find_min(L, mid + 1, high)` solves the second subproblem of size \( n/2 \). - Together, there are **2 recursive calls**, each on half the list. **3. Recurrence Relation:** \[ T(n) = 2T(n/2) + 1 \] **Answer: T(n) = 2T(n/2) + 1.** A: **Incorrect:** The function makes two recursive calls (`find_min(L, low, mid)` and `find_min(L, mid + 1, high)`), and the combine step `min(min1, min2)` takes `O(1)` time, not `n`. B: **Correct:** The function makes 2 recursive calls of size `n/2` and performs `O(1)` constant work (`mid` calculation and `min` of two numbers). C: **Incorrect:** Comparing two numbers `min(min1, min2)` takes constant time `1`, not linear time `n`. D: **Incorrect:** `T(n) = T(n/2) + 1` is the recurrence for binary search (which makes only 1 recursive call), whereas `find_min` makes 2 recursive calls.

The minimum number of conference rooms required to schedule all meetings is equal to the **maximum number of overlapping meetings at any point in time** (considering that if a meeting ends at time \( t \), another meeting can start at time \( t \) in the same room, so intervals are half-open \( [\text{start}, \text{end}) \)). **1. List the Meeting Intervals \( [s_i, e_i) \):** - Meeting 1: \( [1, 4) \) - Meeting 2: \( [1, 2) \) - Meeting 3: \( [5, 8) \) - Meeting 4: \( [7, 10) \) - Meeting 5: \( [6, 8) \) - Meeting 6: \( [11, 16) \) - Meeting 7: \( [15, 20) \) - Meeting 8: \( [14, 17) \) **2. Check Maximum Overlap Across Time Windows:** - **During \( [1, 4) \)**: Meetings 1 \( [1, 4) \) and 2 \( [1, 2) \) overlap at \( t = 1 \) \( \rightarrow \mathbf{2} \) rooms. - **During \( [5, 10) \)**: - At \( t = 5 \): Meeting 3 \( [5, 8) \) starts (1 active). - At \( t = 6 \): Meeting 5 \( [6, 8) \) starts (Meetings 3, 5 active \( \rightarrow 2 \)). - At \( t = 7 \): Meeting 4 \( [7, 10) \) starts while Meetings 3 and 5 are still running until \( t = 8 \)! Thus during \( [7, 8) \), Meetings 3, 4, and 5 are all active simultaneously \( \rightarrow \mathbf{3} \) rooms. - **During \( [11, 20) \)**: - At \( t = 15 \): Meeting 6 \( [11, 16) \), Meeting 8 \( [14, 17) \), and Meeting 7 \( [15, 20) \) are all active simultaneously during \( [15, 16) \) \( \rightarrow \mathbf{3} \) rooms. Since the maximum number of simultaneously active meetings at any time is **3**, the minimum number of conference rooms required is **3**. **Answer: 3.** A: **Correct:** The maximum number of simultaneously overlapping meetings is 3 (for example, Meetings 3, 4, and 5 during `[7, 8)`, and Meetings 6, 7, and 8 during `[15, 16)`). B: **Incorrect:** At most 3 meetings overlap at any single time instant, so 4 rooms are not needed. C: **Incorrect:** 5 rooms is more than the maximum overlap of 3. D: **Incorrect:** 6 rooms is more than the maximum overlap of 3.

Let us trace the recursive function `traversal(t)`: ```python def traversal(t): if t != None: traversal(t.right) traversal(t.left) print(t.value, end = ' ') ``` Notice that for every node `t`, this function visits: **1. Right subtree** \( \rightarrow \) **2. Left subtree** \( \rightarrow \) **3. Root (`t.value`)**. **Tracing on the Given Tree (Root = 5):** - **1. Right subtree of 5 (rooted at 8):** - Right child of 8 is **9** (leaf) \( \rightarrow \) prints `9`. - Left child of 8 is **6**: - Right child of 6 is **7** (leaf) \( \rightarrow \) prints `7`. - Left child of 6 is `None`. - Prints node `6`. - Prints node `8`. *(So far: `9 7 6 8`)* - **2. Left subtree of 5 (rooted at 2):** - Right child of 2 is **4**: - Right child of 4 is `None`. - Left child of 4 is **3** (leaf) \( \rightarrow \) prints `3`. - Prints node `4`. - Left child of 2 is **1** (leaf) \( \rightarrow \) prints `1`. - Prints node `2`. *(So far: `9 7 6 8 3 4 1 2`)* - **3. Finally, print Root `5`:** Complete output: `9 7 6 8 3 4 1 2 5`. **Answer: 9 7 6 8 3 4 1 2 5.** A: **Incorrect:** `1 3 4 2 7 6 9 8 5` is standard Left-Right-Root postorder traversal, whereas the code calls `traversal(t.right)` before `traversal(t.left)`. B: **Incorrect:** `1 2 3 4 5 6 7 8 9` is Left-Root-Right inorder traversal. C: **Incorrect:** `9 8 7 6 5 4 3 2 1` is reverse inorder (Right-Root-Left) traversal. D: **Correct:** Visiting Right-Left-Root recursively prints `9 7 6 8 3 4 1 2 5`.

Let us construct the **Huffman tree** step by step from the given character frequencies: - Initial frequencies: \( E: 2, \; C: 6, \; F: 11, \; A: 13, \; B: 30, \; D: 35 \). **Step-by-Step Merging of the Two Smallest Frequencies:** **1. Merge \( E(2) \) and \( C(6) \):** - Creates internal node \( N_1 = 2 + 6 = 8 \). - Remaining frequencies: \( N_1: 8, \; F: 11, \; A: 13, \; B: 30, \; D: 35 \). **2. Merge \( N_1(8) \) and \( F(11) \):** - Creates internal node \( N_2 = 8 + 11 = 19 \). - Remaining frequencies: \( A: 13, \; N_2: 19, \; B: 30, \; D: 35 \). **3. Merge \( A(13) \) and \( N_2(19) \):** - Creates internal node \( N_3 = 13 + 19 = 32 \). - Remaining frequencies: \( B: 30, \; N_3: 32, \; D: 35 \). **4. Merge \( B(30) \) and \( N_3(32) \):** - Creates internal node \( N_4 = 30 + 32 = 62 \). - Remaining frequencies: \( D: 35, \; N_4: 62 \). **5. Merge \( D(35) \) and \( N_4(62) \):** - Creates the root node \( R = 35 + 62 = 97 \). **Code Lengths (Depth of Each Character from Root \( R \)):** - **\( D \)**: child of \( R \) \( \rightarrow \) depth **1** - **\( B \)**: child of \( N_4 \) (which is child of \( R \)) \( \rightarrow \) depth **2** - **\( A \)**: child of \( N_3 \) (depth 2) \( \rightarrow \) depth **3** - **\( F \)**: child of \( N_2 \) (depth 3) \( \rightarrow \) depth **4** - **\( C, E \)**: children of \( N_1 \) (depth 4) \( \rightarrow \) depth **5** Thus: **A - 3, B - 2, C - 5, D - 1, E - 5, F - 4**. **Answer: A - 3, B - 2, C - 5, D - 1, E - 5, F - 4.** A: **Incorrect:** `B(30)` merges with `N3(32)` at depth 2, so `B` has code length 2, not 3. B: **Incorrect:** `D(35)` merges at the very last step directly into the root, so `D` has code length 1, not 2. C: **Incorrect:** `B` has length 2 and `D` has length 1. D: **Correct:** Tracing the Huffman tree gives depths `D = 1, B = 2, A = 3, F = 4, C = 5, E = 5`.

Let us evaluate each statement about the **Floyd-Warshall all-pairs shortest path algorithm**: - **Option A**: Initially, the diagonal entries \( SP[i][i] = 0 \). If the graph contains a negative-weight cycle reachable from vertex \( i \) and returning to \( i \), the shortest path from \( i \) to itself becomes negative (\( SP[i][i] < 0 \)). Thus, a negative diagonal entry detects a negative-weight cycle. (**True**) - **Option B**: Floyd-Warshall uses three nested loops over \( k, i, j \in \{1, \dots, V\} \), so its time complexity is \( O(V^3) \), **not** \( O(V^2) \). (**False**) - **Option C**: Floyd-Warshall handles negative edge weights properly as long as there are no negative-weight cycles. (**True**) - **Option D**: The recurrence in Option D is written as \( \min[SP^{k-1}[i, j] + SP^{k-1}[i, k], \; SP^{k-1}[k, j]] \), which is wrong! The correct recurrence is \( SP^k[i, j] = \min\left(SP^{k-1}[i, j], \; SP^{k-1}[i, k] + SP^{k-1}[k, j]\right) \). (**False**) **Answer: Options A and C.** A: **Correct:** A negative diagonal entry `SP[i][i] < 0` in the final distance matrix indicates a negative-weight cycle involving vertex `i`. B: **Incorrect:** The time complexity of Floyd-Warshall is `O(V^3)`, not `O(V^2)`. C: **Correct:** Floyd-Warshall correctly computes all-pairs shortest paths in graphs with negative edge weights, provided there are no negative-weight cycles. D: **Incorrect:** Misplaces the `+` and `,` in the recurrence; the correct formula is `min(SP^{k-1}[i, j], SP^{k-1}[i, k] + SP^{k-1}[k, j])`.

In a 0-indexed **min-heap** array \( A \), every parent at index \( i \) must be less than or equal to its left child at \( 2i + 1 \) and its right child at \( 2i + 2 \): - **Option A (`[1, 3, 6, 5, 4, 9, 8, 7]`)**: - `i = 0 (1)`: children `3, 6` (`1 <= 3, 6`) - `i = 1 (3)`: children `5, 4` (`3 <= 5, 4`) - `i = 2 (6)`: children `9, 8` (`6 <= 9, 8`) - `i = 3 (5)`: left child `7` (`5 <= 7`) All parent-child pairs satisfy the min-heap property! (**Valid**) - **Option B (`[2, 4, 3, 8, 10, 15, 9, 6]`)**: - At `i = 3`, parent is `A[3] = 8`, and its left child is `A[7] = 6`. Since `8 > 6`, this violates the min-heap property! (**Invalid**) - **Option C (`[7, 10, 15, 20, 30, 16, 12, 22]`)**: - At `i = 2`, parent is `A[2] = 15`, and its right child is `A[6] = 12`. Since `15 > 12`, this violates the min-heap property! (**Invalid**) - **Option D (`[3, 6, 8, 10, 15, 9, 11, 20]`)**: - `i = 0 (3)`: children `6, 8` (`3 <= 6, 8`) - `i = 1 (6)`: children `10, 15` (`6 <= 10, 15`) - `i = 2 (8)`: children `9, 11` (`8 <= 9, 11`) - `i = 3 (10)`: left child `20` (`10 <= 20`) All parent-child pairs satisfy the min-heap property! (**Valid**) **Answer: [1, 3, 6, 5, 4, 9, 8, 7] and [3, 6, 8, 10, 15, 9, 11, 20] (Options A and D).** A: **Correct:** Every parent `A[i]` is less than or equal to its children `A[2i+1]` and `A[2i+2]`. B: **Incorrect:** `A[3] = 8` is greater than its left child `A[7] = 6`, violating the min-heap property. C: **Incorrect:** `A[2] = 15` is greater than its right child `A[6] = 12`, violating the min-heap property. D: **Correct:** Every parent `A[i]` is less than or equal to its children `A[2i+1]` and `A[2i+2]`.

In a binary heap implemented using a **0-indexed array**, for any node at index \( i \): - The index of its **left child** is \( 2i + 1 \). - The index of its **right child** is \( 2i + 2 \). **Calculation for \( i = 35 \):** \[ \text{Right Child Index} = 2(35) + 2 = 70 + 2 = 72 \] (Since the heap has 100 elements, valid indices are \( 0 \) to \( 99 \), so index \( 72 \) is within bounds.) **Answer: 72.**

An **inversion** in the list \( L = [9, 1, 12, 4, 7, 13, 5] \) is a pair of indices \( (i, j) \) with \( i < j \) such that \( L[i] > L[j] \). **Let us count the inversions for each element \( L[i] \) from left to right:** **1. For \( L[0] = 9 \):** - Elements to its right smaller than 9: \( 1, 4, 7, 5 \) \( \rightarrow \mathbf{4} \) inversions: \( (9, 1), (9, 4), (9, 7), (9, 5) \). **2. For \( L[1] = 1 \):** - Elements to its right smaller than 1: none \( \rightarrow \mathbf{0} \) inversions. **3. For \( L[2] = 12 \):** - Elements to its right smaller than 12: \( 4, 7, 5 \) \( \rightarrow \mathbf{3} \) inversions: \( (12, 4), (12, 7), (12, 5) \). **4. For \( L[3] = 4 \):** - Elements to its right smaller than 4: none \( \rightarrow \mathbf{0} \) inversions. **5. For \( L[4] = 7 \):** - Elements to its right smaller than 7: \( 5 \) \( \rightarrow \mathbf{1} \) inversion: \( (7, 5) \). **6. For \( L[5] = 13 \):** - Elements to its right smaller than 13: \( 5 \) \( \rightarrow \mathbf{1} \) inversion: \( (13, 5) \). **Total Number of Inversions:** \[ 4 + 0 + 3 + 0 + 1 + 1 = 9 \] **Answer: 9.**

Let us list all the edges and their weights in the given undirected graph \( G \): - \( (A, C) = 1 \) - \( (A, D) = 3 \) - \( (C, D) = 4 \) - \( (C, B) = 4 \) - \( (A, B) = 4 \) - \( (D, E) = 5 \) - \( (A, E) = X \) **1. Cycle Property for Exclusion from Every MST:** By the **Cycle Property** of Minimum Spanning Trees, an edge \( e = (A, E) \) is excluded from **every** MST if and only if \( (A, E) \) is the **strictly heaviest** edge on some cycle containing \( A \) and \( E \). **2. Finding the Path Between \( A \) and \( E \) Without \( (A, E) \):** - In \( G \setminus \{(A, E)\} \), vertex \( E \) is connected to the rest of the graph only via edge \( (D, E) \) of weight \( 5 \). - The minimax path between \( A \) and \( D \) is the direct edge \( (A, D) \) of weight \( 3 \) (completing the cycle \( A - D - E - A \) with other edge weights \( 3 \) and \( 5 \)). - The maximum weight among the other edges in this cycle is \( \max(3, 5) = 5 \). **3. Smallest Integer Value of \( X \):** For \( (A, E) \) to be excluded from *every* MST, its weight \( X \) must be strictly greater than \( 5 \) (since if \( X = 5 \), there is a tie between \( (A, E) \) and \( (D, E) \), so one MST would include \( (A, E) \)). Therefore, the smallest integer value of \( X \) is: \[ X = 5 + 1 = 6 \] **Answer: 6.**