Answers

The answers to each chapter’s bank of exercises, chapter by chapter.

Contracts and cost models

The keys to the exercises, under the numbers the chapter gives them.

Exercises

Exercise 1

Heavier or lighter. Why does distinguishing \(2n\) possibilities change the bound, and how many weighings do twelve balls need?

• why: each of the \(n\) balls can be the odd one in two ways, heavier or lighter, so a strategy’s tree needs at least \(2n\) leaves, one per possibility. A weighing has three outcomes, so \(k\) weighings reach at most \(3^k\) leaves, and the bound becomes \(\lceil \log_3 (2n) \rceil\) weighings.
• twelve balls: three. Two weighings give at most \(3^2 = 9\) leaves, fewer than \(24\); three give \(27\).
• a strategy that does it in three: weigh 1–4 against 5–8.
  • They balance: the odd ball is among 9–12. Weigh 9, 10, 11 against 1, 2, 3 (known to be good). If that balances, 12 is the odd ball, and weighing it against 1 says heavier or lighter. If 9–11 go down, the odd ball is heavy among them: weigh 9 against 10, and the heavier one, or 11 if they balance, is it. If 9–11 go up, the same with lighter.
  • 1–4 go down (by symmetry the same when 5–8 go down): the odd ball is a heavy one of 1–4 or a light one of 5–8. Weigh 1, 2, 5 against 3, 6, 9. Left down: 1 or 2 is heavy, or 6 is light; weigh 1 against 2, and the heavier is it, or 6 if they balance. Right down: 3 is heavy or 5 is light; weigh 3 against 9: if 3 goes down it is heavy, and if they balance 5 is light. Balance: 4 is heavy, or 7 or 8 is light; weigh 7 against 8, and the lighter is it, or 4 if they balance.

Exercise 2

Close the gap. Prove the \(\Omega(n \log n)\) sorting bound cleanly from \(\log_2(n!)\), using Stirling’s approximation.

• the bound: a comparison sort is a tree with at least \(n!\) leaves, one per order of the input, and each comparison has two outcomes, so its worst case makes at least \(\log_2(n!)\) comparisons.
• Stirling: \(\ln(n!) = n \ln n - n + O(\log n)\), so \(\log_2(n!) = n \log_2 n - n \log_2 e + O(\log n)\), with \(\log_2 e \approx 1.443\). The leading term is \(n \log_2 n\), so \(\log_2(n!) = \Theta(n \log n)\), and every comparison sort makes \(\Omega(n \log n)\) comparisons in its worst case.
• a check without Stirling: the largest \(n/2\) factors of \(n!\) are each at least \(n/2\), so \(n! \ge (n/2)^{n/2}\) and \(\log_2(n!) \ge \tfrac{n}{2} \log_2 \tfrac{n}{2}\), which is already \(\Omega(n \log n)\).

Exercise 3

Which model makes it true? “Hashing is \(O(1)\)”, “appending to a growable array is \(O(1)\)”, “a binary search on disk is fast”.

• hashing is \(O(1)\): true as an expected cost, with a hash function that spreads keys at random, a table kept from filling up, and keys that fit in a word, so hashing one is one step. False in the worst case: keys that all land in one place make a lookup cost as much as the keys it holds. False too when a key is long, since computing its number reads all of it.
• appending is \(O(1)\): true amortized, over a run of appends (Exercise 5). False in the worst case for one append: the one that doubles the array copies everything.
• binary search on disk is fast: true when you count steps, about \(\log_2 n\) comparisons. False when you count block transfers, the model for a disk: nearly every probe lands in a different block, so it costs about \(\log_2 n\) slow trips, where a structure built for blocks (the search chapter’s B-tree) needs far fewer.

Exercise 4

How does it fail? For binary search, a hash table and the small yes-or-no summary, name the assumption and the failure mode. Which of the three fail silently, and how would you notice?

• binary search: assumes the list is sorted. Without it, it answers “not here” about a key that is there. Silent: nothing crashes. You notice by checking the order, or by catching a “not here” for a key you know is present.
• hash table: assumes the hash function spreads the keys. Without it, keys pile up in a few places and operations slow down toward a scan of everything. The answers stay right; only the cost fails, and silently. You notice by timing it, or by counting how many keys share a place.
• small yes-or-no summary: assumes it is not filled past the number of items it was sized for, and that whoever asks can live with a rare wrong “yes”. Its failure mode is a wrong “yes”: it may say “yes” when the true answer is “no”, silently, and its promise allows that. The promised rarity holds only within its size; filled past it, wrong yeses grow more frequent. You notice only by asking the full data behind it, and you measure how often it happens by doing that on keys you know are absent.
• which are silent: all three. None of them crashes or warns.

Exercise 5

Pay for the doubling. Show that \(n\) appends cost \(O(n)\) in total, so \(O(1)\) amortized per append, even though one append occasionally costs \(O(n)\).

• the count: each append writes one item, \(n\) writes in all. Copies happen only when the array is full and doubles, at sizes \(1, 2, 4, \ldots\) up to below \(n\), and together they copy \(1 + 2 + 4 + \cdots < 2n\) items in total. So \(n\) appends cost fewer than \(3n\) steps: \(O(n)\) in total, \(O(1)\) amortized per append.
• the expensive one: an append that finds the array full copies all \(k\) items it holds before writing, so that one costs \(O(k)\), up to \(O(n)\). The total stays small because each copy of \(k\) items comes only after the \(k/2\) cheap appends that filled the second half of the array.

Exercise 6

Find the wrong one that passes. Three specifications for “remove the smallest item from a collection”.

• wrong but meets (a): remove the largest item, or any item at all.
• wrong but meets (b): return the smallest item and remove nothing; or return a value smaller than everything, such as \(-\infty\), that was never in the collection.
• why (c) admits no wrong one: the returned item was in the collection and is no larger than anything left, so it is a smallest item; the collection afterwards holds exactly what it held, minus one copy of it, so exactly that one copy was removed. With ties, any copy of the smallest value is equally correct.
• the empty collection: (c) cannot be met, because there is no item to return. It must say what happens: for example, “on an empty collection, report that it is empty and change nothing”, or state that the collection must not be empty when remove_min is called.

Exercise 7

Drop the other half. Keep only “the output is a rearrangement of the input”. Name, in one line, a wrong sort the weakened specification now admits.

• a wrong sort it admits: return the input unchanged. It holds exactly the items it was given, and is not in order.

Search

The keys to the exercises, under the numbers the chapter gives them.

Run it and report the state

Exercise 1

Build a list that refuses duplicates by inserting 4, 9, 4, 2, 9, 7 one at a time, checking each key against the keys you have accepted so far, from the first, and stopping at a match. What does the list hold at the end, and how many key comparisons did the build cost?

• list: [4, 9, 2, 7]
• comparisons: 9

4 distinct keys on their own cost 4 × 3 / 2 = 6. The two duplicates add the other 3: a duplicate stops at the match rather than scanning the whole list, which is why it is not simply 6 × 5 / 2 = 15.

Exercise 2

Here is a sorted row of fifteen keys: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44. Binary search it for 14, and write down every key the search looks at, in order.

• probes: [23, 11, 17, 14]
• glances: 4
• outcome: found

Exercise 3

Here is a sorted row of fifteen keys: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44. Binary search it for 33, and write down every key the search looks at, in order.

• probes: [23, 35, 29, 32]
• glances: 4
• outcome: absent

Exercise 4

Insert 60, 30, 80, 20, 45, 70, 90, 40, 50, 42 into an empty binary search tree. How tall is it, counting nodes (a single node has height 1)? What are ceiling(55), rank(43) and select(6), counting from select(0) as the smallest key?

