Skip to main content

Worked Examples

These examples connect contracts to derivations. Cover the solution, attempt the prompt, then compare your invariant and assumptions as well as your final answer.

1. Stability is observable in payload order​

Sort (2,A),(1,B),(2,C),(1,D) by the numeric key. Split into two two-record runs, sort each, then merge (1,B),(2,A) and (1,D),(2,C). On equal keys take from the left. Output is (1,B),(1,D),(2,A),(2,C).

The merge invariant says that output is sorted, contains exactly the consumed records, and preserves tie order from each run and across the earlier left run. Taking D before B would keep keys sorted and retain all records, but violate stability. Comparing the whole tuple can also silently impose alphabetical payload order. A stronger test gives each payload an unorderable object and retains its identity. Transfer: sort by department then arrival order, and state which field is the actual key versus an explicitly requested secondary key.

2. Lower and upper bounds answer different questions​

For [1,2,2,2,4], lower bound of 2 is 1, upper bound is 4, so count is 4-1=3. For 3 both return 4. For 0 both return 0; for 5 both return 5.

Lower-bound excluded regions are < target and >= target; upper-bound regions are <= target and > target. Both start empty, preserve order by sortedness, and terminate when the unknown interval is empty. An arbitrary successful binary search result cannot substitute for either boundary. Transfer: emit keys in the closed range [2,3] by using lower_bound(2) and upper_bound(3), with output cost added to the two searches.

3. Selection pays for one side, including bad attempts​

Find zero-based rank 2 of [9,1,1,4,7]. With pivot 1, two equal values occupy ranks 0 and 1. Continue among [9,4,7]; pivot 4 identifies the answer 4.

The partition invariant separates smaller, equal, unknown, and greater regions. Every step shrinks the unknown region; every unsuccessful outer iteration removes the nonempty equal region and one irrelevant side. Thus it terminates. For time, group random pivot attempts into phases ending with a pivot in the middle half. Each phase needs a bounded expected number of attempts and costs O(current size) in expectation. Phase sizes decrease geometrically, so their expected costs sum to O(n). Worst-case unlucky pivots can still give O(n²). Transfer: a fixed seed permits replay, not a stronger bound.

4. Delete, then update behind a tombstone​

Capacity 8 and home slot key mod 8 put (0,A),(8,B),(16,C) at slots 0,1,2. Delete 0 to a tombstone. A lookup for 16 must pass that tombstone and key 8. Updating 8 must find slot 1, not create another 8 at slot 0. After deleting 8, get(8) must fail; returning the stale B reveals the duplicate-key bug.

Live size falls from 3 to 2 on the first deletion and stays 2 on update. Used occupancy remains 3 because the tombstone still affects probing. Growth must rehash into the new modulus. Transfer: 7,15,23 expose the same bug across the end of the array; an in-bounds-only test misses it.

5. A low load factor does not prove constant-time access​

At capacity 16, the five keys 0,16,32,48,64 have load 5/16 but share a home slot. A missing key 80 probes five entries plus an empty slot in linear probing. Increasing capacity can help some key patterns, but for any fixed modulus there is another colliding set.

Under a universal family chosen independently of fixed keys, a separate-chaining analysis instead bounds expected colliders by sum_y Pr[h(y)=h(x)] <= n/m. That establishes expected O(1+alpha) navigation for that model, not for every deterministic hash and not automatically for linear probing. Transfer: add the cost of hashing and comparing a long string; constant navigation is not constant total key-processing time.

6. Why bottom-up heapify is linear​

Heapify [5,1,1,3] from index 1, then 0. Index 1 is already ordered above 3. Root 5 swaps with a child 1 and may then swap with 3. One valid heap is [1,3,1,5]. Its array is not sorted, but repeatedly popping produces [1,1,3,5].

At each parent, child subtrees are already heaps. Sifting the parent restores the whole subtree without breaking its children's internal order. The total height sum is bounded by sum_{h>=1} floor(n/2^h) < n. Each possible downward level needs a constant number of comparisons, so construction is O(n). Testing sorted draining verifies examples of correctness; it cannot distinguish O(n) heapify from repeated O(log n) insertion. Transfer: review source and derive the bound separately.

7. One head per stream is enough​

Merge [1,4], [], and [1,2,5]. Initial heap holds (1,0),(1,2); the empty stream contributes no entry. Emit stream 0's 1 and insert (4,0). Emit stream 2's 1 and insert (2,2). Continue with 2,4,5, giving [1,1,2,4,5].

Each head is no greater than any unread item in its own sorted stream, so the smallest head is globally safe to emit. Advancing only that stream preserves representation and multiplicity. Cost is O(K + N log(K+1)), extra state O(K). Materializing the output adds O(N) space. Transfer: input streams are generators; an eager flatten-and-sort implementation violates the bounded-state objective.

8. External-sort traffic includes run generation​

For 100 GB of data and 4 GB usable run capacity, generate 25 runs. With fan-in 5, the first merge produces five runs and the second produces one: two merge passes. In a fully materialized model, run generation transfers 200 GB and each merge pass another 200 GB. Total is 600 GB. An ideal aggregate 0.5 GB/s yields an I/O-only estimate of 1,200 seconds, excluding CPU and operational overhead.

Fan-in 5 needs five input buffers, one output buffer, heap state and other runtime overhead. The 4 GB run budget cannot simultaneously be assumed available for all other structures. If the final output streams directly into a consumer, the final 100 GB disk write is omitted in this model, giving 500 GB of disk traffic; the consumer's work remains. Transfer: recompute for file-handle limits or unequal record sizes instead of preserving the original estimate blindly.