A First Taste of Algorithms · Problem Set 1

Concept & Counterexample

3.1 A classmate claims: “binary search works fine on unsorted lists — I tried it and it found my target.” Construct an unsorted list and a target that is in the list for which binary search wrongly reports absence. Make your example as small as possible.

3.2 Another claim: “if binary search finds the target, the list must have been sorted.” Refute it with a three-item example.

3.3 Claim: “in the guessing game, the question ‘is it bigger than 50?’ is the best first question for the range 1–100.” Is the question “is the number even?” just as good — it also eliminates exactly half? Trace what goes wrong (or doesn’t) when you try to build a whole strategy out of such questions. Then say precisely what property the survivors must keep for the two-finger method to work, and which deep-water sentence that property comes from.

3.4 Claim: “worst case is too pessimistic; the target is usually somewhere in the middle.” Construct a realistic scenario where the absent case — the true worst case — is the overwhelmingly common one. (Hint: think about checking whether a username is taken.)

3.5 Modify binary search so that, when the fingers cross, it reports where the target would belong instead of merely “not found.” Why does the invariant guarantee that this position is correct? (This version is what your phone uses to keep a list sorted as items arrive.)

Diamond

4.1 The lower bound, yours now. Write out the exact-count argument from the deep water as a complete proof, in your own words, of the statement: any strategy that solves the guessing game on 1, …, n with yes/no questions needs at least ⌈log₂(n+1)⌉ questions in the worst case. Your proof must make explicit (a) why two different situations cannot share an answer-sequence, (b) where the “+1” comes from, and (c) why the argument applies to every strategy, including ones nobody has invented. Then answer: does the bound still hold if the questions need not be of the form “is it bigger than x?” — and where in your proof is that fact used (or not used)?

Computational Lab

5.1 Labs 0 and 1, completely — including every Break-it prediction written before running. Bring your prediction gaps (the ones you got wrong) to the Teach It tier: they are your best material.

Teach It

6.1 Teach the guessing game and the halving strategy to someone at home, with one rule: you may not say “algorithm,” “binary,” or “logarithm.” Win the game on 1–1000 in ten questions in front of them, then get them to explain back to you why ten is always enough. Write three sentences on what was hardest for them to believe.

6.2 Explain to the same person why being sure something is missing from a messy drawer costs more than finding something that’s there — and why a sorted drawer changes that. If you can make them feel the asymmetry, you understand this chapter.

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