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

**1. Preserve which student takes which course:** The original key is \((Student\_ID,Course\_ID)\). A correct decomposition must retain this pairing as well as removing the nonprime attributes that depend on only one key component. **2. Separate the partial dependencies:** Students(Student_ID,Student_Name) has a singleton key. Departments(Course_ID,Course_Name,Dept_Name,Dept_Head) also has a singleton key Course_ID and is therefore in 2NF, although Dept_Name → Dept_Head still prevents its 3NF. **3. Retain the association:** Enroll(Course_ID,Student_ID) contains the original pair and has no nonprime attributes, so it is in 2NF. Joining it with Students on Student_ID and Departments on Course_ID is lossless because those joining attributes determine the corresponding descriptive rows. **4. Select the complete decomposition:** Only the fourth option retains all attributes, removes the partial dependencies from every component and keeps the student-course association. **Answer: D — Students, Departments keyed by Course_ID, and Enroll(Course_ID, Student_ID).** **Convention note:** The shared Enrollment schema and FDs are supplied in the DBMS passage in this bundle. The Departments relation is in 2NF, which is all the question requires; it need not be in 3NF. A: **Incorrect:** The student-course association is lost; joining these two disjoint schemas produces all combinations. B: **Incorrect:** Students still contains the composite key Student_ID,Course_ID and the partial dependency Student_ID → Student_Name. C: **Incorrect:** Courses still has Course_ID → Course_Name as a partial dependency, and no relation retains Course_ID → Dept_Name. D: **Correct:** All three components are in 2NF, and Enroll preserves the original student-course pairs.

**1. Initialize Dijkstra from P:** Set \(d(P)=0\). Relaxing its outgoing edges gives \(d(Q)=1,d(S)=6,d(T)=7\), while R and U remain infinite. P is the first visited vertex. **2. Settle the next two vertices:** Q is second with distance 1. Its edges improve R to 2 and S to 5. R is then third with distance 2; relaxing R → S (weight 2) improves S to 4, and R → U (weight 1) gives U distance 3. **3. Settle fourth and fifth:** U is fourth at distance 3. It has no outgoing edge that lowers S, so S, with distance 4, is fifth. S can subsequently improve T to 7, and T is last. **4. Record the visited order:** The order is P,Q,R,U,S,T, with settled distances 0,1,2,3,4,7. The question counts P as the first visited node, so the requested fifth node is S. **Answer: C — S.** A: **Incorrect:** U is visited fourth, at distance 3. B: **Incorrect:** R is visited third, at distance 2. C: **Correct:** S is visited fifth, at distance 4. D: **Incorrect:** T is visited sixth, at distance 7.

**1. Preserve the cost of each original path:** Replacing an edge of positive integer weight w by a chain of w unit edges makes its number of unit edges equal to its old weight. Distinct fresh intermediate vertices prevent unintended shortcuts between edge chains. **2. Apply BFS correctness:** Every original weighted path corresponds to a unit-edge path with the same total cost, and paths between original vertices in the transformed graph map back to original paths. BFS minimizes unit-edge count, so its distances to original vertices solve the original shortest-path problem. **3. Compare running times:** Let \(W=\sum_e w_e\). The transformed graph has \(V+W-E\) vertices and W edges, so construction plus BFS takes \(O(V+W)\). Large binary-encoded weights can make W enormous. Dijkstra on the original graph avoids explicitly expanding each unit of weight, so the claimed equal efficiency is false. **Answer: A — I is true, II is false.** **Convention note:** The construction requires positive integer weights, as indicated by paths containing w edges. For an arbitrary positive real weight, that literal replacement is not defined. A weight-w chain uses w−1 fresh intermediate vertices; the example correctly shows two for w=3. A: **Correct:** I is true by path-cost preservation; II fails because expansion depends on the sum of weights. B: **Incorrect:** The correctness claim is valid, and the efficiency claim is not. C: **Incorrect:** The first statement is true for positive integer weights. D: **Incorrect:** The expansion can be far more expensive than Dijkstra on the original graph.

**1. Sort the edges for Kruskal’s algorithm:** In increasing order the graph has bc=1, ef=1, ab=2, df=2, ac=3, de=3, be=4, bd=5 and ce=7. Always choose the cheapest edge that joins different components. **2. Add edges without creating a cycle:** Select bc and ef, then ab and df. The components are now \(\{a,b,c\}\) and \(\{d,e,f\}\). Reject ac and de because each would create a cycle inside one component. **3. Connect the two components:** Edge be of weight 4 is the cheapest remaining connection. The selected five edges span all six vertices with no cycle, and their weight is \(1+1+2+2+4=10\). **Answer: 10.**

