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

**1. Recall Dijkstra’s greedy invariant:** The algorithm finalizes the unvisited vertex with the smallest tentative distance. Nonnegative edge weights ensure that a later route through an unvisited vertex cannot improve that finalized distance. **2. Explain the negative-edge failure:** For edges s→a=2, s→b=5 and b→a=−10, a can be finalized at distance 2 before b is processed, although the path through b has length −5. A visited-once implementation does not reconsider a. **3. Compare weight transformations:** Multiplication by a positive constant scales every path cost equally and preserves minimizers. Adding c to each edge adds c times the number of edges on a path, so paths of different lengths can change order. For instance, a direct edge of weight 3 beats two unit edges only after a sufficiently large additive increase. **Answer: A, C, D — negative-edge failure, positive-scaling invariance and minimum-distance selection.** A: **Correct:** A later negative edge can invalidate the finalization invariant. B: **Incorrect:** An equal additive increase penalizes paths according to their numbers of edges and can change the shortest route. C: **Correct:** A positive multiplicative factor preserves the ordering of all path weights. D: **Correct:** Choosing the smallest tentative-distance unvisited vertex is the algorithm’s greedy step.

**1. Apply the cut property:** e is the uniquely lightest edge crossing the cut (X,Y), because all edge weights are distinct. Such an edge belongs to every minimum spanning tree. **2. Justify the exchange:** If a spanning tree omitted e, adding it would create a cycle containing another edge crossing the same cut. That edge is heavier; replacing it by e reduces the tree’s weight, contradicting minimality. **3. Distinguish an MST edge from a bridge:** An edge need not belong to every s-to-t path merely because it is the lightest cut edge. In a triangle there can be a two-edge route between its endpoints avoiding e. Therefore statement 1 is false and statement 2 is true. **Answer: B — Only 2.** **Convention note:** As implicit in the reference to a spanning tree, assume the graph is connected; otherwise the corresponding statement applies to a minimum spanning forest. A: **Incorrect:** A lightest cut edge need not be a bridge or occur on every endpoint-to-endpoint path. B: **Correct:** Only the minimum-spanning-tree claim follows from the cut property. C: **Incorrect:** The first statement fails in a triangle with an alternate route. D: **Incorrect:** The second statement is guaranteed by the unique lightest-cut-edge property.

**1. State the dynamic-programming subproblem:** Floyd–Warshall computes distances for every ordered vertex pair while progressively allowing more intermediate vertices. Its update is \[D_{ij}\leftarrow\min(D_{ij},D_{ik}+D_{kj}).\] **2. Check weight and cycle restrictions:** Negative edge weights are allowed because the update does not use Dijkstra’s greedy finalization rule. Negative cycles prevent finite shortest-path values for affected reachable pairs; the algorithm can detect them through negative diagonal entries. **3. Identify the correct description:** It is an all-pairs algorithm and does not require an acyclic graph. Finite shortest-path computation assumes no relevant negative cycle. **Answer: C — It computes shortest paths between every pair of vertices and can handle .** A: **Incorrect:** Negative edges are allowed; negative cycles are the relevant obstruction. B: **Incorrect:** It solves all-pairs rather than only single-source shortest paths. C: **Correct:** This describes its scope and the condition for well-defined finite distances. D: **Incorrect:** Cycles are permitted provided they do not create a negative-cycle obstruction.

**1. Delete the minimum and restore the heap:** Start with [2,5,10,15,7,20,25,18,19]. Move the last value 19 to the root and remove 2. Sifting down swaps it with 5 and then 7, giving [5,7,10,15,19,20,25,18]. **2. Insert 6:** Append 6 at index 8. It is smaller than its parent 15, so swap them; it is then smaller than parent 7, so swap again. It stops below 5, giving [5,6,10,7,19,20,25,18,15]. **3. Read only the leaves:** In a zero-based heap of length 9, leaves occupy indices floor(9/2)=4 through 8. Their values are 19,20,25,18,15, which is the same set as 18,15,19,20,25 in option A. **Answer: A — leaf set {18,15,19,20,25}.** A: **Correct:** It lists exactly the five final leaf values, though in a different order from the array. B: **Incorrect:** 7 has child nodes after insertion and is not a leaf; 15 is a leaf. C: **Incorrect:** 6 moves upward and is an internal node, not a leaf. D: **Incorrect:** 7 is internal and 20 is an omitted leaf.

