A First Taste of Algorithms

Problem Set 7

✦ ✦ ✦

Lab 7 (The Honest Die) is the Computational Lab tier; the Diamond’s part (b) and problem 2.4 lean on its simulations.

Fluency

1.1 Compute the expected value of: one roll of a fair die; the sum of two dice; the larger of two dice (enumerate the 36 outcomes — no shortcut yet). Which of the three did linearity make trivial, and which made you work?

1.2 Hat-check with n = 3, by hand: list all 6 ways three hats can return, count the lucky people in each, and average. Confirm the theorem’s answer of 1, and note which single outcome did most of the lifting.

1.3 Run one quicksort partition by hand: list 5, 9, 2, 8, 1, 6 with pivot 6 (chosen by a generous coin). Show the left pile, right pile, the pivot’s final position, and the comparison count.

1.4 For randomized quicksort on n = 8 distinct items, compute P(ranks i, j compared) for the pairs (3, 4), (2, 5), and (1, 8). Which pair’s fate is certain, and why does the proof say so?

1.5 Birthday product, small: compute by hand the probability that 4 people all have different birthdays, and from it p(some pair shares). Keep four decimal places; the smallness is the point — and the Diamond explains how 0.016 becomes 0.507 by k = 23.

1.6 Verify by direct enumeration that randomized quicksort on 3 distinct items makes 8/3 expected comparisons: the first pivot is each rank with probability 1/3 — trace each case’s total and average. Then check 8/3 against the deep water’s exact formula 2(n+1)Hₙ − 4n at n = 3.

Practice

2.1 Expected rolls until a die first shows a six: call the answer E and notice that after one roll you have either finished (probability 1/6) or are exactly where you started (probability 5/6) — write the one-line equation this self-similarity implies and solve it. (Recursion’s ghost, haunting probability.)

2.2 A cereal brand packs one of 4 equally likely toys per box. Expected boxes to collect all 4? Decompose by linearity into four waiting times — already have c distinct toys, the next new one is a “six” on a die with what success probability? — and sum. Then simulate in the lab and compare.

2.3 Your school has 730 lockers and assigns them by hashing student names. With 300 students, estimate via the birthday lens: is a collision likely? Roughly how many students before collisions are expected (the √k scale)? And the design question: what must the locker system do about collisions that the no-collision fantasy ignores?

2.4 Sizing the gamble. You will store m = 1,000 keys and want the probability of any collision below ½ (a luxury — explain first why hash tables don’t actually need this). Using the Diamond’s inequality machinery in reverse, estimate how many buckets k you’d need, and compare k to m. Then the honest engineering question: with the standard k ≈ m instead, what is the expected number of collisions (linearity over pairs: m(m−1)/2 pairs, each colliding with probability 1/k), and why is that number livable?

2.5 The fixed-person birthday: how many people must be in the room before someone likely shares your birthday? Set up the product, show the answer is near 253, and write two sentences for a friend on why 23 and 253 answer different questions — naming the exact phrase in each question that changes the count of lottery tickets.

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