A First Taste of Algorithms · Problem Set 7
Diamond
4.1 Twenty-three, by inequality alone. Let q(k) be the probability that k people have k different birthdays (365 days, all equally likely). (a) Derive q(k) = (1 − 1/365)(1 − 2/365)···(1 − (k−1)/365), arguing each factor as a conditional step: given no collision so far, the next person must dodge how many taken days? (b) Book 2’s inequality: 1 − x ≤ e^(−x) for all x. Apply it factor by factor to get q(k) ≤ e^(−k(k−1)/730), showing where the sum 1 + 2 + … + (k−1) enters. (c) Conclude: a shared birthday has probability at least ½ as soon as k(k−1) ≥ 730 ln 2. Compute 730 ln 2 ≈ 505.97 and 23 × 22 = 506, and savor the margin of 0.03 — then state the theorem you have proved with no calculator beyond one logarithm: at k = 23, p ≥ 1 − e^(−506/730) > ½. (d) The general moral: for k keys into N buckets the same argument gives the collision threshold at k ≈ √(2N ln 2) ≈ 1.18√N. Verify it predicts 23 for N = 365, and use it to answer: how many random 8-digit ID numbers before a collision is more likely than not? (e) One sentence: the inequality in (b) points the useful direction — it upper-bounds q, hence lower-bounds the collision probability. If it pointed the other way, what exactly would your “proof” of (c) be worth?
Computational Lab
5.1 Lab 7 in full, predictions before runs. Your histogram and its mean are evidence in problems 3.3 and the Diamond’s part (b) check; export the numbers.
Teach It
6.1 Run the birthday bet live: gather any group of 23+ (a class, a team roster, a family reunion — or a list of 23 historical mathematicians’ birthdays pulled from a shelf) and check for a shared birthday, after recording everyone’s prediction. Whatever happens, explain the 253 pairs. Three sentences: did the demonstration or the pairs-argument move them more — and which should it have been, by this book’s own standards?
6.2 Explain to someone why a casino is calm. They face thousands of gamblers, any one of whom might win big tonight — yet the house sleeps well. Use this chapter’s words: whose worst case is whose bad luck, what does linearity promise the house per bet, and what does concentration add that the average alone doesn’t? Then the turn: explain that randomized quicksort is the house. Report whether they bought it.
Questions to talk about
No answer key. These are for arguing over, with someone who read the same chapter.
- Construct the input that makes a fixed-pivot quicksort behave at its worst. How easy was it?
- What does it mean to trust an average? What would have to be true about the spread for the trust to be earned?
- Where else in life do you accept a guarantee about the average rather than the worst case?
All 32 chapters of A First Taste of Algorithms · Foundations · All courses