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

**1. Initialize from A:** The directed outgoing edges are A → B of weight 2 and A → D of weight 1. Start with distances A=0,B=2,D=1 and all others infinite. **2. Settle D and relax its outgoing edges:** D gives C=1+2=3, E=1+2=3, G=1+4=5 and F=1+8=9. B is next at distance 2, but B → D and B → E do not improve the current values. **3. Finish the remaining improvements:** C → F gives candidate 3+5=8, lowering F from 9. E → G gives 3+6=9, which does not improve G=5. Finally G → F lowers F to 5+1=6. **4. Report in the requested vertex order:** For A,B,C,D,E,F,G the distances are \((0,2,3,1,3,6,5)\). Example shortest paths to E and F are A→D→E and A→D→G→F. **Answer: B — (A,B,C,D,E,F,G) = (0,2,3,1,3,6,5).** A: **Incorrect:** E can be reached with cost 3 and F with cost 6, smaller than the stated 4 and 8. B: **Correct:** All seven entries match the directed shortest paths. C: **Incorrect:** The stated E,F,G entries disagree with the relaxation results. D: **Incorrect:** All entries except E match; A→D→E has cost 3, not 4.

**1. Delete the minimum:** Remove 11 and move the last element 37 to the root. Sift down by choosing the smaller child at each step: swap with 12, then with 20. The eight-element heap becomes [12,19,20,26,32,27,37,29]. **2. Insert 18:** Append it at index 8, giving parent 26 at index 3. Swap 18 with 26, then with its new parent 19 at index 1. Stop because the root 12 is smaller than 18. **3. Write the final array:** The result is [12,18,20,19,32,27,37,29,26]. Both operations follow the standard array-based binary min-heap algorithm; a heap array need not be globally sorted. **Answer: B — [12,18,20,19,32,27,37,29,26].** A: **Incorrect:** This does not match the sift-down and sift-up positions generated by the operations. B: **Correct:** This is the exact array after replacing the removed root and bubbling the inserted 18 upward. C: **Incorrect:** This is a different heap arrangement, not the result of the stated standard operations. D: **Incorrect:** This places 20 at index 1 above the smaller child 19 at index 3, violating the min-heap property.

**1. Identify Prim’s selection rule:** Maintain a growing visited set and repeatedly choose a minimum-weight edge crossing from that set to an unvisited vertex. This is statement iii and follows the MST cut property. **2. Distinguish it from Kruskal’s preprocessing:** Prim does not first sort every graph edge globally. A priority queue or key array identifies the next cheapest crossing edge. Sorting all edges is characteristic of Kruskal’s algorithm, so ii is false. **3. Account for ties:** When several MSTs exist, the starting vertex together with tie choices can lead Prim to select different minimum spanning trees of the same total weight. Thus the possibility claim i is true. **Answer: C — statements i and iii.** A: **Incorrect:** ii is false, so this pair is not correct. B: **Incorrect:** iii is true but ii is false. C: **Correct:** i and iii describe valid properties of Prim’s algorithm. D: **Incorrect:** The global edge-sorting claim ii is false.

**1. Relate internal nodes and edges:** Let I be the number of internal nodes and L=4 the leaves. Every internal node has exactly two children, so the tree has 2I child edges. **2. Use the edge count of a tree:** With N=I+L nodes, the number of edges is N−1=I+L−1. Hence \(2I=I+L-1\), giving I=L−1=3. **3. Count all nodes:** \(N=I+L=3+4=7\), equivalently \(N=2L-1\). BST key ordering does not change this structural identity. **Answer: A — 7.** A: **Correct:** A full/strict binary tree with 4 leaves has 3 internal nodes and 7 nodes total. B: **Incorrect:** A strict binary tree’s total node count is odd, so 8 cannot fit. C: **Incorrect:** 9 nodes would require 5 leaves under N=2L−1. D: **Incorrect:** 10 is even and violates the full-binary-tree counting identity.

**1. Locate the last inserted position:** Before the final insertion a nine-element heap has eight entries. The new item is appended at index 8 (zero-based) and can only move through indices 8→3→1→0 while sifting up. **2. Compare with the final heap:** Those final positions contain 36,37,46,71. Therefore any candidate last-inserted value must finish at one of these positions. Value 29 is at index 4, which is not on that path, and cannot be the final insertion. **3. Verify the other candidates can occur:** For last=36, take the first eight final entries as the predecessor heap. For last=37, replace final index 3 by 36 and remove index 8. For last=71, use predecessor [46,37,27,36,29,17,11,32]. Each predecessor is a valid max-heap and appending/sifting the stated value produces the given final array. **Answer: D — 29 could not have been inserted last.** A: **Incorrect:** 71 can rise from index 8 through 3 and 1 to the root. B: **Incorrect:** 36 can remain at the newly appended final index 8. C: **Incorrect:** 37 can rise one level from index 8 to index 3. D: **Correct:** 29 is not on the new entry’s possible ancestor path, so select it as the impossible candidate.