**1. Use the max-heap order:** Every parent is at least as large as its children. A minimum therefore occurs at a leaf, although an equal minimum may also appear internally when duplicates exist. **2. Count the candidates:** A complete heap has about n/2 leaves. The heap property imposes no ordering among them, so an adversarial input can place the unique minimum at any leaf. **3. Establish the tight bound:** Scanning all leaves takes O(n) time and requires Ω(n) comparisons in the worst case. Therefore the optimal worst-case complexity is Θ(n), matching the O(n) option. **Answer: C — O(n), with tight worst-case bound Θ(n).** A: **Incorrect:** The minimum is not stored at a fixed location such as the root. B: **Incorrect:** The height bound does not order the leaves or identify which contains the minimum. C: **Correct:** A linear scan of the leaves is sufficient and worst-case necessary. D: **Incorrect:** Sorting is unnecessary; a direct scan achieves a better bound.

**1. Construct the relevant BST path:** Inserting 50,30,70,20,40,60,80 makes 50 the root, 70 its right child and 60 the left child of 70. Other inserted keys do not alter that path. **2. Search for 60:** Compare with 50 and go right; compare with 70 and go left; compare with 60 and stop. The visited keys are 50→70→60. **3. Count key comparisons:** There are three visited keys and therefore three key-to-key comparisons, including the successful equality at the final node. **Answer: B — 3.** **Convention note:** A comparison means one three-way comparison with a visited key, not counting separate low-level equality and ordering tests in a particular implementation. A: **Incorrect:** It counts the two traversed edges but omits the comparison at the found node. B: **Correct:** The search compares against 50, 70 and 60. C: **Incorrect:** No fourth node is visited on the search path. D: **Incorrect:** No fifth comparison is required.

**1. Use the AVL height bound:** An AVL tree has height O(log n). The path between any two nodes goes upward to their lowest common ancestor and then downward, using at most twice the tree height. **2. Establish the always-true claim:** Twice an O(log n) height is still O(log n), so the shortest path between any two nodes has that asymptotic bound. **3. Distinguish height balance from other properties:** AVL balance constrains subtree heights, not exact medians or subtree sizes. For example, child subtree heights 3 and 2 can have sizes 7 and 2, differing by 5. Also, an AVL tree with root 4, left chain 2→1 and right chain 6→7 has two leaves but three internal nodes. **Answer: B — every two-node shortest path has length O(log n).** A: **Incorrect:** Height balance does not require the left and right subtrees to have equal sizes or the root to be a median. B: **Correct:** Any two-node path has at most twice the logarithmic AVL height. C: **Incorrect:** Valid AVL subtree sizes can differ by more than three even when their heights differ by one. D: **Incorrect:** The five-node AVL counterexample has two leaves and three internal nodes.

**1. Apply the prefix-free requirement:** No complete character code may be the initial segment of a different character code. This allows decoding to stop unambiguously at the end of each codeword. **2. Check option A:** A has code 0 while C has code 01, so A’s code is a prefix of C’s. Also B has code 1 while D has code 10, giving another violation. **3. Check the alternatives:** The code sets {0,10,110,111}, {1,01,001,000}, and {00,01,10,11} contain no codeword that prefixes another. They satisfy the property asked about. **Answer: A — A: codes 0,1,01,10 violate the prefix property.** A: **Correct:** Select this invalid allocation: 0 prefixes 01, and 1 prefixes 10. B: **Incorrect:** This allocation is prefix-free; no complete code starts another. C: **Incorrect:** Its progressively longer zero-led codes remain prefix-free. D: **Incorrect:** Distinct equal-length codewords cannot prefix one another.

**1. Sort by finishing time:** The greedy activity-selection rule chooses the earliest finishing available activity, then discards overlapping ones. The first choice is A2=(1,4). **2. Continue with compatible activities:** After time 4, the earliest finishing compatible activity is A5=(5,7). After time 7 choose A1=(8,11), and then A10=(12,14). The selected schedule is (1,4),(5,7),(8,11),(12,14). **3. Explain why the greedy count is optimal:** Choosing an earliest finish leaves at least as much remaining time as any other first choice. Repeating that exchange argument gives a maximum-size compatible set, here containing four activities. **Answer: B — 4.** A: **Incorrect:** The greedy schedule explicitly contains four compatible activities. B: **Correct:** The earliest-finish selection yields four activities and is cardinality-optimal. C: **Incorrect:** After the selected finish times, there is no fifth compatible activity available. D: **Incorrect:** The stated intervals do not permit a six-activity non-overlapping schedule.

**1. Compute original and compressed sizes:** The original 1000-character file uses 1000×4=4000 bits. At average Huffman length 3 bits per character, the encoded data use 1000×3=3000 bits. **2. Measure savings against the original size:** \[100\frac{4000-3000}{4000}=25\%.\] The original size is the denominator; the compressed size is not. **Answer: B — 25.** **Convention note:** This compares encoded character payload sizes, as requested. No separate codebook or container overhead is specified. A: **Incorrect:** It does not match the one-bit saving out of four original bits. B: **Correct:** The saving is 1000 of 4000 bits, or 25%. C: **Incorrect:** The given code lengths imply a quarter reduction, not 30%. D: **Incorrect:** It divides the saving by the compressed size rather than the original size.

