A First Taste of Algorithms

Problem Set 3

✦ ✦ ✦

Lab 3 (The Visible Staircase) is the Computational Lab tier. The Diamond wants the lab’s counting program as a check on part (a).

Fluency

1.1 With three coins, perform the 7-move solution for three disks, writing each move as “disk d: peg → peg.” Then, without playing, use the three-line plan to write out all 15 moves for four disks. Check your list’s move count against the table.

1.2 Extend the M(n) table to n = 12 using the recurrence (not the formula). Then verify M(12) against 2¹² − 1.

1.3 Prove M(n) = 2ⁿ − 1 by induction from the recurrence M(n) = 2M(n−1) + 1, M(1) = 1. Two lines suffice; write them.

1.4 Merge these two sorted piles by hand, recording every comparison: [2, 9, 11, 30] and [4, 5, 12, 28]. How many comparisons did you make? What is the most comparisons merging two piles of four could ever take — and design the two piles that achieve it.

1.5 Draw the full merge sort tree for the 8-item list [7, 3, 9, 1, 8, 2, 6, 4]: every box, every split, and the sorted contents flowing back up. Verify that each level’s merge work totals 8.

1.6 Evaluate, by drawing the level sums of the tree: T(n) = 3·T(n/3) + n. Which of the deep water’s three stories is it?

Practice

2.1 Rewrite Chapter 1’s binary search as a recursion in words: “to search a region: if empty, absent; check the middle; otherwise search the ___ half.” What is the floor? What does the recursion’s cost recurrence look like, and which master-theorem story does it tell?

2.2 You have 2 parents, 4 grandparents, 8 great-grandparents. (a) How many ancestors n generations back does the doubling rule predict? (b) Thirty generations is roughly 800 years; compute the rule’s prediction and compare it with the entire population of medieval Earth (~400 million). (c) The rule’s conclusion is absurd, so a hypothesis fails. Find it — what does the failure tell you about your family tree’s actual shape? (Recursions, like all arguments, are only as true as their assumptions about the smaller case.)

2.3 A sheet of paper is 0.1 mm thick; folding doubles the thickness. The Moon is 384,400 km away. How many folds reach it? Solve using the M(n)-table style first (make the doubling table), then with one logarithm. Why does the answer feel impossible, and what (physically) actually stops it?

2.4 A tournament: 64 players, single elimination. How many matches are played in total? Find the answer two ways: by the recurrence/tree, and by a one-sentence counting argument with no recursion at all. (The second way is the kind of argument that makes mathematicians grin.)

2.5 Phone chain: news must reach 1,000 people; each person who knows it calls one person per minute. Model the spread as a recurrence for K(t), the number who know after t minutes, and find how many minutes are needed. Then the variant: each informed person makes only three calls total, then stops. Does the news still reach everyone? What changed in the tree?

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