**1. Disprove the universal greedy claim:** Greedy decisions give an optimal result only when the problem supports the necessary greedy-choice property. With coins 1,3,4 and target 6, taking the largest possible coin gives 4+1+1, while the optimum is 3+3. Thus i is false. **2. Classify the two shortest-path algorithms:** Bellman–Ford repeatedly relaxes edges, with a dynamic-programming interpretation by allowed path-edge count. Floyd–Warshall uses the recurrence \(d_{ij}^{(k)}=\min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})\), progressively allowing intermediate vertices. They are not the greedy algorithms claimed in ii. **Answer: A — both statements are false.** A: **Correct:** Both statements are false: greedy is not universally optimal, and these are relaxation/dynamic-programming methods. B: **Incorrect:** The counterexample and algorithm classifications refute both claims. C: **Incorrect:** i is also false; greedy does not always produce an optimum. D: **Incorrect:** ii is false; neither listed method is classified as the claimed greedy approach.

**1. Insert using BST order:** The new key 1 follows 10→5→3 and becomes the left child of 3. Node 3 remains balanced, and node 5 has child heights differing by one. **2. Find the first unbalanced ancestor:** At 10, the left subtree now has height 3 and the right subtree height 1. The insertion occurred along the left-left direction, so a single right rotation at 10 restores balance. **3. Track the rotation:** Promote 5 to the root; make 10 its right child and move 5’s old right subtree rooted at 8 to become 10’s left subtree. The final root 5 has left child 3 with left child 1, and right child 10 with children 8 and 20. **Answer: B — root 5; left subtree 3→1; right child 10 with children 8 and 20.** A: **Incorrect:** This different root and arrangement do not result from the required single right rotation. B: **Correct:** This exactly matches the right rotation at 10. C: **Incorrect:** A right rotation preserves the existing 3→1 relationship; it does not make 1 the parent of 3. D: **Incorrect:** The chain 5→3→1 leaves a height imbalance and is not the required AVL result.

**1. Merge the two least frequent symbols:** Frequencies are A=50,B=20,C=2,D=10. Huffman first combines C and D into a node of weight 12. **2. Complete the merges:** Combine 12 with B=20 to get 32, then combine 32 with A=50 to get the root of weight 82. The resulting code lengths are A:1 bit, B:2 bits, C:3 bits and D:3 bits. **3. Weight each code length by its occurrence count:** \[Total=50(1)+20(2)+2(3)+10(3)=50+40+6+30=126\text{ bits}.\] Equivalently, the sum of Huffman merge weights is 12+32+82=126. **Answer: D — 126 bits.** **Convention note:** The count is the encoded message payload, excluding any additional storage needed to transmit the codebook or tree. A: **Incorrect:** This assigns 4 bits to each of the 82 characters instead of using the Huffman code lengths. B: **Incorrect:** 82 is the number of characters, not the encoded bit total. C: **Incorrect:** This does not include all weighted code lengths correctly. D: **Correct:** The weighted sum of lengths is exactly 126 bits.

**1. Solve A and B by recursion levels:** A has two size-n/2 calls and linear work per level, so its standard bound is \(O(n\log n)\), label 4. B has one half-size call plus constant work across \(O(\log n)\) levels, giving label 1. **2. Solve C and D by summation:** C decreases n by one and adds constant work each time, yielding \(O(n)\), label 2. D decreases n by one and adds linear work, whose sum \(n+(n-1)+\cdots+1\) is \(O(n^2)\), label 3. **3. Combine the assignments:** The intended mapping is A–4,B–1,C–2,D–3. **Answer: C — A–4, B–1, C–2, D–3.** **Convention note:** The source writes O(...) in the additive terms. The displayed mappings give the standard upper bounds; corresponding tight Theta bounds require the intended constant/linear work to be of that order. A: **Incorrect:** A and D are exchanged: the branching recurrence is n log n and the decrement-by-one linear-work recurrence is quadratic. B: **Incorrect:** C is linear, not quadratic, and D is quadratic rather than linear. C: **Correct:** All four recurrence patterns match their intended complexity labels. D: **Incorrect:** A is not logarithmic, and B is not quadratic.

**1. Follow the five-element grouping in the code:** The sorted groups are [5,7,9,13,18], [9,14,15,33,60], [1,14,15,17,41], [6,6,8,11,15] and [2,9,17,19,31]. **2. Extract the programmed index-2 entries:** The middle elements of these groups are 9,15,15,8,17. Thus the recursively supplied list M is [9,15,15,8,17]. **3. Execute the base case:** Since M has five elements, it is sorted to [8,9,15,15,17] and L[2] is returned. The function therefore returns 15. This traces the actual median-of-medians code rather than assuming it simply sorts the original list. **Answer: A — 15.** **Convention note:** This routine returns a recursively selected median-of-medians pivot; that pivot need not always equal the exact median of the complete original input. Its fixed index 2 also assumes the relevant groups have at least three elements, which they do in this question. A: **Correct:** The third entry of the sorted list of group medians is 15. B: **Incorrect:** 9 is one group median but is not the median of all five medians. C: **Incorrect:** 14 occurs in the input groups but is not the returned group-median value. D: **Incorrect:** 17 is the largest group median, not their middle element.