**1. Separate an MST from pairwise shortest paths:** A minimum spanning tree minimizes the sum of its selected edges across the entire graph. A shortest path minimizes travel cost for a particular pair; the lightest edge across a cut need not serve every cross-cut pair. **2. Disprove statement I:** Let \(X=\{a,c\},Y=\{b\}\) and use edges ab=1, cb=2, ac=100. The unique lightest crossing edge is ab. But the shortest path from c to b is the direct edge of cost 2, which does not use ab. **3. Prove statement II by exchange:** Suppose an MST omits the unique lightest crossing edge e. Adding e creates a cycle, which contains another crossing edge f. Distinct weights and minimality across the cut imply \(w(f)>w(e)\). Replacing f by e yields a cheaper spanning tree, a contradiction. Thus e must belong to the MST. **Answer: B — I is false, II is true.** A: **Incorrect:** I fails by the three-vertex counterexample, while II follows from the cut property. B: **Correct:** I is false and II is true. C: **Incorrect:** The cut property makes II true. D: **Incorrect:** The cut property does not imply the pairwise shortest-path claim I.

**1. Use the height of an array heap:** A binary heap is a complete binary tree of height \(O(\log n)\). Restoring order along one ancestor or descendant path therefore takes logarithmic time. **2. Analyze local changes:** Insertion appends a value and sifts it upward. Deleting the root replaces it by the last value and sifts downward. Updating a known array index sifts upward if its value increases or downward if it decreases; no search for the index is needed. **3. Analyze merging separately:** Two size-n array heaps contain 2n values in total. Concatenating and rebuilding by bottom-up heapification takes \(O(n)\), and a standard materialized merged array cannot in general be produced in \(O(\log n)\). **Answer: A, B, D — insertion, deleting the maximum, and updating a known index.** **Convention note:** The standard heap analysis assumes capacity is available for insertion, or uses amortized dynamic-array resizing. A single insertion that triggers an array reallocation can additionally cost O(n). A: **Correct:** At most one rootward path is traversed after appending. B: **Correct:** Replacing the root and sifting down takes at most the heap height. C: **Incorrect:** Ordinary array-heap merging takes linear time with bottom-up heapification. D: **Correct:** A known index allows immediate access followed by one sift-up or sift-down path.

**1. Locate the minimum:** In a max-heap with distinct elements, every internal node exceeds each child. An internal node therefore cannot be the minimum, which must be a leaf. **2. Distinguish leaves from the deepest level:** A complete tree may have leaves on its next-to-last level as well. The valid max-heap array [100,90,1,80] has minimum 1 as a leaf above the deepest node 80, disproving the last-level restriction. **3. Locate the second largest:** A nonroot node below a root child is smaller than that ancestor. Thus the largest value after the root must be one of the root’s children. **4. Bound minimum-search time:** The leaves are not ordered relative to each other. There are \(\lceil n/2\rceil\) of them, so finding their minimum takes \(\Theta(n)\) comparisons in the worst case, not logarithmic time. **Answer: A, C — the minimum is a leaf; the second maximum is a child of the root.** **Convention note:** The second-largest statement presumes n≥2; for a one-element heap there is no second-largest element. A: **Correct:** Any internal node has a smaller child, so the minimum must be a leaf. B: **Incorrect:** A leaf need not be on the deepest level; [100,90,1,80] is a counterexample. C: **Correct:** Every deeper node is smaller than its root-child ancestor. D: **Incorrect:** The unordered leaves require a worst-case linear scan.

**1. Follow the search path:** At each visited BST node, compare the target with the key and choose at most one child. No level requires scanning the other subtree. **2. Use the stated height:** Height h counts nodes on the longest root-to-leaf path. A target at the deepest node, or an unsuccessful search beyond it, may require h node inspections. Each inspection takes constant time, so the tight worst-case bound is \(\Theta(h)\). **3. Avoid an unsupported balance assumption:** The tree need not be balanced. It can be a chain with h=n, so logarithmic behavior in the number of nodes is not guaranteed. **Answer: B — \(O(h)\).** **Convention note:** As usual in complexity MCQs, the intended answer is the tight bound. O(h log h) and O(2^h) are also loose asymptotic upper bounds, but do not describe the tight running time. A: **Incorrect:** A deepest search may inspect h nodes, exceeding a logarithmic-in-h bound. B: **Correct:** This is the tight worst-case bound, conventionally written O(h) in the options. C: **Incorrect:** This is a loose upper bound, not the tight complexity of the search. D: **Incorrect:** This is a much looser upper bound; search follows one path rather than exploring exponentially many nodes.