• height: 5. This book counts to the empty spot below the deepest node, so a single node is a tree of height one. A text that counts edges will say 4. Accept either, provided the reader says which they used.
• ceiling(55): 60
• rank(43): 4
• select(6): 60

43 is not in the tree, and rank still answers: the number of keys smaller than it.

Exercise 5

From the tree you built in Exercise 4, delete 30 by copying the successor’s key up into the node (Hibbard’s deletion, delete_hibbard in the companion library). Which key now sits where 30 was, and what hangs off it?

• key in that slot: 40
• its left: 20
• its right: 45
• where the successor’s own child went: 42, now the left child of 45
• inorder: [20, 40, 42, 45, 50, 60, 70, 80, 90]

the other deletion, moving the successor node itself (the library’s delete), leaves the same keys in the same shape, but built from different nodes: the node that held 40 now sits where 30 was.

Exercise 6

Insert 75, 51, 79, 9, 36, 72, 40, 71, 70, 66, 4, 69 into an empty left-leaning red-black tree. Which keys have a red link into them?

• red links into: [4, 51]
• root: 71
• height: 5. This book counts to the empty spot below the deepest node, so a single node is a tree of height one. A text that counts edges will say 4. Accept either, provided the reader says which they used.

Exercise 7

Starting from an empty left-leaning red-black tree, insert D, C, A, B, E, then F. After each insert, name every repair that fires (rotate left, rotate right, flip colors), in order, or say that none does. Letters compare in alphabetical order.

• D: ['none']
• C: ['none']
• A: ['rotate_right', 'flip_colors']
• B: ['rotate_left']
• E: ['rotate_left']
• F: ['flip_colors', 'rotate_left']

inserting F is the one to watch: the flip sends a red link up a level, where it leans right, so a rotate left fires one level higher. A repair can cause the next one up.

Exercise 8

Build the left-leaning red-black tree from 10, 20, 30, 40, 50, 60, then delete the smallest key twice in a row. Each time, say whether move_red_left fired, and at which node, and draw the tree afterwards.

• built: ((10 20* 30) 40 (50* 60 ·))
• delete 10: move_red_left at [20]; tree ((20* 30 ·) 40 (50* 60 ·))
• delete 20: no push; tree (30 40 (50* 60 ·))
• notation: (left key right), * marks a red link into the key

the first walk left the link into 20 red, so the second walk found a red link already waiting and had nothing to push.

Then: If the second deletion needed no push at all, explain what the first one left behind that made it unnecessary.

Exercise 9

Chapter 1 listed five things a left-leaning red-black tree holds true at once, before you had met the tree. Without scrolling back, write all five. Then, for each one, name the repair in this chapter that puts it back when an insert breaks it, or say that an insert never breaks it. Check your list against the box for the left-leaning tree (The design 2.2).

The keys are in order: an insert never breaks it, since the new key goes where a search for it ends and a rotation keeps the order. The top node is black: a color flip at the top can paint it red, so the insert ends by painting it black again. A red link leans left: rotate left. No node has two red links touching it: two chained below each other, rotate right, which leaves one on each side; one on each side, flip colors, which sends the red up a level. Every path crosses the same number of black links: an insert never breaks it, since the new key arrives on a red link and every rotation and flip keeps each path’s black count. If you missed one of the five, that is the one to reread in the chapter.

Exercise 10

Insert 17, 21, 8, 48, 27, 32, 11 into an empty B-tree of minimum degree t = 2, so each node holds at most 3 keys. What keys are in the leftmost leaf?

• leftmost leaf: [8, 11]
• root: [17, 27]
• height: 2. This book counts to the empty spot below the deepest node, so a single node is a tree of height one. A text that counts edges will say 1. Accept either, provided the reader says which they used.

Exercise 11

Build the B-tree at t = 2 from 17, 21, 8, 48, 27, 32, 11, 7, then delete 27 and then 48. Draw the tree after each. Each time, say which of the chapter’s moves the deletion used: replacing the key with its predecessor or successor, redistributing a key from a neighbor, or merging two nodes. Then say what decided the move each time: where the key sat, and what its children or neighbors held.

• built: ([17, 27], [[7, 8, 11], [21], [32, 48]])
• after deleting 27: ([17, 32], [[7, 8, 11], [21], [48]])
• after deleting 48: ([17], [[7, 8, 11], [21, 32]])
• moves: 27 sits in the root, so it cannot simply be removed: it is replaced by a neighbor in sorted order. Its left child is at the minimum and cannot give up the predecessor, so the successor 32 comes up from the right child, which had a key to spare; nothing is redistributed and nothing merges. 48 sits in a leaf at the minimum, so that leaf is topped up before the walk steps into it, and its only neighbor has nothing to spare either: the key between them comes down out of the parent and the two merge, then 48 is taken out. What decided it: the first key sat in an internal node, which needs a replacement, and a child could afford one; the second sat in a leaf, and no neighbor could afford anything.

Exercise 12

Give a B-tree room for three keys per node (minimum degree t = 2) and insert 1 through 20 in order. How many splits happen, how tall is the tree at the end, and how many nodes does a search for 17 fetch? Then count the same search in the plain binary search tree the same insertions build, and say the most any search can fetch in a perfectly balanced binary search tree of 20 keys.

• splits: 13
• height: 4. This book counts to the empty spot below the deepest node, so a single node is a tree of height one. A text that counts edges will say 3. Accept either, provided the reader says which they used.
• root: [8]
• search for 17 fetches: 4
• plain binary search tree: 17
• perfectly balanced, at most: 5

Exercise 13

Keep the chapter’s list of where things are, allowing yourself three entries before a trip. In this order: the keys go in the hall bowl, the tickets in the desk drawer, then the keys move to your coat pocket, and the spare charger goes in the car; then the tickets move to your wallet, the spare charger is thrown away, the passport goes on the top shelf, and the umbrella goes by the door. Write out both sealed pages and the list exactly as they end up. Then answer “where are the keys?”, “where is the umbrella?” and “where is the flashlight?”, counting how many pages each question touched.

• Page 1: keys: coat pocket, spare charger: car, tickets: desk drawer
• Page 2: passport: top shelf, spare charger: gone, tickets: wallet
• the list: umbrella: by the door
• keys: coat pocket, 2 pages
• umbrella: by the door, 0 pages
• flashlight: nowhere, 2 pages

the keys changed place before the first trip, while the list was still unsealed, so the list line was simply corrected: Page 1 holds one entry for them, not two. Only a sealed page is never changed.

Then: The keys changed place before the first trip. Does Page 1 hold one entry for them or two, and why is that allowed when a page is never changed? Then say which of the three questions a Bloom filter on each page would have made cheaper, and by how many pages.

Answer to the follow-up: One entry. Before the trip the list is not sealed, so a change corrects its line; only sealed pages are never touched. With a filter on each page, the flashlight drops from two pages to none, and the keys from two to one: Page 2’s filter says they are not there, so only Page 1 is read. Each barring a false positive. The umbrella question never reached a page, so it gains nothing.

Which promise broke

Exercise 14

The model returns the reference tree with this changed: exchange the keys 70 and 72, touching no link and no color.

• promises now false: the keys are in order

Exercise 15

A different tree, built from 20, 10, 30: paint the top node (20) red.

• promises now false: the top node is black

Exercise 16

On the reference tree, apply rotate_right at the root (71), exactly as the repair code does.

• promises now false: a red link always leans left

Exercise 17

A tree of three nodes: a black link into 30, a red link into 20 as 30’s left child, and a red link into 10 as 20’s left child.

