Speaker note: Last week we explored a whole graph to answer a question. This week flips that idea: can we compute exactly where to look, without exploring anything at all?
Speaker note: Twenty-one short animations carry the whole lecture; each idea gets one normal run and one edge/hard run, right where it is introduced.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: Everything this week either beats binary search on a special case, or drops "compare" entirely for "compute".
Speaker note: Nothing here is brand new machinery — Week 2's two basic structures reappear as building blocks all through today.
Speaker note: Every box on this map gets its own slides below, most with a short animation and a complete C/Java program.
Speaker note: Section 1 sets up the one question every algorithm today answers differently: how many comparisons before you find — or rule out — a key?
Speaker note: Yes to both — faster comparison-based search exists for special data, and hashing drops comparisons almost entirely.
Speaker note: "Correctness first, speed second" — every algorithm today must still get the right answer on every input.
Speaker note: Sections 2–6 answer the first question; Sections 7 onward answer the second, with hashing.
Speaker note: Every algorithm in Sections 2–5 exploits one extra fact about the data that plain binary search throws away.
Speaker note: Hashing, the biggest idea of the week, gets its own toolbox slide later, right before Section 7 begins.
Speaker note: Think about what extra information the array's actual values might carry, beyond just being sorted.
Speaker note: This is exactly the idea Section 3's interpolation search turns into a full algorithm.
Speaker note: Section 2 opens the "faster than binary" family: instead of halving, jump forward in fixed blocks, then scan one block linearly.
Speaker note: Jump search trades binary search's recursion for one straight line of block jumps, then a short linear scan.
Speaker note: This is one of the cleanest examples in the course of calculus (minimizing a sum) driving an algorithm's design.
Speaker note: A block is like a chapter — check its last page, and only open it fully once you know the word is inside.
Speaker note: Two phases, each simple on its own: coarse jumps to find the right block, then a short linear scan inside it.
Speaker note: Balancing "few big jumps" against "short final scan" is exactly a minimize-the-sum calculus problem, solved once for all n.
Speaker note: Normal example: 16 sorted values, target found in the second block — watch the block boundary checks, then the short linear scan.
Speaker note: The target falls between two real values — the linear scan inside the right block stops early, the moment it passes the target.
Speaker note: `block` is computed once, from `n` alone — it never depends on `target`, only the array's size.
Speaker note: The same "sorted array" fact that lets binary search stop early also lets this final scan stop early, on `arr[i] > target`.
Speaker note: Jump search is a genuine middle ground: faster than linear search, simpler (no recursion) than binary search.
Speaker note: A wrong block size still finds the right answer — it just loses the O(sqrt(n)) guarantee.
Speaker note: Recall the formula from a few slides back, then apply the O(sqrt(n)) bound.
Speaker note: This is the O(sqrt(n)) bound made concrete: 20 is close to 2*sqrt(100), the theoretical worst case.
Speaker note: Section 3 replaces "always check the middle" with "compute where the target should be" — a formula instead of a fixed split point.
Speaker note: Nobody does — you flip straight toward the back, because you already know roughly where "S" should be.
Speaker note: O(log log n) is a genuinely small number — for a billion elements, it is only around 5.
Speaker note: This single difference, using the value instead of ignoring it, is the entire idea of interpolation search.
Speaker note: Everything after the formula is identical to binary search — only how the split point is chosen has changed.
Speaker note: Normal example: 16 uniformly spread values — watch the formula's estimate land very close to the target in a single probe.
Speaker note: Every value in this range is identical — arr[hi] equals arr[lo], so the formula's denominator would be zero without an explicit guard.
Speaker note: The guard is not optional — without it, an all-equal range crashes the program with a division-by-zero error.
Speaker note: Identical in shape to binary search's narrowing step — only `pos` came from a formula instead of `(lo + hi) / 2`.
Speaker note: Interpolation search is a genuine trade: excellent on the right data, no better than linear search on the wrong data.
Speaker note: A skewed array can make interpolation search's probes climb toward O(n), demonstrating exactly the second mistake.
Speaker note: Recall the complexity slide's second bullet point, a few slides back.
Speaker note: "Roughly uniform" is not a minor detail in interpolation search's description — it is the condition the whole speed-up depends on.
Speaker note: Section 4 answers a very different question from Sections 2–3: what if you do not even know how big the array is?
Speaker note: Binary search's very first step needs `hi = n - 1` — if `n` is unknown, that step cannot even be taken.
Speaker note: "Galloping" is a vivid name for the doubling phase — small steps that get bigger and bigger, like a horse picking up speed.
Speaker note: The doubling phase's only job is to manufacture a valid `hi` for binary search to use — nothing more.
Speaker note: The array does need a known upper bound in practice — "unbounded" here means "we do not need to know n in advance", not "infinite".
Speaker note: Normal example: 16 sorted values, target found around the middle — watch the bound double, then binary search take over inside it.
Speaker note: The bound doubles all the way past the array's real end, clamped to n-1, before binary search reports not found.
Speaker note: This whole block only decides where binary search should start — it never itself finds the target, except by luck at index 0.
Speaker note: Exactly binary search from Week 1, unchanged — only the starting `lo` and `hi` come from the doubling phase above.
Speaker note: This is the whole payoff: exponential search adapts to WHERE the answer is, not just to how big the array is.
Speaker note: Clamping matters because `arr[bound]` would otherwise read past the array's real end.
Speaker note: Recall the complexity slide: the cost depends on the target's INDEX, not the array's size.
Speaker note: Binary search alone would still need about 20 comparisons here — exponential search's advantage is largest exactly when the target is near the front.
Speaker note: Section 5 closes the "faster search on sorted data" family with a strategy that never divides or multiplies at all.
Speaker note: This was a real, practical constraint on early computers — some had no hardware division instruction at all.
Speaker note: Kiefer's original problem was finding the peak of a function using as few measurements as possible — the same math reused here.
Speaker note: The ruler shrinks by exactly one Fibonacci step at a time, which is what replaces halving in binary search.
Speaker note: "Shrink by two steps" on an overshoot is what keeps the whole algorithm free of any multiplication or division.
Speaker note: Normal example: 16 sorted values, target found around the middle — watch the (fib, fib1, fib2) triple shrink after each probe.
Speaker note: The main loop ends with fib1 == 1 — one element is left over and checked separately, then reported not found.
Speaker note: The while-loop above only runs once, before any comparisons — it just finds the starting Fibonacci triple for `n`.
Speaker note: Every line here is `+` or `-` only — this is the concrete proof that no division or multiplication was ever needed.
Speaker note: On modern hardware division is cheap, so Fibonacci search is now mostly of historical and educational interest.
Speaker note: The "one element left over" case is exactly what this section's not-present edge case was built to show.
Speaker note: Recall the "short history" slide's motivation, a few slides back.
Speaker note: Modern CPUs have fast hardware division, so this specific advantage has mostly disappeared — the algorithm survives as an elegant idea.
Speaker note: Section 6 is a short pause before hashing — a single table to compare everything Sections 2–5 just built.
Speaker note: "Needs" here is the extra assumption beyond "sorted" that each strategy relies on to beat plain binary search.
Speaker note: Every row on both tables shares one requirement: the data must be sorted first — hashing, starting next, drops that requirement entirely.
Speaker note: None of these strategies is ever the "wrong" choice — each is a specialist that wins only under its own assumption.
Speaker note: Recall which strategy specifically does not require knowing `n` ahead of time.
Speaker note: This is precisely the "unbounded searching" framing from Bentley and Yao's original 1976 paper.
Speaker note: Section 7 opens the second half of the week: instead of comparing values, compute exactly where a key belongs.
Speaker note: Yes — that single idea, "compute, don't compare", is the entire foundation of hashing.
Speaker note: Luhn also invented the separate, unrelated credit-card checksum that bears his name — a different, more famous invention by the same person.
Speaker note: Direct addressing is the ideal case hashing is trying to approximate, once the key space is far bigger than the table.
Speaker note: A perfect hash function with zero collisions exists in theory, but in practice collisions are expected and must be handled.
Speaker note: "mod" is the whole function — its simplicity is exactly why it is the natural first hash function to teach.
Speaker note: Normal example: m = 11 (prime), 12 assorted keys — watch most keys spread out, with only the occasional collision.
Speaker note: m = 10, and every key is a multiple of 10 — k mod 10 is 0 for every single key: total collision, the worst possible spread.
Speaker note: This is not a superstition — it follows directly from how the modulo operation interacts with a key's own factors.
Speaker note: In C, `key % m` can be negative when `key` is negative — the extra `+ m` fixes that before the final `% m`.
Speaker note: A hash function's own cost is essentially free; every remaining slide this week is about what happens after two keys collide.
Speaker note: The negative-key guard slide's `+ m` trick is a small detail that a surprising number of real bugs trace back to.
Speaker note: Think about which remainders `key mod 8` can produce when `key` is always even.
Speaker note: This is the same "shared factor" problem as the power-of-10 edge case, just with the factor 2 instead of 10.
Speaker note: Section 8 accepts that collisions are normal, then builds the first of two standard ways to survive them.
Speaker note: There is no single right answer — the rest of today's lecture is two different, equally valid answers to this exact question.
Speaker note: Collisions never overwrite anything here — they simply grow a list, which is exactly Week 2's linked list reused.
Speaker note: Insertion never has to search the chain first — the new node always goes straight to the front.
Speaker note: Normal example: m = 7, 10 inserts, 4 searches — watch a bucket's chain grow, then get walked during a search.
Speaker note: m = 3, 12 keys: load factor α = 4 — chains grow long, and searching now costs several probes on average, not O(1).
Speaker note: This is Week 2's "insert at head" linked-list operation, completely unchanged — only the bucket comes from a hash.
Speaker note: A `NULL` chain is handled for free here — the for-loop simply never runs, and the function returns false immediately.
Speaker note: Load factor is the single number that predicts, on average, how many nodes a search must walk past.
Speaker note: The worst case is deliberately alarming — Section 10's rehashing exists specifically to prevent α from ever getting that large.
Speaker note: A hash table with zero collisions ever is not a realistic design goal — managing them well is the actual goal.
Speaker note: Apply the load factor formula from a few slides back directly.
Speaker note: This exact scenario is what Section 10's rehashing later fixes, by growing the table before α gets this large.
Speaker note: Section 9 answers the collision question a second way: instead of a list outside the table, keep every key inside it.
Speaker note: Yes — this whole section is three different rules for where to look next, when a key's home cell is occupied.
Speaker note: All three rules answer exactly one question differently: "the home cell is taken — where do I look next?" The tombstone detail is explained fully in Section 9a.
Speaker note: The simplest probing rule: if a cell is taken, just try the very next one, wrapping around at the end.
Speaker note: Those growing runs are exactly what the next slide's "primary clustering" describes.
Speaker note: Normal example: m = 11, 10 inserts, a search, and a delete — watch a probe sequence form, then get walked again during the search.
Speaker note: Without a tombstone, this exact search would wrongly stop at the emptied cell and report "not found" — even though the key is still further along the probe chain.
Speaker note: m = 8, 8 keys collide into the same cell in sequence — the table fills exactly, and the next insert is correctly rejected.
Speaker note: `state[idx] != OCCUPIED` accepts both EMPTY and DELETED cells — reusing a tombstone's slot for a new key.
Speaker note: `DELETED`, never `EMPTY` — this one-word difference is what keeps every later search's probe chain intact.
Speaker note: "Predictable" is the actual problem — every key that collides at the start of a run walks the exact same growing run to escape it.
Speaker note: Open addressing has no "extra" memory to fall back on — once the table is full, no key at all fits, unlike chaining.
Speaker note: Every one of these mistakes still compiles and often "looks" correct on small test cases — that is exactly what makes them dangerous.
Speaker note: Recall the tombstone edge-case animation's speaker note, a few slides back.
Speaker note: A tombstone means "something was here, keep looking" — only a true EMPTY cell means "nothing was ever placed beyond this point".
Speaker note: Quadratic probing keeps every key inside the table too, but replaces linear probing's fixed step with a fast-growing one.
Speaker note: The growing step is the whole fix for clustering — but that same growth is what can cause the new cycling problem.
Speaker note: Normal example: m = 13 (prime), 10 keys — watch the i² jumps land on scattered cells instead of one growing run.
Speaker note: m = 8, not prime — the i² sequence revisits the same few cells forever, even though free cells still exist elsewhere in the table.
Speaker note: `i*i` is the only real change from linear probing's code — the step now depends on `i`, not on a fixed +1.
Speaker note: Unlike linear probing, a bad m here can break correctness outright, not just slow things down — this condition is genuinely stronger.
Speaker note: The animation's edge case flags a cycle explicitly, exactly so it is never confused with a table that is truly full.
Speaker note: Recall the "complexity, and why m matters" slide's last bullet.
Speaker note: This is exactly the scenario the quadratic-cycle edge-case animation demonstrated a few slides back.
Speaker note: Double hashing keeps the same "probe inside the table" idea, but makes the step itself depend on the key.
Speaker note: This directly fixes linear probing's problem: two keys sharing a home cell now usually take completely different routes from there.
Speaker note: Normal example: m = 13, R = 11, 10 keys — watch two keys share a home cell, then follow visibly different probe paths.
Speaker note: m = 9, not prime — a key's step shares a common factor with m, so its probe sequence cycles without reaching every cell.
Speaker note: `h2` is built so its result is always in `[1, r]` — never 0, since a step of 0 would reprobe the same cell forever.
Speaker note: `step` is computed once per key, outside the loop — every collision for this key then reuses that same personal step.
Speaker note: A composite m can let some keys' steps cycle, exactly like Section 9b — double hashing is not immune to the same underlying issue.
Speaker note: A step of exactly 0 is the single most dangerous bug here — it reprobes the very same occupied cell forever.
Speaker note: Recall each subsection's "why m matters" bullets, and compare how strict each condition was.
Speaker note: Quadratic and double hashing can outright fail to find a free cell on a bad m; linear probing degrades gracefully instead, just more slowly.
Speaker note: Section 10 answers the question every collision-resolution technique this week has been dodging: what happens when the table gets too full?
Speaker note: The table should grow — but growing a hash table is not as simple as growing an array, because every key's index depends on m.
Speaker note: A key's index depends on m through the mod operation — change m, and almost every key's correct index changes too.
Speaker note: Rehashing needs no new insertion logic at all — it just calls the ordinary insert() once per surviving key.
Speaker note: Normal example: m0 = 6, 10 keys — watch α cross the threshold, a new prime-sized table appear, and every key's index get recomputed.
Speaker note: m0 = 2 is tiny — the threshold is crossed almost immediately, and a second rehash follows soon after the first.
Speaker note: This is the exact same reasoning as Section 7's division method — the new table size still needs to be prime.
Speaker note: The loop walks every OLD cell once, so this whole operation costs O(m) — expensive, but it happens rarely.
Speaker note: "Amortized" means the occasional expensive operation, averaged over many cheap ones, still comes out to a small constant.
Speaker note: Rehashing on every insert would make EVERY insert cost O(n) — the whole point of a threshold is to make it rare.
Speaker note: Compute the new α after the insert, then compare it to the threshold, then apply next_prime(2*m).
Speaker note: This is exactly the normal-preset animation's scenario above, with the same m0 = 6 starting size.
Speaker note: Section 11 is the practical payoff of the whole second half of the week: which technique should you actually reach for?
Speaker note: Every row is a genuine trade-off — neither column is simply "better" in every situation.
Speaker note: This ordering is also roughly the historical order these three techniques were developed in, each fixing the previous one's weak spot.
Speaker note: Real hash table libraries (Java's HashMap, for instance) make exactly this kind of engineering trade-off explicitly, in their documentation.
Speaker note: Recall the practical rule of thumb slide's first two bullets.
Speaker note: If deletions later become common, tombstones would need careful handling — chaining might then become the better trade-off instead.
Speaker note: Every row here still compares values — hashing, summarized next, is the one idea this week that mostly does not.
Speaker note: Both collision families still share one number that predicts their speed: the load factor α = n/m.
Speaker note: If a student remembers only one sentence from today, this is the one worth remembering.
Speaker note: These mirror the self-check quiz at the end of the written notes, one question per slide, with a shorter set here.
Speaker note: Ask, wait, then advance.
Speaker note: This is the exact O(sqrt(n)) bound from Section 2, applied to a bigger n.