**1. Find the minimum node count:** A longest root-to-leaf path contains h nodes by definition. Therefore \(n\ge h\), attained by a chain. **2. Find the maximum node count:** Level j, counting the root as level 0, has at most \(2^j\) nodes. Summing over h levels gives \[n\le1+2+\cdots+2^{h-1}=2^h-1.\] **3. Test the alternatives:** At height 3, a perfect tree has 7 nodes, exceeding \(2^{h-1}=4\). A chain has n=h, disproving n≥h+1. A perfect height-4 tree has 15 nodes, exceeding \(h\log_2h=8\); h log h is not a universal upper bound. **Answer: B, E — \(n\ge h\) and \(n\le2^h-1\).** A: **Incorrect:** A perfect height-3 tree has 7 nodes, exceeding 4. B: **Correct:** The longest path itself contains h distinct nodes. C: **Incorrect:** A chain attains n=h, so the extra 1 is unjustified. D: **Incorrect:** Perfect trees have exponentially many nodes in h, exceeding this bound for sufficiently large h. E: **Correct:** This is the geometric-series upper bound for h levels.

**1. Build the sparsest AVL tree:** Let N(h) be its minimum node count, where a leaf has height 1 and an empty tree has height 0. To achieve height h with as few nodes as possible, the two child heights must be h−1 and h−2; a larger difference would violate AVL balance. **2. Set up the recurrence:** \[N(0)=0,\quad N(1)=1,\quad N(h)=1+N(h-1)+N(h-2).\] The extra 1 is the root. **3. Calculate up to height 6:** \(N(2)=2,N(3)=4,N(4)=7,N(5)=12\). Hence \(N(6)=1+12+7=20\). **Answer: 20.**

**1. Insert 30,20,10:** Inserting 10 creates a left-left imbalance at 30. A right rotation makes 20 the root, with children 10 and 30. **2. Insert 28 and then 25:** Node 28 becomes the left child of 30. Inserting 25 as the left child of 28 creates a left-left imbalance at 30, so rotate right there. The overall root remains 20, and its right subtree is rooted at 28 with children 25 and 30. **3. Insert 40:** It becomes the right child of 30. Now the subtree at 20 has left height 1 and right height 3, a right-right imbalance. Rotate left at 20, promoting 28 to the root. **4. Verify the final tree:** Root 28 has left child 20 with children 10,25 and right child 30 with right child 40. Every node’s child heights differ by at most 1, and the inorder traversal remains 10,20,25,28,30,40. **Answer: D — 28.** A: **Incorrect:** 25 is the right child of 20 after the final rotation. B: **Incorrect:** 20 is the root before the final insertion, but the last rotation moves it below 28. C: **Incorrect:** 30 becomes the right child of 28, not the final root. D: **Correct:** The final left rotation at 20 promotes 28 to the root.

**1. Repeatedly merge the two smallest weights:** Start with C=.06,A=.12,E=.14,D=.16,F=.24,B=.28. Merge C+A=.18, then E+D=.30. **2. Complete the Huffman merges:** The remaining weights are .18,.24,.28,.30. Merge .18+.24=.42, then .28+.30=.58, and finally .42+.58=1. **3. Count the depth of each character:** C and A pass through the .18 and .42 nodes before the root, so they use 3 bits. D and E pass through .30 and .58 and also use 3 bits. F and B are at depth 2 and use 2 bits. **4. Identify the maximum:** The longest codeword has 3 bits. For example, one valid assignment is C=000,A=001,F=01,B=10,E=110,D=111; swapping left/right labels changes codes but not lengths. **Answer: 3.**

**1. Recognize interval scheduling:** Treat each interview as the fixed interval from its start_time to end_time. The objective is the number of nonoverlapping intervals, and a new interview is compatible when its start is at least the previous selected end. **2. Apply the greedy rule:** Among currently compatible interviews, choose the one with the earliest end_time, then repeat. An early finish leaves the greatest remaining time for future interviews. **3. Justify the exchange argument:** In any optimal schedule, replace its first interview by a globally earliest-finishing one. The replacement ends no later and therefore does not conflict with any later interview in that schedule. Repeating the argument proves the greedy schedule has maximum cardinality. **Answer: D — choose the compatible interview with the earliest end_time.** **Convention note:** This is the intended fixed-interval activity-selection model. If start/end instead describe flexible availability windows and interviews have separate durations, those durations must be supplied and the problem changes. A: **Incorrect:** An early-starting but long interview can block many short later interviews. B: **Incorrect:** A shortest interval can overlap the middle of two mutually compatible longer intervals. C: **Incorrect:** Counting conflicts does not give the exchange property needed for an optimal schedule. D: **Correct:** Earliest finish leaves the largest feasible suffix and is optimal for unweighted interval scheduling.