• promises now false: no node has two red links touching it, not one on each side, and not one chained below the other

Exercise 18

On the reference tree, repaint the link into 51 from red to black.

• promises now false: every path crosses the same number of black links

Exercise 19

The same twelve keys, inserted in this order instead: 4, 79, 69, 71, 51, 9, 40, 75, 70, 72, 36, 66.

• promises now false: none. This tree is valid, and saying so is the answer.

Exercise 20

On the reference tree, repaint the link into 69 from black to red.

• promises now false: a red link always leans left; no node has two red links touching it, not one on each side, and not one chained below the other; every path crosses the same number of black links

Why this exercise exists, and why the trees before it took four different kinds of edit: the promises are not independent. Of the twelve single-link repaints on this tree, only 4 break exactly one promise, and every one of those breaks black height.

• breaks 1: every path crosses the same number of black links by repainting 51 (red→black), 4 (red→black), 66 (black→red), 72 (black→red)
• breaks 2: a red link always leans left; every path crosses the same number of black links by repainting 40 (black→red), 70 (black→red), 79 (black→red)
• breaks 2: no node has two red links touching it, not one on each side, and not one chained below the other; every path crosses the same number of black links by repainting 36 (black→red), 9 (black→red)
• breaks 2: the top node is black; no node has two red links touching it, not one on each side, and not one chained below the other by repainting 71 (black→red)
• breaks 3: a red link always leans left; no node has two red links touching it, not one on each side, and not one chained below the other; every path crosses the same number of black links by repainting 69 (black→red), 75 (black→red)

Repainting 75 creates no chain of reds, yet it breaks the two-red promise: 71’s link to 51 is already red, so 71 gets a red link on each side.

Then: Count how many promises that one repaint took down, then say whether the count means the promises are badly chosen, or something else.

Answer to the follow-up: 3. The promises are not badly chosen: they are not independent. One link’s color takes part in several of them at once (which way reds lean, whether two reds touch, how many black links a path crosses), so a single repaint can break several. Five separate promises are still the right way to state them, because each can also fail alone, as the other items show.

You supply the input

Exercise 21

Make a plain binary search tree on the keys 1 to 8 as tall as it can possibly be. Give the insertion order. Then find a second order that reaches the same height but does not look sorted, and say what all such orders have in common.

order	height	verdict
[4, 2, 6, 1, 3, 5, 7, 8] (a student who balanced it)	4	reject
[1, 2, 3, 4, 5, 6, 7, 8] (sorted)	8	accept
[8, 7, 6, 5, 4, 3, 2, 1] (reverse sorted)	8	accept
[1, 8, 2, 7, 3, 6, 4, 5] (zig-zag)	8	accept

The zig-zag is the one worth discussing: it looks like the least orderly of the four and reaches the same height as sorted. What matters is that every key is the smallest or the largest of the keys not yet inserted; how disordered the order looks makes no difference.

Then: How many of the 8! possible orders of the eight keys reach that height? Guess first, then count.

Answer to the follow-up: 128, which is 2 to the 7th: every key but the last must be the smallest or the largest of those still to come, a choice of two at each of seven steps. Checked by building all 40,320 orders.

Exercise 22

Now do the same to the left-leaning red-black tree: find an insertion order of 1 to 8 that makes it 8 tall, or as tall as you can. Predict what will happen before you run anything, and write the prediction down.

order	height	valid
[1, 2, 3, 4, 5, 6, 7, 8] (sorted)	4	True
[8, 7, 6, 5, 4, 3, 2, 1] (reverse sorted)	4	True
[1, 8, 2, 7, 3, 6, 4, 5] (zig-zag)	4	True

No order reaches 8. That refusal is the whole purchase: the repair on every insert bought the property that the adversary’s choice of order stops mattering.

Then: State what you found as a sentence about insertion orders rather than about trees.

Answer to the follow-up: Every one of the 40,320 orders of 1 to 8 gives height exactly 4, which is also the least any tree on 8 keys can have: the order the keys arrive in stopped being something anyone can use against the tree.

Exercise 23

Falsify this (find a case that shows it is false): two people who insert the same fifteen keys into a B-tree at minimum degree t = 2, in different orders, end up with the same tree. Then measure the height of every tree you built while falsifying it.

False. Over 202 insertion orders of 1 to 15 the root came out 17 different ways:

• sorted: [1, 2, 3, 4, 5, 6]... → root [4, 8]
• reverse: [15, 14, 13, 12, 11, 10]... → root [8, 12]
• random: [13, 11, 7, 12, 15, 1]... → root [11]

And the part worth more than the falsification: every one of those orders gave the same height. The set of heights observed is [3]. The guarantee held while the shape moved. What a caller may depend on is the height staying within its logarithmic bound; the shape is not promised, and is not a bug. That every order here gave the same height is a fact about fifteen keys, not the promise itself. The same point closes the appendix’s derivation exercise, where it costs two hours rather than a minute.

Then: Of the two things you checked, the tree’s shape and its height, say which a caller is entitled to depend on, which is not, and why the second is not a bug.

Exercise 24

Falsify this: binary search makes a sorted array beat the tree at everything, so the trees were never needed. Your answer has to name an operation and count something, not name a structure.

• claim: a sorted array with binary search dominates the tree
• counter-workload (one acceptable answer; the reader picks their own): 1000 keys already in place, then 100 inserts arriving in uniformly random positions
• key moves the array pays, expected: 52475
• key moves the array pays, one simulated run: 50927
• key moves the tree pays: 0
• note: lookups really are comparable, so the falsification has to name the operation rather than the structure. Accept any answer near the expected figure: the point is the order of magnitude against zero, not the third digit. A reader who answers 50000 has used 1000/2 for every insert and missed that the array grows as it absorbs them.

Then: State the workload under which the claim is actually true.

Answer to the follow-up: A static or read-only set: nothing is inserted or deleted after the array is built, so no insert ever shoves, and the array’s lookups are as fast as the tree’s with less space and better locality.

Which idea do you reach for

Exercise 25

A messaging service keeps, for every conversation, the messages in time order. Reads ask for the newest few. Writes arrive in bursts, far faster than reads, and a message is never edited once sent. Which idea do you reach for first?

• (a) slack in the levels below

• → (b) keep it in layers

• (c) work in blocks

• (d) fingerprinting

Answer: (b) Never write in place: seal each batch, reconcile at read time. You buy the write path and pay read amplification and compaction.

Then: Name the failure mode you just bought, in this chapter’s terms.

Answer to the follow-up: Either of the chapter’s two. From the choosing table: a deleted message comes back with its old value, or an accepted write is gone after a crash, and no error says so. From the box’s Assumes line: a burst that outruns the merging piles up unmerged batches until new writes have to wait. What you pay even when nothing breaks is a cost, not a failure mode: read amplification, since a read may consult several layers.

Exercise 26

A read-only dataset of 40 million records ships once a month on a disk image and is loaded into memory on arrival. Every query is a lookup by id, or asks for all records whose ids fall between two bounds. Nothing is ever inserted between shipments. Which idea do you reach for first?

• (a) slack in the levels below

• (b) keep it in layers

• → (c) divide and conquer

• (d) pay in installments

Answer: (c) Nothing changes, so the one cost a sorted array cannot pay, moving keys on insert, is never charged. Slack would be paid for nothing.

Then: What single change to this workload would make your answer wrong?

Answer to the follow-up: Inserts between shipments. Each one would shove keys along the array, and the cost the array never had to pay becomes the dominant one; slack in the levels below, or layers if the inserts come fast, is then the answer. Also right: data that outgrows memory, so every probe becomes a fetch and work in blocks wins.

Exercise 27

