A First Taste of Algorithms · Problem Set 7

Concept & Counterexample

3.1 Claim: “randomized quicksort has no worst case.” Exhibit, for n = 4, an explicit sequence of pivot choices under which the algorithm performs its full quadratic bill — then compute the probability of that sequence and state the claim correctly. Improbable and impossible are different words; the chapter’s trade was one for the other.

3.2 Claim: “the adversary can still defeat randomized quicksort: just supply sorted input, which was the killer before.” Explain the quantifier shift that breaks this — when are the coins flipped relative to the input choice? Then find the loophole that resurrects the adversary in practice: your lab seeds its generator with a fixed number. If the adversary knows the seed, what can it reconstruct, and what does this say about the word “random” in “pseudo-random”? (This is a real attack class; the repair — secret, unpredictable seeds — is a real industry.)

3.3 Claim: “the hat-check average is 1, so usually about one person gets their hat.” For n = 3, your 1.2 enumeration has the distribution — is the claim roughly honest there? Now invent a different game whose average is also 1 but where “usually about 1” is badly false (two outcomes suffice). State the moral: what does an expectation alone not tell you, and which instrument from the lab fills the gap?

3.4 Claim: “a hash function that spreads keys evenly is all you need.” The adversary disagrees: if the function is public and fixed, what can an adversary who wants to hurt you construct, and what happens to your “constant time on average” when every key lands in one bucket? Connect this to the chapter’s iron law of fixed strategies — hashing’s repair is the same as quicksort’s; say what it is.

3.5 Claim: “366 people guarantee a shared birthday, so the birthday ‘paradox’ is just the pigeonhole principle in slow motion.” Half right. State exactly what pigeonhole proves at 366, what it proves at 23 (nothing!), and what kind of statement — in the vocabulary of this chapter — the 23 result is instead. Two true theorems, two different species; name both species.

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