**1. Bound the number of inversions:** Each pair of distinct positions contributes at most one inversion, so a list of length n has at most \(\binom n2=n(n-1)/2\), attained in descending order. **2. Exclude smaller lengths:** For n=8 the maximum is \(8\cdot7/2=28<30\). For n=9 the maximum is 36, so 9 is the first possible length. **3. Show 30 inversions are attainable:** The list [9,8,7,6,5,1,2,3,4] has 10 inversions among its first five descending entries and 20 between those five and the final four; the final four are increasing. Its total is exactly 30, proving that the minimum possible n is 9. **Answer: 9.**

**1. Analyze ordinary Quickselect’s worst pivot:** If each partition leaves a recursive subproblem of size n−1, \(T(n)=T(n-1)+\Theta(n)\). Summing the partition costs gives \(\Theta(n^2)\), rather than the claimed worst-case linear time. **2. Distinguish average and guaranteed time:** Random-pivot Quickselect has expected linear time, but that does not remove its quadratic worst case. Median-of-medians chooses a pivot with a guaranteed constant-fraction split, yielding \(T(n)\le T(\lceil n/5\rceil)+T(7n/10+O(1))+O(n)=O(n)\). **3. Select the false statement:** The question asks for the incorrect option. The ordinary Quickselect worst-case claim in A is false; both median-of-medians linear-time claims are valid. **Answer: A — the ordinary Quickselect worst-case O(n) claim is incorrect.** **Convention note:** Some texts classify Quickselect more narrowly as decrease-and-conquer because only one partition is recursively solved. Under that taxonomy option C would also be called incorrect. The intended exam terminology treats its partition-based strategy under the broader divide-and-conquer umbrella. A: **Correct:** Select this false statement: ordinary Quickselect can take quadratic worst-case time. B: **Incorrect:** This is a true statement: deterministic median-of-medians selection is worst-case linear. C: **Incorrect:** Under the broad partition-based divide-and-conquer terminology used here, this is accepted; Quickselect recurses into only the relevant partition. D: **Incorrect:** This is true: using median-of-medians pivots gives worst-case linear selection.

**1. Count recursive calls:** For more than one element, the function computes the minimum of both halves. Thus it makes two recursive calls of approximately n/2 elements, rather than recursing into only one half. **2. Count work outside recursion:** Calculating mid and comparing min1 with min2 take constant time. There is no scan over all n elements at the current call. **3. Write and solve the recurrence:** \[T(n)=2T(n/2)+1,\quad T(1)=1.\] For powers of two this gives \(T(n)=2n-1=\Theta(n)\), with n leaf calls and n−1 combining calls. For odd sizes, use floor and ceiling half sizes without changing the asymptotic result. **Answer: B — \(T(n)=2T(n/2)+1,\ T(1)=1\).** A: **Incorrect:** This omits one recursive call and incorrectly adds linear combining work. B: **Correct:** Two half-size calls plus constant overhead match the function. C: **Incorrect:** Both calls are present, but combining two minima is constant, not linear. D: **Incorrect:** This omits the call processing the second half.

**1. Analyze the first recurrence:** For \(T_1(n)=9T_1(n/3)+O(n)\), the critical exponent is \(\log_3 9=2\). The recursion has \(n^2\) leaves, while the linear work at internal nodes totals at most the same order. Thus \(T_1(n)=\Theta(n^2)\) with the stated unit base cost. **2. Analyze the second recurrence:** For \(T_2(n)=3T_2(n/3)+O(n)\), the critical exponent is \(\log_3 3=1\). Each level contributes at most O(n), and there are \(\log_3n\) levels, giving \(T_2(n)=O(n\log n)\). **3. Match the pair:** The requested upper bounds are \(O(n^2)\) and \(O(n\log n)\), respectively. If the second recurrence’s nonrecursive work is actually \(\Theta(n)\), its bound is tight: \(\Theta(n\log n)\). **Answer: C — \(T_1(n)=O(n^2),\ T_2(n)=O(n\log n)\).** **Convention note:** The source writes O(n), not Theta(n), for the additive terms. This guarantees the displayed upper bounds; a tight n log n claim for T2 additionally requires linear-order nonrecursive work. A: **Incorrect:** The first recurrence grows quadratically, not O(n log n). B: **Incorrect:** The first recurrence’s n-squared leaf count rules out this bound. C: **Correct:** These are valid bounds for both stated recurrences. D: **Incorrect:** The second recurrence can require n log n work when its added term is linear, so O(n) is not assured.