A service must answer “have we seen this id before?” for a stream of billions of ids, in memory that holds only a small fraction of them, where a wrong “yes” costs one wasted lookup and a wrong “no” corrupts the records. Which idea do you reach for?

• → (a) fingerprinting

• (b) work in blocks

• (c) keep an invariant

• (d) randomization

Answer: (a) One-sided error is the whole point: it may say maybe-present when the key is absent, never absent when it is present.

Then: Errors here have two directions. Say what your choice does to each of them, and why that matches this workload.

Answer to the follow-up: A wrong yes (the filter says maybe, the id is new) happens now and then and costs the one wasted lookup the workload can afford. A wrong no never happens, and that is the error that would corrupt the records.

Exercise 28

An index is a plain binary search tree, and its keys are ids chosen by whoever is calling. One caller has worked out that a particular arrival order makes every lookup slow. You cannot change the tree’s code, because it is a library you depend on. You can change only the order in which keys are handed to it: the index is rebuilt from scratch every night from the full list of ids, and you may reorder that list before passing it on. Which idea do you reach for?

• (a) slack in the levels below

• (b) divide and conquer

• → (c) randomization

• (d) work in blocks

Answer: (c) Slack in the levels below is the better fix and is ruled out by the stem: it means replacing the structure. With only the arrival order under your control, you take the choice away from the caller, which turns a worst case they can aim at into one nobody can.

Then: Compare the guarantee you just bought against a balanced tree’s, in one sentence.

Answer to the follow-up: A balanced tree is logarithmic on every order, guaranteed; the shuffle makes it logarithmic in expectation, with a small chance of a bad tree that no caller can aim at. It holds only because you shuffle the whole list: if keys arrived in batches you could only reorder one at a time, the caller could still aim across batches, and only the balanced tree would stop that.

Exercise 29

A sorted array is the right structure for a read-heavy index, but a few hundred inserts a day do arrive, and each one shoves a large part of the array along, stalling the service for a visible moment. The total work is affordable; it is the spikes that are not. Which idea do you reach for?

• (a) pay in installments

• (b) divide and conquer

• → (c) spread the work out

• (d) keep an invariant

Answer: (c) Collect the inserts to one side and merge them into the array a small piece at a time, a few steps per operation. Paying in installments is the tempting answer and the wrong one: it says the day’s total is affordable, which the question already grants, and promises nothing about the one insert that stalls. Doing the work in small pieces is what takes the spike away. The total cost is unchanged and may even rise slightly; what changes is that no single operation carries it.

Then: Name a workload where this is the wrong trade, and say what about that workload makes it wrong.

Answer to the follow-up: An insert-heavy one. Spreading the work out spreads a cost without shrinking it, so once inserts are frequent the total shoving is no longer affordable however it is spread; the structure itself has to change, to slack in the levels below. Also right: a workload where nobody waits on a single insert, such as an overnight rebuild, where spreading the work out only adds bookkeeping.

Exercise 30

An in-memory red-black tree holds a hundred million keys. A profiler says lookups spend nearly all their time waiting on memory rather than comparing: almost every node visited is a cache miss, and each miss brings in a whole cache line, typically 64 bytes, of which the node uses a fraction. Nothing moved off the machine. Which idea do you reach for?

• (a) divide and conquer

• → (b) work in blocks

• (c) randomization

• (d) keep an invariant

Answer: (b) The comparison stopped being the unit of cost; reaching a node started being it, even inside one machine. Widen the node until it fills a cache line, and the same log₂ n halvings cost far fewer misses: the B-tree’s idea, at a block of 64 bytes instead of a disk page.

Then: Name the block here, and say why a disk or a network round trip would have led you to the same idea.

Answer to the follow-up: The block is the 64-byte cache line. A disk page and a network round trip have the same shape at a larger block: reaching a node costs far more than comparing inside it, so the node is widened to fill whatever one fetch brings back.

Exercise 31

An in-memory index must support lookup, ordered iteration, and range queries, with reads and writes in about equal numbers. The keys are timestamps from thousands of sensors whose readings arrive late: each sensor’s keys come in increasing order, but a new key can land anywhere in the range already stored. You control the structure entirely. Which idea do you reach for?

• (a) divide and conquer

• (b) keep it in layers

• → (c) slack in the levels below

• (d) fingerprinting

Answer: (c) A new key can land anywhere, so a sorted array shoves on every insert, and each sensor’s increasing run is exactly the order that degrades a plain tree to a list. Room below every node absorbs an arrival wherever it lands, and a balanced tree keeps the height logarithmic whatever the order.

Then: Say why each of the three wrong answers fails here.

Answer to the follow-up: Divide and conquer over a sorted array: arrivals land anywhere, so every insert shoves. Keep it in layers: it makes writes cheap by making reads consult several levels, and writes are not the dominant cost here. Fingerprinting: it answers membership only and throws the order away, so no iteration and no ranges.

Exercise 32

You add a subtree-size field to every node so the tree can answer rank and select. Insert maintains it. A colleague now adds a delete, and a bulk-load path that builds nodes directly. What makes the field safe to read?

• → (a) keep an invariant

• (b) pay in installments

• (c) work in blocks

• (d) randomization

Answer: (a) A derived field is only as good as the weakest operation that touches a node. Every path that builds or rewrites a node has to restore it, or the field stops being a fact about the tree and becomes a fact about which code ran last.

Then: This is the same risk the broken trees in Exercises 14 to 20 showed: a promise that holds only until a new code path touches the nodes. Say why.

Answer to the follow-up: In those exercises a refactored insert path broke a promise the old insert kept; here delete and bulk-load break one insert keeps, because nobody taught them it. Either way a promise holds only while every path that writes a node restores it.

Exercise 33

A nightly batch job appends a hundred million log events to a growable array that doubles its capacity whenever it is full. The job is judged only on when the whole run finishes; nobody waits on any single append. A reviewer objects that some appends copy the entire array. Which idea says the objection does not matter here?

• → (a) pay in installments

• (b) spread the work out

• (c) work in blocks

• (d) slack in the levels below

Answer: (a) Because the capacity doubles, all the copies together cost at most about twice the number of appends, so the run stays linear: each rare expensive append is paid for by the many cheap ones before it. Nobody waits on a single append, so a promise about the total is exactly the one needed. Spreading the copy out would add work and code to protect a latency nobody sees.

Then: Change one thing about the workload that would make (b) the right answer instead.

Answer to the follow-up: Put a caller with a deadline behind every append, say a live service logging each request as it happens. Then the one append that copies the whole array is a missed deadline, and the copy has to be done a few elements at a time.

The tests pass. What did they miss?

Exercise 34

A colleague’s key-value store is an LSM-tree: writes go into a memtable, a full memtable is flushed to a sorted file that is never edited again, deletes write tombstones, reads go newest first, and compaction merges files in the background. Three tests guard it, and all three pass: after any random sequence of writes and deletes, every read agrees with a plain dictionary given the same sequence; the same holds after every compaction; and every file on disk is sorted and unchanged once written. In its first week the machine loses power. The store restarts cleanly and every file is intact, but the last few hundred writes the service had confirmed to its callers are gone. Name the requirement the tests never stated, and write it as one sentence a test could check.

Answer: Every write the store has confirmed to a caller must still be readable after the machine loses power and restarts, at any moment. All three tests ran inside one living process, so the memtable, which is memory and does not survive a power cut, never had to survive anything. The requirement is about confirmation, not about files: the files were intact, and correct for everything they held.

Then: Describe the test that would have failed, then say what the store must do to pass it and what that costs on every write.