**1. Explain relaxation with negative weights:** After at most V−1 complete edge-relaxation passes, Bellman–Ford has correct distances when no source-reachable negative cycle affects the relevant paths. Negative edge weights by themselves are allowed. **2. Handle disconnected vertices:** Vertices unreachable from the source retain infinite distance. The algorithm can still compute the source-reachable distances in a disconnected graph. **3. Interpret negative-cycle failure:** A reachable negative cycle permits arbitrarily cheaper walks for vertices reachable from that cycle, so finite shortest distances there do not stabilize. An additional relaxation pass detects such a cycle. The method is not a greedy one-vertex-finalization algorithm. **Answer: A, B, C — A, B and C.** **Convention note:** B and C use the customary source-reachable/affected-vertex qualification. A negative cycle in a disconnected unreachable component does not invalidate distances from the chosen source. Bellman–Ford can detect reachable negative cycles; “not handle” means not returning finite shortest paths where none exist. A: **Correct:** Unreachable vertices can remain at infinity while reachable vertices are processed normally. B: **Correct:** Source-reachable negative cycles can keep decreasing affected distances, so finite shortest paths there are undefined. C: **Correct:** Negative weights are supported; reachable negative cycles prevent ordinary finite shortest-distance output for affected vertices. D: **Incorrect:** Bellman–Ford uses repeated relaxation, with a dynamic-programming interpretation, rather than a greedy settled-vertex strategy.

**1. Express search cost using height:** A BST search follows one root-to-leaf path and takes \(\Theta(h)\) worst-case time for height h. **2. Compare balanced and skewed shapes:** A balanced tree has \(h=\Theta(\log n)\), so the tight search bound is logarithmic. An unbalanced tree can be a chain with \(h=\Theta(n)\), producing linear worst-case time. **3. Select the intended false descriptions:** A incorrectly promises logarithmic time even for an unbalanced tree. B gives linear time for a balanced tree rather than its tight logarithmic bound. C and D give the standard intended worst-case classifications. **Answer: A, B — A and B under the intended tight-complexity convention.** **Convention note:** Literally, O(n) is also a valid loose upper bound for an O(log n) balanced search. Thus B is not false under the formal upper-bound definition of big-O; the supplied key uses “complexity” to mean the tight growth rate. With literal big-O semantics only A is false. A: **Correct:** Select this false claim: an unbalanced chain can require n comparisons. B: **Correct:** Select this under the exam’s tight-bound convention: balanced search is Theta(log n), not a tight linear bound. C: **Incorrect:** Do not select: an unbalanced tree can have a linear-length path in the worst case. D: **Incorrect:** Do not select: a balanced BST has logarithmic height.

**1. Divide and solve recursively:** For the standard two-dimensional Euclidean closest-pair problem, split the points into two x-ordered halves, recursively find the closest distance in each, and let δ be the smaller result. **2. Restrict the cross-boundary search:** A cross-boundary pair closer than δ must lie in the strip of width 2δ about the dividing line. Keeping that strip in y order and using the packing bound means each point needs only a constant number of nearby comparisons, not every cross-half pair. **3. Derive the complexity:** With maintained y order, the combine work is O(n), giving \(T(n)=2T(n/2)+O(n)=O(n\log n)\), including the initial sorting. Pair distances use \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\), or squared distances for equivalent comparisons. **Answer: A, B, C — A, B and C.** **Convention note:** The bound refers to the standard planar Euclidean divide-and-conquer implementation that maintains y-sorted lists. Re-sorting every strip at every recursion level can instead give O(n log² n). A: **Correct:** Euclidean separation is the metric for the standard planar closest-pair problem. B: **Correct:** The algorithm recursively solves the two smaller point subsets. C: **Correct:** Linear combining and logarithmic recursion depth give the optimal comparison-model O(n log n) bound. D: **Incorrect:** The strip/packing argument avoids the quadratic comparison of every left point with every right point.

**1. Sort the graph edges:** AB=2, DE=3, BE=4, BD=5, BC=6, CE=7 and AC=8. Kruskal selects the cheapest edge that connects different components. **2. Grow the forest without cycles:** Add AB, DE and BE. These connect A,B,D,E. Reject BD=5 because B and D are already connected through E; adding it would form a cycle. **3. Attach the remaining vertex:** Choose BC=6 to add C. The four selected edges span all five vertices, and their total is \(2+3+4+6=15\). **Answer: 15.**

**1. Use the specified height convention:** The empty tree has height 0, so a single root has height 1 and height 5 means five node levels. **2. Maximize each level:** A binary tree can have at most 1,2,4,8,16 nodes on those five levels. A perfect binary tree achieves all these maxima. **3. Sum the geometric series:** \(N_{max}=1+2+4+8+16=2^5-1=31\). Using an edge-height convention would shift the exponent, which is why the empty-tree convention matters. **Answer: 31.**