A First Taste of Algorithms

Problem Set 1

✦ ✦ ✦

The labs are the Computational Lab tier: Lab 0 (Talking to the Machine) and Lab 1 (Counting Steps) accompany this chapter. Do them before the Diamond.

Fluency

1.1 Play the halving strategy by hand on the range 1 to 64, against a friend who picks the number 50. Write down every question and answer. How many questions did you use? How many does the table promise are enough?

1.2 Trace binary search on the sorted list 3, 7, 11, 19, 23, 31, 42, 57, 60, 71, 85, 99 (twelve items) for the target 57. At each step write the region between the fingers and the middle item checked. Repeat for target 4. How many comparisons each?

1.3 For each n, compute the worst-case comparisons for linear search and for binary search: n = 16, n = 1,024, n = 32,768. (Notice anything about these particular numbers?)

1.4 How many times can you halve 1,000,000 before reaching 1? Compute it by repeated halving (a calculator is fine), then check against log₂ from Book 2.

1.5 A sorted list has 500 items. The target is absent. Exactly how many items does linear search examine? At most how many does binary search examine?

1.6 Using the exact count from the deep water, compute ⌈log₂(n+1)⌉ for n = 63, 64, 65. Explain in one sentence why 64 and 65 differ.

Practice

2.1 Your music app holds 4,000 songs. Sorted by title, how many comparisons might finding one song take, at worst? Unsorted? How many songs would the library need before the sorted search’s worst case exceeded 15 comparisons?

2.2 You’re guessing a number between 1 and 1,000,000, but today the answerer may lie once during the game. Don’t solve this fully — it is genuinely hard — but answer two parts: (a) explain in a sentence or two why the plain halving strategy can now fail catastrophically; (b) show that asking every question twice rescues correctness, and count what that costs. (The gap between your repair and the best known repair is real mathematics, and open-ended.)

2.3 A “guess the word” game: I think of a word; you may ask “does it come before ___ in the dictionary?” Roughly how many questions to corner one word among 200,000? Among all ~10⁶ words ever used in English?

2.4 Binary search works on any sorted list — including a list of moments in time. You have 10,000 photos sorted by date, and you want the first photo from your trip last July. Describe the search in words, and count its worst case. (You have just invented how photo apps jump to a date.)

2.5 Three runs of linear search on the same 1,000-item list took 3 steps, 998 steps, and 412 steps. A friend concludes “linear search takes about 471 steps on average.” Name two distinct reasons this conclusion is unjustified. (Chapter 7 will earn the right to such sentences; here, identify what’s missing.)

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