Answer to the follow-up: The test: run a random sequence of writes and cut the power at a random point, or imitate the cut by stopping the process without warning and throwing away every write the device had not yet confirmed as landed; restart, and check that every write confirmed before the cut reads back. To pass, append each write to a write-ahead log and wait for the device to confirm it landed before confirming the write to the caller; replay the log into the memtable on restart; discard a log segment only once its memtable is flushed. The cost is the wait for the device on every confirmed write, which is why real systems group many writes into one confirmation and pay it once per group.

Fill in the contract

Exercise 35

A weather network has thousands of stations, and together they send tens of thousands of readings a second, all day. Each reading must be confirmed to its station within ten milliseconds, every time, even in the busiest minute of the year, and a confirmed reading must never be lost, even in a power cut. Reads are rare: a weekly report per station, and now and then a look at one station over one afternoon, and nobody minds if that takes a few seconds. Work out the parts of a contract for this workload, in the order the contracts chapter works them out, one or two sentences each, and name the assumptions these promises need.

Answer, one line per question. Grade on the promises kept apart, not on the wording:

1. Goal: take tens of thousands of small writes a second, confirm each one within ten milliseconds, and never lose a confirmed reading; the rare reads ask for one station over a time range.
2. Scarce resource: time on each write’s path, because every confirmation has a deadline, and the slow part is waiting for the disk.
3. Floor: a reading cannot be confirmed before it has reached the disk, so each confirmation waits for at least one disk write, which many readings can share.
4. Promise: every confirmed reading can be read back afterwards, power cut or not, and a query returns exactly the confirmed readings for that station and time range. What must remain true: every confirmed reading is on disk, in the log or in a flushed file.
5. Ideas: keep it in layers and pay in installments, so writes land in memory and the sorting and merging is charged to many writes; spread the work out, so the merging runs in the background and no write waits for it; and a write-ahead log, appended before each confirmation, so a power cut loses nothing confirmed.
6. Cost and what it refuses: a write costs one in-memory insert, its share of one log append and of the wait for the device to confirm it, and its share of the merges that rewrite it several times on its way down; a read may look in several files and is slow.
7. Assumes: arrivals, bursts included, stay within a bound low enough that a reading’s whole wait fits in ten milliseconds: waiting in line, waiting for its group of writes to fill, being processed, and the device confirming that the log append landed; background merging keeps up with that workload; and a write the device has confirmed survives a power cut. If merging falls behind, unmerged batches pile up until writes wait, and the deadline breaks. Reconsider when reads become frequent or must be fast (a B-tree, or Bloom filters and more merging), or when arrivals outrun merging for long stretches (split the stations across machines).

Then: This workload makes three separate promises. Name them, name the idea that keeps each one, and say which of the three costs something on every single write.

Answer to the follow-up: A cheap total: pay in installments. No long wait on any one write: spread the work out, since installments promise an average and say nothing about the write that triggers a merge. Confirmed means kept: the write-ahead log. The log is the one that costs something on every write, the wait for the disk, which is why many readings share one append. An answer that covers all three with paying in installments has kept only the first.

Fix the code, the box, or the design?

Exercise 36

An AI writes an LSM-tree from its design box. Its memtable holds two entries, every flush is merged straight into the first level, and each level may hold twice as many as the one above. Its compaction drops every tombstone it meets, in every merge. Write a to f with the values 1 to 6, then delete a and write g. A read of a returns 1. Every batch on disk is sorted and never changed, and every level is within its budget: the store’s validity check passes. Which of the three is it, and why?

Answer: fix the code. The box promises that a read gets nothing once the newest write was a delete. This read returns 1, so the code breaks the promise. The tombstone was dropped in a merge while an older batch further down still held a, and the read found that batch. A tombstone may go only in a merge with nothing older beneath it.

Then: Write a test you would keep from the AI that fails on this code, and say why checking the invariants could not catch it.

Answer to the follow-up: Run random writes and deletes on the store and on a plain dictionary, with a memtable small enough that merges reach the third level, and compare every read, deleted keys above all. The invariants are about the batches’ shape, sorted and within budget, and this bug leaves the shape right and the contents wrong, so only the promise sees it. You may also add the tombstone rule to the box as an invariant, so a check can catch it; the repair is still in the code.

Exercise 37

An AI writes a left-leaning red-black tree from its design box, as an index of 100,000 product numbers kept on disk, each node in its own block. Every check of the tree passes, and every lookup is right. But a lookup reads 16 blocks on average and up to 22, and one read from the disk costs far more than all the comparisons. A colleague says the tree must be out of balance. Which of the three is it, and why?

Answer: change the design. The tree keeps its promise and its cost: 22 is well under twice log₂ of 100,000, about 33, so it is balanced. What fails is the line Assumes: reaching any node costs about the same, as in the RAM model. On disk, reaching a node is a block read, and a node with one key uses one key of the block it costs. The B-tree fills the block with one wide node: at t = 64, the same numbers take up to 3 block reads per lookup.

Then: Rewrite the lines of the box that no longer fit the job, and say what you would measure to check the new design.

Answer to the follow-up: Goal: a search tree for memory that hands over whole blocks, each fetch costing far more than looking inside it, which is the B-tree’s goal. Idea: work in blocks, so one block read buys a whole node, as many keys as fill the block. Cost: \(\Theta(\log_t n)\) block reads per lookup in the worst case, up to 3 here at t = 64, with one node per block and nothing cached; a key found in the root costs one. Assumes: one node fills one block. Measure block reads per lookup, not comparisons, and keep the old lookup tests, since the promise has not changed.

Derive it

Exercise 38

The appendix states the standard tree’s five invariants and stops. It does not give you its repair procedure. Derive it. Then say what the analogy was: which object mapped to which, and which move to which.

Given to the reader: the 2-3 tree behind LLRB, and why LLRB’s three moves are what they are; the appendix’s encoding: a black node with its red children is one node of a 2-3-4 tree (black alone = 1 key, +1 red = 2 keys, +2 reds = 3 keys); the B-tree section, where you traced splits at minimum degree t = 2

The routes

A. through the encoding — Translate the red-black tree into its 2-3-4 tree. Ask what a 2-3-4 tree does when a key lands in a node that is already full. Translate the answer back.

B. by moving LLRB’s trigger — LLRB and the standard tree run the same moves. LLRB refuses to hold a 4-node, so it splits the moment a node would hold three keys. The standard tree allows 4-nodes, so it splits one key later. Same moves, trigger moved by one.

C. through the B-tree you already traced — A B-tree of minimum degree t = 2 holds one to three keys per node. That is a 2-3-4 tree. You built one in the B-tree section and were not told what it was called. It splits on the way down, though, and the standard repair splits on the way back up: follow the B-tree’s timing and you reach a valid relative of the standard repair, not the repair itself. Move the split to after the key lands and the routes agree.

The three self-checks

Predict, before running anything: which is more common on random keys, the split (the key lands in a full node) or the absorb (the node has room)? By roughly what ratio? Then measure it.

The absorb, about two to one. Measured over 11,700 inserts into standard red-black trees on random keys: 33.2% land in a node that is already full and split it, 66.8% land in a node with room. A reader who predicted ‘splitting is rare’ is closer than one who predicted a coin flip, and the reason is that there are simply more non-full nodes than full ones at any moment.

Check your procedure against a real one. The companion library ships a standard red-black tree, built to the textbook rules rather than this chapter’s: algodesign.searching.RBTree, in red_black_standard.py. This is the oracle, the reference you check against. First, after every insertion, check that your tree holds exactly the keys inserted and keeps the five invariants. Then run its repair over the same keys and compare the trees node by node. A mismatch may be a bug, or a different, also valid, repair procedure for the same rules: say which yours is, and why. Splitting full nodes on the way down, as this chapter’s B-tree does, is one such procedure. The next check is about exactly that.