**1. Count the tiny subproblem’s work:** With at most three points, there are at most \(\binom32=3\) pairwise distances to compare. This is a small constant amount of work. **2. Compare against further recursion:** More splitting would add recursive calls and combine-step bookkeeping without a meaningful saving on just three distances. Brute force is therefore a simple efficient base case, while larger inputs still benefit from divide and conquer. **Answer: D — The overhead of further recursive division outweighs its benefit for very small .** A: **Incorrect:** Brute force is not asymptotically faster on large inputs; the reason is its low constant cost here. B: **Incorrect:** The possible use of dynamic programming does not explain this base-case choice. C: **Incorrect:** The closest pair must still be determined by examining distances. D: **Correct:** Further recursion adds overhead that is unnecessary for a tiny subproblem.

**1. Identify the worst-case requirement:** Random or small-sample pivots may give good expected behavior, but an unlucky sequence of highly unbalanced partitions can still take quadratic time. **2. Use Median-of-Medians:** Group elements into constant-size groups, find their medians, and recursively select the median of those medians. This guarantees that a fixed fraction of elements can be discarded on either side of the pivot. **3. Bound the recurrence:** With groups of five, \[T(n)\le T(\lceil n/5\rceil)+T(7n/10+O(1))+O(n)=O(n).\] The recursive fractions sum to less than one, enabling a linear worst-case bound. **Answer: D — Selecting the pivot using the Median-of-Medians algorithm..** A: **Incorrect:** A constant random sample does not guarantee a balanced pivot on every input. B: **Incorrect:** A random pivot gives expected linear time, but worst-case quadratic time remains possible. C: **Incorrect:** Sorting the entire subarray to get its median costs O(n log n) with standard comparison sorting. D: **Correct:** Its guaranteed partition quality supports deterministic worst-case linear selection.

**1. Determine the minimum tree weight:** The triangle on a,b,c has three edges of weight 2. Connecting those three vertices requires two of them, costing 4. Connecting d requires one of its edges to b or c, each of weight 4. Thus every MST has weight β=8. **2. Count the minimum trees:** Any two of the three triangle edges form a tree on a,b,c, giving three choices. Independently, d can be attached through b or c, giving two choices. Hence α=3×2=6. **3. Exclude other forms and add:** Using both d-edges would leave room for only one weight-2 edge and cost at least 10, so it is not minimum. Therefore \(\alpha+\beta=6+8=14\). **Answer: 14.**

**1. Use the stated node-count height:** A complete binary tree of height h, with the root counted as level 1, has between 2^(h−1) and 2^h−1 nodes. Equivalently, \(h=\lfloor\log_2n\rfloor+1\). **2. Substitute n=1023:** \(1023=2^{10}-1\), so the tree has ten completely filled levels. Its height under the question’s convention is 10, not the edge-count height 9. **Answer: 10.**

**1. Bound inversions for a fixed length:** A list of n distinct elements contains only \(\binom n2=n(n-1)/2\) index pairs, so it cannot have more inversions than that. A reverse-sorted list reaches this bound. **2. Find the smallest feasible n:** For n=5 the maximum is 10, below 15. For n=6 the maximum is \(6\cdot5/2=15\), so six elements can suffice. **3. Show attainability:** The list [6,5,4,3,2,1] has every earlier element larger than every later one, yielding exactly 15 inversions. Thus the minimum length is 6. **Answer: 6.**

**1. Compare branching with shrinkage:** For T₁, a=b=2; for T₃, a=b=8; and for T₄, a=b=3. Each recursion level has total subproblem size n, so O(n) work per level over O(log n) levels gives O(n log n). **2. Analyze T₂ separately:** For \(T_2(n)=4T_2(n/2)+O(n)\), the number of unit-size leaves is \(4^{\log_2n}=n^2\). With base-case cost 1, the leaf cost alone is Ω(n²), and the full recurrence has Θ(n²) cost under nonnegative O(n) overhead. **3. Select the upper-bound matches:** T₁, T₃ and T₄ have O(n log n) running time, while T₂ does not. **Answer: A, C, D — T₁, T₃ and T₄.** **Convention note:** The recurrences state O(n), not Θ(n), nonrecursive work. The selected O(n log n) upper bounds remain valid; a matching Θ(n log n) claim would require a corresponding linear lower bound on that work. A: **Correct:** Two half-size branches have total size n per level and logarithmic depth. B: **Incorrect:** Four half-size branches produce n² base-case leaves. C: **Correct:** Eight one-eighth-size branches retain O(n) work per level over logarithmic depth. D: **Correct:** Three one-third-size branches also give O(n) work per level over logarithmic depth.