A First Taste of Algorithms · Problem Set 6

Concept & Counterexample

3.1 Claim: “merge sort is O(n log n) and insertion sort is O(n²), so merge sort is faster.” Produce two refutations from your own Lab 6 data: one about small n and clocks, one about a specific input family where insertion sort beats merge sort at every size in the counted currency. State what the claim should have said.

3.2 Claim: “to speed up insertion sort, find each card’s landing spot by binary search — comparisons drop to O(n log n), so insertion sort becomes as good as merge sort.” The comparison count is right; the conclusion is wrong. Find the cost the claim forgot to count (watch your own hands slide cards), and state insertion sort’s Θ with the repair in place. Currencies, always currencies.

3.3 Claim: “the lower bound proves sorting takes Ω(n log n), so counting sort must have a hidden flaw.” Resolve the apparent contradiction in three sentences, quoting the exact phrase of the theorem that counting sort steps around. Then state what counting sort cannot do: exhibit a sorting task where no finite bucket scheme works and the fence reasserts itself.

3.4 Claim: “counting sort is O(n), so it’s always the best choice when keys are integers.” The hidden variable is the universe size k. Construct a scenario (real numbers welcome: ID numbers, timestamps) where k is so much larger than n that counting sort loses to merge sort by any honest accounting — and give the rule for when the dodge pays.

3.5 Take the score-name pairs from Lab 3’s Break-it 4: [[3, “Ada”], [1, “Hua”], [3, “Noether”]]. Show, step by step, how sorting by score with an unstable method can shred a previous sort by name, while the stable method composes. Then explain why stability is free for insertion sort as humans deal cards (where does the tie naturally land?).

Diamond

4.1 The fence, built by your hands. Prove: every comparison-based sorting algorithm makes at least log₂(n!) comparisons on some input of n distinct items. (a) Model: argue that a deterministic comparison sort is a binary tree — what exactly are its nodes, branches, and leaves, and why does determinism matter to the modeling? (b) The load-bearing wall: prove distinct input orderings cannot share a leaf. Suppose orderings π ≠ σ follow identical answer-paths; the algorithm at that leaf applies one fixed rearrangement to the input; show it cannot correctly sort both, exhibiting the failure (where do π and σ first differ, and what does the fixed rearrangement do to that position?). (c) Geometry: prove a binary tree of depth d has at most 2ᵈ leaves, by induction on d (the only trick, appearance the sixth). (d) Conclude d ≥ log₂(n!), and finish the shape with the crude bound: log₂(n!) ≥ (n/2)log₂(n/2). (e) Two sentences of architecture: set this proof beside Chapter 1’s answer-sequence bound and Chapter 3’s unavoidable-event bound for Hanoi. Which of the three is this one’s sibling, and what single word names what both of them count?

Computational Lab

5.1 Lab 6 in full, predictions before runs. Your clocked crossover point (or your environment’s refusal to produce one) is data for problems 2.1 and 3.1 — record it.

Teach It

6.1 Deal someone twelve cards and ask them to sort their hand while you watch their hands, not the cards. Then show them they were running an algorithm with a name, count its worst case together on a reversed deal, and demonstrate the halver on the table with the same cards. Three sentences: which fact surprised them more — that they already knew an algorithm, or that the table method beat their hands?

6.2 Tell the census story, ending not with IBM but with the fence: explain to your listener, in plain words, what it means that nobody — no company, no genius, no machine — will ever sort by comparisons faster than the n log n shape, and how anyone could possibly know such a thing about algorithms not yet invented. If you can convey “we counted situations, not strategies,” you own this chapter. Report the sentence that finally worked.

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