A derivation of the standard repair agrees with it node by node. Two checks settle the derivation, in this order. First, after every insert your tree holds exactly the keys inserted and keeps the five invariants: that says your procedure is correct. Then compare node by node with RBTree: agreement says it is the standard repair, not just a valid one. A mismatch with the keys and invariants intact is not a bug: the standard rules allow a 3-node to be drawn with its red child on either side, so a repair can choose differently and stay valid. A procedure that splits on the way down disagrees with it on some sequences and is still a valid relative, not the standard repair; the third check shows where.

Now a comparison that does not come out equal. Build the same keys as a B-tree at t = 2, and group your red-black tree into its 2-3-4 nodes. Both are 2-3-4 trees on the same keys. They are often different 2-3-4 trees, though never on eight keys or fewer. Find the smallest key sequence where they differ, say what is still true of both, and explain the difference. It comes down to one line in the two procedures.

Nine keys, and 1 to 9 in order is one of them. Exhaustive over every permutation of 1..8 – all 40,320 – the two agree; the first disagreement appears at nine. There, the B-tree gives (1)(2)(3)(4)(5)(6)(7 8 9) and the red-black grouping gives (1)(2 4 6)(3)(5)(7 8 9).

What stays true of both: same keys, every node holding one to three keys, every leaf at the same depth. Both are valid 2-3-4 trees.

The difference is WHEN each one splits. The chapter’s B-tree splits a full node on the way DOWN, before descending through it, so a node is never full when a key arrives beneath it. The red-black repair runs on the way back UP, splitting only once the key has landed. Same rule, opposite side of the descent, and the answer to the exercise’s second question counts top-down splitting as a procedure for the same rules, not a new set. Over 3,000 random 12-key orders the two disagree 48% of the time, so a reader who finds them differing has found the truth, not a bug.

The mapping the answer has to make explicit

2-3-4 tree	standard red-black tree
2-3-4 tree	standard red-black tree	you already know it as
a node holding 1 key	black node, no red children	a 2-node
a node holding 2 keys	black node, one red child	a 3-node
a node holding 3 keys	black node, two red children	a 4-node, full
node is not full, absorb the key	parent is black: no repair fires at all	the easy case
node is full, split it: middle key rises, halves become separate nodes	uncle is RED: recolor parent and uncle black, grandparent red, continue from the grandparent	the split, and the rise is why the walk continues upward
node is not full, but the binary drawing of it is illegal	uncle is BLACK: rotate, once or twice, to reach the legal drawing	no split: only the encoding needs fixing
the root splits	the root is forced black at the end	the one place the tree gets taller

Punchline. ‘Uncle is red’ is not a rule about uncles. It is how a binary tree says ‘the node I am inserting into is already full’.

Q1 (How many distinct routes reach this derivation? Find as many as you can, say what each one takes as given, and show they agree.) At least three, above. They are not rephrasings: A starts from the abstract structure, B starts from an algorithm you already have and moves one trigger, C starts from a tree you already drew. A student who finds only one has not finished.

Q2 (Harder. Every structure in this family keeps the same headline promise: the height stays within a constant factor of log₂ n, so search, insert and delete are all logarithmic. How many different sets of rules keep it? Not: how many ways to derive one set. How many sets are there, and what separates them?) Infinitely many. Two you have met are red-black rule sets: the left-leaning tree this chapter builds, and the standard either-leaning tree. Splitting full nodes on the way down is a different procedure for the standard tree’s rules, not a new set. Andersson’s AA tree stores a level number in place of a color, but its rules are the left-leaning tree’s rules mirrored, so it is the same point seen in a mirror. Reflecting any of these left-for-right gives a mirror image, which is the same structure rather than a new member – a reader who counts it separately has counted one point twice. Beyond these the count never stops: allowing the two sides of every node to differ in height by up to k, for any fixed whole number k ≥ 1, keeps the height within a constant factor of log₂ n, a constant that grows with k.

A reader who answers AVL is right, and the answer is better than the question deserved: AVL keeps the same headline promise with a tighter height bound, by a different mechanism, and it is already in this chapter’s own table of primitives. Take that answer.

What separates the family is not correctness. It is how many distinct broken shapes a repair must recognize, against how tight the height bound comes out, against how much work per operation is bounded. Each rule set exposes a different trade-off among those three; sharing the logarithmic bound does not settle which one is better on any of them.

Check: Build the same keys as a left-leaning tree and as a standard tree. Compare the shapes, and compare both against the height bound. Over four seeds of 400 random 63-key trials the shapes differ every single time, and both stay under 2·log₂(n+1) = 12.00 in every trial. The left-leaning tree is taller on average by about half a level – mean +0.42 to +0.57 across the four seeds – and the distinction worth keeping is that this is an average, not a rule: the two come out the same height about four times in ten, and the left-leaning tree is the shorter one about one time in twenty. The rules are not the guarantee. They are one way of keeping it.

Strings

The keys to the exercises, under the numbers the chapter gives them.

Run it and report the state

Exercise 1

Slide the pattern aab along the text aabaacaabaab by hand, comparing character by character and moving on at the first mismatch. Where does it occur, and how many character comparisons did the whole scan make?

• occurrences: [0, 6, 9]
• comparisons: 21

Exercise 2

The text is the digits 6404137153929 and the pattern is 153, base 10, modulus 13. Write down the fingerprint of every window of three digits, rolling each from the one before. At which positions do the fingerprints agree with the pattern’s, and which of those are false alarms?

• pattern fingerprint: 10
• window fingerprints: [3, 1, 2, 10, 7, 7, 0, 10, 6, 2, 6]
• found: [7]
• false alarms: [3]

Exercise 3

Insert tea, ten, to, inn, in, tent into an empty trie, in that order. How many nodes does it have, root included? How many after squeezing it into a Patricia tree? What does keys_with_prefix("te") return, in order?

• trie nodes: 10
• Patricia nodes: 9
• keys_with_prefix(te): ['tea', 'ten', 'tent']

Exercise 4

Insert romane, romanus, romulus, rubens, ruber into an empty Patricia tree and draw it, every branch labelled. Then insert rubicon. Which branch is cut, and where? How many nodes does the tree have before and after?

• before:

  r
    om
      an
        e (word)
        us (word)
      ulus (word)
    ube
      ns (word)
      r (word)

• nodes before: 10

• after:

  r
    om
      an
        e (word)
        us (word)
      ulus (word)
    ub
      e
        ns (word)
        r (word)
      icon (word)

• nodes after: 12

Exercise 5

Write the suffix array of abracadabra$, with $ sorting before every letter. Which rows hold the suffixes that begin with abra, and which text positions are they?

• suffix array: [11, 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]
• rows: [2, 3]
• positions, in row order: [7, 0]

Exercise 6

From the suffix array of abracadabra$ (the previous exercise), write its LCP array. What is the longest passage that occurs twice, and which entry tells you? Then fill it in Kasai’s way: visit the positions in text order, 0 to 11, carrying h. For each position, what does h start at, and what does it record?

• LCP array: [0, 0, 1, 4, 1, 1, 0, 3, 0, 0, 0, 2]
• longest repeat: abra
• largest entry, at row: 3
• h per position:
  • 0: starts at 0, records 4
  • 1: starts at 3, records 3
  • 2: starts at 2, records 2
  • 3: starts at 1, records 1
  • 4: starts at 0, records 0
  • 5: starts at 0, records 1
  • 6: starts at 0, records 0
  • 7: starts at 0, records 1
  • 8: starts at 0, records 0
  • 9: starts at 0, records 0
  • 10: starts at 0, records 0
  • 11: starts at 0, row 0: nothing to compare

