A First Taste of Algorithms · Problem Set 3

Concept & Counterexample

3.1 Claim: “any procedure that calls itself on a smaller input terminates.” Refute with the smallest broken procedure you can write or describe — then state the second condition the claim forgot, and reconcile with the chapter’s rule.

3.2 Claim: “recursion requires shrinking by at least 1, so calling yourself on n/2 is extra safe.” Find the loophole: a procedure that calls itself on n // 2 (whole-number division) and never terminates for some starting n. What is the floor it forgot?

3.3 In merge, what happens if one of the two input piles is not sorted? Construct a 3-and-3 example where the merge completes without complaint and outputs an unsorted list. Moral, in one sentence: what does merge trust, and what happens to procedures built on trust?

3.4 Claim: “merge sort makes exactly n·log₂ n element-steps.” Test at n = 6: draw the tree (the halves are 3 and 3, then 2-and-1) and count exactly. Is the claim exact, an overcount, or an undercount? Repair the claim’s wording so it is true and still useful.

3.5 Claim: “Hanoi’s exponential cost comes from recursion; an iterative (loop-based) solution would be faster.” What does the Diamond say about this claim before any iterative solution is even examined?

Diamond

4.1 The wall is real: 2ⁿ − 1 is optimal. Two directions, both by induction. (a) Achievability: prove the three-line plan makes exactly 2ⁿ − 1 moves. (You did this in 1.3; restate it as the first half of a theorem.) (b) The lower bound: prove that every legal solution, however clever, makes at least 2ⁿ − 1 moves. Scaffold: at some moment, the largest disk must move for the first time (why must it move at all?). What must be true of the other n − 1 disks at that exact moment — where can they legally be? Conclude that before that moment, a full (n−1)-tower transfer has already happened, and after the largest disk’s last move, another one must still happen. Apply the induction hypothesis twice and add. (c) Compare this lower bound’s style with Chapter 1’s answer-sequence bound. One counts information; this one finds an unavoidable event. Both fence in every strategy, including uninvented ones — point to the sentence in your proof of (b) that does the fencing.

Computational Lab

5.1 Lab 3 in full, predictions before runs. Bring the Break-it where you starve the recursion of its base case: the error message you receive is the deep water’s “physical stack” made visible, and the Teach It tier wants it.

Teach It

6.1 Teach someone the Tower of Hanoi with real objects, in this strict order: let them struggle with 3 disks; have them master 2 disks until automatic; then ask only this question — “can you see a 2-disk job hiding inside the 3-disk job?” — and stay silent until they find it. Write three sentences about the moment the recursion became visible to them (it is visible on a face).

6.2 Retell Lucas’s legend of the 64 golden disks to someone, ending with the 585-billion-year computation done together on a phone calculator from 2⁶⁴ alone. Then ask them: the priests work for free and never err — why does the world still get to keep existing? Report their answer and yours.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses