Programming, Data Structures and Algorithms using Python · Quiz 1 · May 2026

**1. Trace the recursive arguments:** The calls are \((45,75)\to(45,30)\to(15,30)\to(15,15)\). Each step subtracts the smaller positive argument from the larger. **2. Reach the base case:** When x=y=15, the function returns x, and that value propagates through every return. This is the subtraction version of Euclid’s greatest-common-divisor algorithm. **Answer: 15.**

**1. Count all possible edges:** A simple undirected complete graph on 8 vertices has \(\binom82=8(7)/2=28\) distinct edges. **2. Subtract existing edges:** The graph already contains 10, so exactly \(28-10=18\) missing edges must be added. Connectedness does not change this count. **Answer: 18.** **Convention note:** As usual for this question, the graph is simple: no parallel edges or self-loops.

**1. Follow the growth of x:** It starts at 1 and takes values \(10,10^2,\ldots,10^k\) after k iterations. The loop stops at the first k for which \(10^k\ge n\), giving \(k=\lceil\log_{10}n\rceil\) for n>1. **2. Count work:** Each iteration does constant elementary work in the standard unit-cost analysis. Thus the tight growth is \(\Theta(\log n)\), represented by B. **Answer: B — O(log n), the tight class.** **Convention note:** The choices use O notation informally for a tight running-time description. Literally a logarithmic algorithm is also O(n) and O(n log n); B is the most informative listed bound. Python arbitrary-precision arithmetic is not charged by bit length in this course analysis. A: **Incorrect:** The number of iterations grows without bound with n. B: **Correct:** It is the tight logarithmic running-time class. C: **Incorrect:** It is a valid but loose upper bound, not the tight class sought in this single-choice question. D: **Incorrect:** It is also a loose upper bound; there is no additional linear outer loop.

**1. Sort the keys:** Second coordinates in ascending order are 0,1,1,2,5,5. Stability requires the two key-1 points to remain (8,1) before (6,1), and the key-5 points to remain (7,5) before (2,5). **2. Assemble the stable result:** [(9,0),(8,1),(6,1),(5,2),(7,5),(2,5)] is exactly B. The first coordinates are not secondary sorting keys here. **Answer: B — [(9,0),(8,1),(6,1),(5,2),(7,5),(2,5)].** A: **Incorrect:** It reverses the two points with second coordinate 1. B: **Correct:** It preserves both original equal-key orders. C: **Incorrect:** It reverses the two points with second coordinate 5. D: **Incorrect:** It reverses both equal-key groups.

**1. Relate swaps to inversions:** The code swaps adjacent out-of-order elements. Each such swap removes exactly one inversion, so its total swap count equals the input inversion count. **2. Find the extremes:** An increasing list has zero inversions and no swaps. A decreasing list of 8 distinct values has \(\binom82=28\) inversions. Thus the minimum is 0 and maximum 28; the seven insertion stages are not seven mandatory swaps. **Answer: B — Minimum: 0, Maximum: 28.** A: **Incorrect:** The maximum 36 incorrectly sums through 8 rather than 7. B: **Correct:** It gives the attainable extrema 0 and 28. C: **Incorrect:** An already sorted list needs no swaps, and 36 is too large. D: **Incorrect:** It confuses at least seven comparisons/stages with swaps.

**1. Search for a boundary, not for numerical order:** The Boolean predicate “is odd” is true on a prefix and false on the suffix. Binary search can locate the first even index b, including b=0 for all-even and b=n for all-odd inputs. **2. Obtain the counts:** Maintain a half-open search interval and test only middle-element parity. Each test discards half of the possible boundary positions, so the worst-case time is \(\Theta(\log n)\). Once b is found, odd count=b and even count=n−b. **Answer: A — O(log n), using boundary search.** A: **Correct:** Binary search exploits the monotone parity boundary. B: **Incorrect:** It is a looser upper bound than logarithmic search, not the optimal rate. C: **Incorrect:** A scan works but does unnecessary tests given the prefix property. D: **Incorrect:** Sorting is unnecessary and more expensive.

**1. Trace the scan with pivot 5:** Start i=1. The values 3 and 1 are already in the less-than region and self-swap, advancing i to 3. Value 7 is skipped. When j=4, swap 0 with 7 to obtain [5,3,1,0,7,10,2], then i=4. **2. Finish partitioning:** Skip 10. At j=6, swap 2 with 7, obtaining [5,3,1,0,2,10,7], with i=5. Finally swap the pivot at index 0 with index i−1=4. **3. State the exact list:** [2,3,1,0,5,10,7]. Both sides satisfy the partition invariant but need not be internally sorted. **Answer: D — [2,3,1,0,5,10,7].** A: **Incorrect:** It is a possible-looking partition but not the list produced by these swaps. B: **Incorrect:** It shifts the pivot out rather than performing the final swap used by the code. C: **Incorrect:** It replaces the leading value by the wrong element after the final pivot swap. D: **Correct:** It exactly matches the scan and final pivot exchange.

**1. Apply FIFO deletions:** Enqueue 5,3 gives [5,3]; the first Dequeue removes 5. Enqueue 7,1 gives [3,7,1]; the second Dequeue removes 3. **2. Append the final item:** Enqueue 9 gives [7,1,9]. The first retained item is the front 7 and the last is the rear 9. **Answer: C — Front: 7, Rear: 9.** A: **Incorrect:** 3 was removed by the second Dequeue. B: **Incorrect:** 1 is not the rear after 9 is enqueued. C: **Correct:** It identifies the endpoints of [7,1,9]. D: **Incorrect:** 1 is the middle element, not the front.