Exercise 7

Sort the suffixes of aababa$ by prefix doubling. Give the tag of every position after each round, with tags starting at 1 and $ tagged lowest, until every tag is different. How many doubling rounds did it take, not counting round 0, the tagging by single letters?

• tags after round 0: [2, 2, 3, 2, 3, 2, 1]
• tags after round 1: [3, 4, 5, 4, 5, 2, 1]
• tags after round 2: [3, 5, 7, 4, 6, 2, 1]
• doubling rounds: 2
• suffix array: [6, 5, 0, 3, 1, 4, 2]

Exercise 8

Write the Burrows–Wheeler transform of abracadabra$: sort its rotations and read the last column. Where are the runs of equal letters?

• last column: ard$rcaaaabb
• first column: $aaaaabbcdrr
• runs: aaaa in rows 6–9; bb in rows 10–11

Exercise 9

A last column reads omotta$. Recover the text with the LF walk: sort the column to get F, number equal letters, start from the row whose last letter is $, and follow LF. Give the LF value of every row, and the text.

• LF by row: [3, 2, 4, 5, 6, 1, 0]
• text: tomato$

Exercise 10

Using only the last column of abracadabra$ (Exercise 8) and its table C, run backward search for bra. Give the interval of rows after each letter, and the count.

• C: {'$': 0, 'a': 1, 'b': 6, 'c': 8, 'd': 9, 'r': 10}
• intervals: ['a: [1, 6)', 'ra: [10, 12)', 'bra: [6, 8)']
• count: 2

Exercise 11

For the bits 0110100111000101 (position 0 first), what are rank(5), rank(11) and rank(16), the number of 1s before each position, and select(0), select(4) and select(7), counting the 1s from zero?

• rank(5), rank(11), rank(16): [3, 6, 8]
• select(0), select(4), select(7): [1, 8, 15]

Exercise 12

The FM-index of abracadabra$ keeps a sample at every 4th text position (0, 4 and 8). Find every row whose suffix begins with a, and turn each into its text position by walking LF to a sampled row. How many steps does the longest walk take?

• rows: [1, 6)
• position and steps per row:
  • 1: 10 after 2
  • 2: 7 after 3
  • 3: 0 after 0
  • 4: 3 after 3
  • 5: 5 after 1
• longest walk: 3

Exercise 13

The FM-index of abracadabra$ keeps the row of every 4th text position (0, 4 and 8). Extract the 3 letters starting at position 5, then the 2 letters starting at position 9. For each: which row do you start from, how many LF steps do you walk, and what comes out?

• 3 letters from 5: start from the row of position 8, 3 LF steps, ‘ada’
• 2 letters from 9: start from the row of position 0, 3 LF steps, ‘ra’

Exercise 14

Three quotes are joined into one text with a separator between them: frankly my dear, here is looking at you, may the force be with you. The fragment looking is found at one position. Which position, which quote does it fall in, numbered from 0, and which bounds do the two selects give? Then: which quotes does a search for you return?

• hit: 24
• quote number: 1
• bounds: (16, 39)
• find(you): [1, 2]

Which promise broke

Exercise 15

The suffix array of cocoa$ is 5 4 0 2 3 1.

• verdict: broken: the rows are not in sorted order
• detail: rows 2 and 3 are swapped: cocoa$ sorts after coa$; the array is [5, 4, 2, 0, 3, 1]

Exercise 16

The suffix array of pepper$ is 6 1 4 0 3 2 5.

• verdict: correct
• suffix array: [6, 1, 4, 0, 3, 2, 5]

Exercise 17

A last column reads ap$p$le, and is said to be the transform of some text.

• verdict: broken: it holds two$, and a transform holds exactly one
• detail: the walk would not know which row is the whole text, and the library refuses it

Exercise 18

The LCP array of cocoa$ is 0 0 0 3 0 1.

• verdict: broken: row 3 claims 3 shared letters
• detail: its suffix shares 2 with the row above; the array is [0, 0, 0, 2, 0, 1]

Exercise 19

A Patricia tree holds cart and card. Below the root it has a branch labelled ca to a node that holds no word, from there a branch r to a node that holds no word, and from there two branches, t and d, each ending a word.

• verdict: broken: the node aftercaneither branches nor ends a word
• detail: merge it with its child into one branchcar; the squeezed tree has 4 nodes, not 5

Exercise 20

A fingerprint search for 15 in the digits 31415926, base 10, modulus 7, reports the positions [3, 5].

• verdict: broken: it reports every fingerprint match without checking the digits
• detail: only [3] is the pattern; the rest are false alarms

You supply the input

Exercise 21

Find a text of 10 letters and a pattern of 4, both over the letters a and b, that make the plain scan do as many character comparisons as it possibly can. How many is that?

• maximum: 28
• an example: text aaaaaaaaaa, pattern aaaa
• every case: every one of the 7 windows is compared to its last character: each window agrees with the pattern on its first 3 letters

Then: Say what every text and pattern that reach the maximum have in common.

Exercise 22

With base 10 and modulus 13, find two different three-digit windows that have the same fingerprint.

• an example: 100 and 113
• the rule: two windows get the same fingerprint exactly when the difference of the numbers they spell is a multiple of 13

Then: Say the rule that decides, for any two numbers, whether they get the same fingerprint.

Exercise 23

Choose five words of four letters each so that the trie holding them has as many nodes as possible. How many is that, and how many nodes does the Patricia tree of the same words have?

• trie nodes: 21
• Patricia nodes: 6
• every case: no two words share a first letter, so nothing is shared

Then: What does that say about when squeezing pays most?

Exercise 24

Choose a text of 8 letters over a and b, with $ added at the end, that makes prefix doubling run as many rounds as possible. How many doubling rounds does it take, not counting round 0, the tagging by single letters?

• maximum rounds: 3
• an example: aaaaaaaa$
• the property: the length of the longest passage that occurs twice: the tags are all different once the window is longer than it

Then: Say which property of the text decides the number of rounds.

Exercise 25

A quote finder joins its quotes with a reserved separator, written | here, and refuses any quote that holds it. It does not check the fragment it is asked for. With the quotes you had me at hello and show me the money, write a fragment that this finder reports as found, though neither quote contains it.

• an example: hello|show
• why: with the separator kept out of every quote, a fragment that holds it can only match across a boundary, so a fragment that holds it must find nothing

Then: Say why keeping the separator out of the quotes is not enough on its own.

Which idea do you reach for

Exercise 26

A multiplayer game must check, sixty times a second, that every player’s copy of the game world is still the same as the server’s. Sending the whole world each time is far too slow, and a very small chance of missing a difference is acceptable.

• → (a) fingerprinting

• (b) divide and conquer

• (c) sample, then walk

• (d) work in blocks

Answer: (a) Each side sends one small number computed from its whole world. Equal numbers say almost certainly the same; only when they differ is anything bigger sent.

Exercise 27

A public web service checks whether a pasted paragraph appears in its archive using a rolling fingerprint with a fixed, published modulus. An attacker sends texts that make every window match, and the service slows to a crawl.

• (a) carry what you know

• → (b) randomization

• (c) rank and select

• (d) canonical form

Answer: (b) Draw the modulus at random for each search, so no input can be written against it in advance.

Exercise 28

A phone keyboard suggests words while you type. The team wants the stored dictionary compact, and still to be correct after words are added and removed every day.

• (a) doubling

• → (b) canonical form

• (c) fingerprinting

• (d) sample, then walk

