A First Taste of Algorithms

Problem Set 6

✦ ✦ ✦

Lab 6 (Counted and Clocked) is the Computational Lab tier; problems 2.1 and 3.2 use its measurements.

Fluency

1.1 Sort the hand 7, 3, 9, 1, 8 by insertion sort on paper, drawing the hand after each arrival and counting every comparison. Then feed the same five cards in reverse-sorted order and count again; check against n(n−1)/2.

1.2 Compute n(n−1)/2 and n·log₂ n (round freely) for n = 16, 256, 4,096. At each n, how many times more does the plodder pay?

1.3 Compute log₂(n!) exactly for n = 3, 4, 5 (small factorials by hand), and compare with merge sort’s element-steps on the same n from Lab 3’s counter. Is the fence below the algorithm at every n?

1.4 Classify each cost into its Θ shape, citing which chapter’s table you met it in: 2ⁿ − 1; ⌈log₂(n+1)⌉; n(n−1)/2; calls of the memoized staircase; element-steps of merge sort; steps of linear search.

1.5 True positions: “f is O(g)” is a ceiling claim. For each pair, say which of O, Ω, Θ honestly relate f to g: f = 3n², g = n²; f = n log n, g = n²; f = 100n, g = n²; f = n², g = n log n.

1.6 Using the crude bound n! ≥ (n/2)^(n/2), show by hand that log₂(8!) ≥ 8 — then compute log₂(8!) exactly (8! = 40,320) and report how loose the crude bound was. Loose but load-bearing: what did the bound’s shape establish that its constant didn’t need to?

Practice

2.1 The toll, exactly. A list of n items will be searched s times. Unsorted: each search costs n. Sorted once (n log₂ n) then searched: each costs log₂ n. For n = 1,000,000, find the smallest s for which sorting first is the cheaper total. Then derive the rule of thumb in symbols and compare with the chapter’s “more than about log n searches.”

2.2 A librarian receives returned books all day and must keep the shelf ordered. Argue that her natural method is insertion sort run in slow motion — and explain why her n² is nothing to fix (what is her n per insertion, and what would she pay to “batch” with merge sort at closing time instead?). Sometimes the plodder is the right professional.

2.3 Design counting sort, in full sentences or code, for sorting a million dates-of-birth by year (years 1900–2030). State the exact cost in touches and buckets. Then the follow-up: your output groups by year but you also want each year’s people ordered by month — compose two counting sorts and state the property from the deep water your composition silently requires.

2.4 You have k sorted piles totaling n cards (the ends of k merge sorts, say). Two plans to combine them: merge pile 1 with 2, the result with 3, the result with 4, …; or merge them as a balanced tournament, pairs of pairs. Count both plans’ element-steps for k = 8 equal piles of m cards each, and explain the difference using Chapter 3’s tree-of-levels picture. (You are re-deriving why the halver halves.)

2.5 “Is it already sorted?” is itself an algorithm question. Give the obvious checker and its exact cost. Then prove a small fence: any checker must, in the worst case, examine every adjacent pair — exhibit what an adversary does with any pair you skip. (A fence argument with no tree in it; fences come in many materials.)

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