**1. Identify the traversal:** Each unvisited neighbor is explored through a recursive call before the current loop resumes. This is depth-first search. Encountering a visited neighbor other than the parent detects an undirected cycle. **2. Limit the reachable region:** A single call can follow only edges in the starting vertex’s connected component. Without the specified outer loop, no vertex in a different component is explored, so cycles there cannot be detected. **Answer: A — DFS confined to the starting component.** A: **Correct:** It correctly identifies recursive DFS and its one-component scope. B: **Incorrect:** The code uses recursion rather than a FIFO frontier for BFS. C: **Incorrect:** There is no mechanism to start a traversal in other components. D: **Incorrect:** Both its BFS identification and all-component scope are wrong.

**1. Compare the DFS intervals:** The times satisfy \(\operatorname{pre}(v)=1<\operatorname{pre}(u)=3<\operatorname{post}(u)=6<\operatorname{post}(v)=10\). Thus u is a descendant of v in the DFS tree. **2. Use the direction of the edge:** The edge goes from u back to its ancestor v. It is therefore a back edge; a tree/forward edge would run in the opposite ancestor-to-descendant direction, and cross-edge intervals would be disjoint. **Answer: C — a back edge.** A: **Incorrect:** The given edge goes toward the ancestor, not toward a descendant. B: **Incorrect:** The two time intervals are nested, not disjoint. C: **Correct:** The target is an ancestor of the source.

**1. Extract the dominant terms:** \(f(n)=10n^4+6n^3=\Theta(n^4)\), \(g(n)=10n^3+2n^2=\Theta(n^3)\), and \(h(n)=12n^3\log n+6n^2=\Theta(n^3\log n)\). **2. Compare ratios:** \(f/g\) grows like n, \(g/h\) is bounded and tends to zero, \(f/h\) grows like \(n/\log n\), and \(h/f\) tends to zero. Therefore g=O(h) and h=O(f), while the other two claimed upper bounds fail. **Answer: B, D — B and D.** A: **Incorrect:** A quartic cannot be bounded by a constant times a cubic for all large n. B: **Correct:** The extra logarithm makes h grow at least as fast as g. C: **Incorrect:** n/log n is unbounded, so h cannot upper-bound f up to a constant. D: **Correct:** n³ log n grows more slowly than n⁴.

**1. Use the available pointers:** The list is singly linked, and both head and tail are known. Insertion after head changes a fixed number of next pointers. Appending uses tail.next and then updates tail, also a fixed number of operations. **2. Identify required searches:** Deleting the tail requires its predecessor, which cannot be obtained from the tail’s one-way pointer; a scan may be needed. A data value alone likewise requires a search before deleting a matching node. **Answer: B, C — B and C.** A: **Incorrect:** Finding the penultimate node can take linear time. B: **Correct:** The insertion location is already given by head. C: **Correct:** The tail pointer gives direct access to the append location. D: **Incorrect:** Searching for the given value takes linear time in the worst case.

**1. Bound distances across any undirected edge:** A shortest path to u followed by edge uv gives \(d(s,v)\le d(s,u)+1\). Reversing the edge gives the symmetric inequality. Hence \(|d(s,u)-d(s,v)|\le1\). **2. Show both allowed cases can be nontree edges:** A triangle rooted at one vertex has a same-level edge between the other two. A square s–a–c–b–s can have tree edges s–a,s–b,a–c and nontree edge b–c, joining levels 1 and 2. Thus differences zero and one are both possible. **Answer: A, B — A and B.** A: **Correct:** A same-level edge occurs in the triangle example. B: **Correct:** A nontree edge can join adjacent BFS levels. C: **Incorrect:** It contradicts the distance-difference bound of one. D: **Incorrect:** Any difference greater than two also violates that bound.

**1. List the precedence constraints:** The DAG has A→B, A→C, B→D, C→D, C→E and D→E. Every edge’s source must precede its target in a topological order. **2. Determine the choices:** A must come first; B and C can appear in either order, but both must precede D, and D must precede E. Hence A,B,C,D,E and A,C,B,D,E are valid. **Answer: B, C — A, B, C, D, E; A, C, B, D, E.** A: **Incorrect:** It places D before its prerequisite C. B: **Correct:** Every edge points from an earlier to a later position. C: **Correct:** Interchanging B and C is allowed; all edge constraints remain satisfied. D: **Incorrect:** It places D before its prerequisite B. E: **Incorrect:** It places E before D despite D→E.

**1. Count one merge’s worst case:** Merging lengths a and b uses at most a+b−1 element comparisons. Each comparison removes one remaining candidate, and the last item can be copied without another comparison. **2. Add the three stages:** Each 5+5 merge requires at most 9 comparisons; the final 10+10 merge requires at most 19. Therefore the total is \(9+9+19=37\). **3. Check attainability:** Interleaving the sorted values at each stage can keep both inputs nonempty until only one item remains. For example assign the two bottom merges disjoint alternating odd and even ranks, so all three maxima can occur together. **Answer: 37.**

**1. Start at each key’s home slot:** h(k)=k mod 8. Key 41 starts at index 1 and is found immediately; 18 starts at 2 and is also found immediately. **2. Trace displaced keys:** Key 26 starts at 2, checks 18, then is found at 3: two probes. Key 34 also starts at 2, checks indices 2,3,4: three probes. Key 14 starts at 6 and takes one probe. **3. Sum successful-search probes:** 1+1+2+3+1=8. Count the successful final index check as a probe too. **Answer: 8.**