Answer: (b) A squeezed tree whose every node branches or ends a word, restored after every insert and removal, stays at about two nodes per word.

Exercise 29

You must sort the positions of every line break in a ten-gigabyte log by what follows them, and many lines repeat long stretches word for word, so comparing strings directly keeps re-reading the same letters.

• → (a) doubling

• (b) randomization

• (c) work in blocks

• (d) rank and select

Answer: (a) Tag by short prefixes, then sort by pairs of old tags: each round covers twice as many letters without reading any.

Exercise 30

A sorted list of every street name in a country is printed in a thick book, with no index. You need the page where names starting with Mill begin.

• (a) carry what you know

• (b) sample, then walk

• → (c) divide and conquer

• (d) fingerprinting

Answer: (c) The list is sorted, so each look at the middle of what remains rules out half of it.

Exercise 31

The suffixes of a long text are sorted, one to a row. For every row you need how many opening letters its suffix shares with the suffix in the row above, and computing each one from scratch is far too slow.

• → (a) carry what you know

• (b) work in blocks

• (c) randomization

• (d) canonical form

Answer: (a) Kasai’s move: sorted order picks the partner, the suffix in the row above; text order is the order to visit the positions, keeping the length from the last one, which can drop by at most one.

Exercise 32

A map app stores, for a billion road segments, one bit saying whether each is a toll road. It must answer how many toll segments come before segment i instantly, and may use only a little more memory than the bits.

• (a) fingerprinting

• → (b) rank and select

• (c) divide and conquer

• (d) doubling

Answer: (b) That question is rank, answered from a directory of counts in little more space than the bits.

Exercise 33

Storing a running count after every bit of that billion would cost far more than the bits; counting from the start on every question is far too slow. Each question may read only two stored counts and one machine word of bits.

• (a) sample, then walk

• → (b) work in blocks

• (c) randomization

• (d) carry what you know

Answer: (b) Store counts per big block and, relative to it, per small block; count only the few bits inside one small block.

Exercise 34

A bank numbers every transaction on an account since it was opened, ten years of them, and must quickly show the balance after any numbered transaction, without storing a balance after every transaction.

• (a) divide and conquer

• (b) canonical form

• → (c) sample, then walk

• (d) rank and select

Answer: (c) Keep the balance after every 1,000th transaction, and get any other by walking through the transactions from the nearest kept one, the way locate walks to a sampled row.

The tests pass. What did they miss?

Exercise 35

A team ships a quote finder built on an FM-index. Its tests pass: for a thousand random fragments, count agrees with a plain scan of the books, and locate returns exactly the positions the scan finds. In production, people type quotes with straight apostrophes copied from a chat, and the finder says they appear nowhere. What requirement did the tests miss?

Answer: Every test fragment was cut out of the books themselves, so every one used the books’ own bytes. The requirement nobody wrote down is what exact means for a person typing: which differences in characters must not matter.

Then: Write the requirement as a sentence a test could check.

Answer to the follow-up: For example: a fragment that differs from the text only in the form of an apostrophe, quotation mark or space finds the same quotes.

Exercise 36

An index over song lyrics returns whole songs for a fragment, joining the songs with a reserved separator. Its tests pass: every fragment cut from inside one song returns that song and every other song containing it, and a fragment that occurs nowhere returns nothing. After launch, a lyric site adds one song containing the separator byte inside a line, and from then on some searches return songs that do not contain the fragment. What requirement did the tests miss?

Answer: Every test used the corpus as it was. The requirement nobody tested is that no record may contain the separator or the end marker; without it, the stray byte is taken for a boundary between songs, and matches near it are credited to the wrong song.

Then: Say where the checks belong, and what each must do.

Answer to the follow-up: Two checks, for two different breaks. When the corpus is built: a song that holds a reserved byte is refused, or the byte is replaced, before any index is built, because wherever song boundaries are found from separators, a stray one inside a song moves them. And at query time, separately: a fragment that holds a reserved byte finds nothing, because even in a clean corpus it could only match across the boundary between two songs.

Fix the code, the box, or the design?

Exercise 37

You give an AI the trie’s design box and ask for the code. Its remove walks to the word and clears the mark that says a word ends there, and nothing else. Insert tea and ten into an empty trie, then remove both. get finds neither word, keys() returns nothing, and the count of words is 0. The trie still has 5 nodes. Which of the three is it, and why?

Answer: fix the code. Every lookup is right, so the promise holds, but invariant 3 breaks: the branch t, e, a leads to no stored word, and so does t, e, n. The box already asks for what you wanted, and the code does not keep it. On the way back up, remove must cut every node left with no word and no children; then the trie is back to 1 node, the root.

Then: Suppose the box had stopped at invariant 2 and said nothing about memory. Which would it be then? Write the line you would add to the box, and a test you would keep from the AI that checks it.

Answer to the follow-up: Fix the box. That code keeps a box without invariant 3; the leftover nodes are what the box failed to forbid. Add 3. Every branch leads to a stored word. The test to keep: insert some words, remove some or all of them, and check that the trie has exactly as many nodes as a trie built fresh from the words that remain; with every word removed, that is one node.

Exercise 38

The same AI’s trie, its remove now mended, holds 2,000 web addresses of a shop, such as https://shop.example.com/products/aaliwuqonsmb/reviews, about 54 letters each. Nothing has been removed, every check of the box’s invariants passes, and every lookup is right. Yet the trie has 36,601 nodes, about 18 per address, and a colleague says the leak is back. Which of the three is it, and why?

Answer: change the design. Nothing is broken. The box’s cost says memory up to a node per letter stored, and addresses that share their start and then never branch again spend a node on every letter of their tail. The promise and the invariants hold; the cost no longer fits a dictionary of long words.

Then: Name the design you would switch to, and say what you would measure to check it.

Answer to the follow-up: The Patricia tree, whose goal is the trie’s job when the words are long: it squeezes every chain into one branch. Its promise is the trie’s, so the same tests of get, insert and remove still apply. Measure the nodes: on these addresses it has 2,649, at most two per address.

Exercise 39

An AI builds the FM-index from its design boxes for a reading app. Asked where i occurs in mississippi$, locate returns [10, 7, 4, 1]; asked for ssi, [5, 2]. The app jumps to the first position in the list, so a search for i takes the reader to position 10, the last i in the text. Which of the three is it, and why?

Answer: fix the box. Every start position is there, each once. The box promises them in no particular order, and the code keeps it: they come out in the order of the sorted suffixes. The app wanted them in text order, and the box never asked for it.

Then: Rewrite the line of the box that has to change, say what the change costs, and name a test you would keep from the AI.

Answer to the follow-up: Promise: every start position, each exactly once, in increasing order. The cost: sorting the \(z\) positions found, about \(z \log_2 z\) more steps per question, and the index needs no more memory. The test: on texts the AI never saw, compare locate with a plain scan as lists, not as sets; for i the scan gives [1, 4, 7, 10].

Derive it

Exercise 40

Write remove(key) for the Patricia tree, as code or as precise steps, so that the invariant holds again after every removal. Your answer must say what happens to a node left with no word and no children, to one left with a single child and no word, and why the root is treated differently from every other node.

Removal: clear the word’s mark; if the node now has no word and no children, delete it from its parent; then, at the parent (and at the node itself if it still has a single child and no word), merge a node that has no word and exactly one child with that child, joining the labels. Never merge the root, which has no branch above it to merge into. A word that is not stored changes nothing: the walk falls off the tree, stops partway along a label, or ends at a node with no mark, and removal returns there.

Node counts after each removal, equal to a fresh build each time: after removing romulus: 12; after removing rubicon: 10; after removing rubicundus: 8