Assessment Solutions and Scoring

Consult after the independent attempt. Accept equivalent correct algorithms and proofs. Use the per-competency rubric in Assessment, and record critical errors even when a final value happens to be correct.

A1 / C1

Output (1,Y),(1,W),(3,Z),(3,X). The consumed output is a sorted permutation of consumed records, preserving their relative order within equal-key groups. Left-first ties preserve earlier input order across runs. Two equal tagged records split across runs expose right-first reversal. Full tuple comparison instead puts W before Y and X before Z here. Standard buffered merge sort takes O(n log(n+1)) time and O(n) extra slots. Level 3 explains the failure with unorderable payloads or a changed explicit secondary-key contract.

A2 / C2

2→(1,3), 3→(3,3). Lower-bound excluded regions are < target and >= target; upper-bound regions are <= target and > target. Use mid in [lo,hi), move lo to mid+1 or hi to mid. hi-lo strictly decreases, ending at the desired boundary. Empty input returns (0,0) without indexed reads. Two boundary searches are logarithmic under random access; a fresh sortedness scan makes each complete call linear. Level 3 derives a range-output or predicate-search variant correctly.

A3 / C3

Sorted values are [1,2,2,6,6,8], answer 6. Pivot 2 yields below [1], equal [2,2], above containing [8,6,6]; original rank 3 is rank 0 of the strict-high subproblem. A good pivot in the middle half shrinks the active set by a constant fraction, and expected attempts until one is bounded by a constant. Charge all those attempts O(current size), then sum phase sizes geometrically. Worst-case work remains quadratic; a public seed adds reproducibility, not a guarantee. The copied implementation uses O(n) storage; all-equal input finishes in one linear partition. Level 3 distinguishes this proof from a deterministic BFPRT discard bound and explains the random-input independence assumption.

A4 / C4

Initial live slots 7:A,0:B,1:C; live=used=3. Deleting 7 leaves a tombstone, live=2, used=3. Update 15 at slot 0 to D; counts unchanged. Delete 15 to a tombstone; live=1, used=3. get(23) returns C after crossing both tombstones; get(15) raises KeyError. Emptying slot 7 would stop get(23) prematurely. Inserting 15 into the first tombstone leaves stale B at slot 0, which can reappear after deletion. With new capacity 16 the home indices change, so copying old slots does not preserve probe reachability. Level 3 covers missing deletes, legal None payloads, and tombstone cleanup separately from live-load growth.

A5 / C5

For any fixed capacity m, keys 0,m,2m,... collide under modulo hashing even at low occupancy. One lookup may traverse a linear cluster; low load alone gives no per-operation constant bound. A resize touches many entries and is not O(1) worst case. Geometric capacity growth bounds total allocated slots, and with an appropriate expected-linear redistribution model can support an expected amortized rebuilding charge; it does not bound adversarial reinsertion probes.

For universal hashing selected independently of fixed keys, sum the n collision indicators for absent x: expectation <=n/m. With constant hash/equality cost, chaining search is expected O(1+n/m). This is not a per-key worst-case bound, an adaptive-adversary guarantee, or a linear-probing theorem. Level 3 separates all these qualifications without confusing expected with amortized.

A6 / C6

One heap is [1,2,5,4,2]. First pop returns 1. After pushing 0, draining yields [0,2,2,4,5]. The full observable removal sequence is [1,0,2,2,4,5]. Every repaired parent starts above already valid child heaps. Charge each possible downward level: sum_{h>=1} floor(n/2^h) < n, yielding O(n) heapify with constant work per level. Use (priority,unique_sequence,payload) for FIFO ties. Level 3 explains occasional backing-array allocation or the index-map cost of priority changes without overstating the minimal heap contract.

A7 / C7

Radix work Theta(4(n+256)), extra slots O(n+256). The number of digit passes is ceil(k/w)>=1, so wider digits cannot remove the work of reading/writing n records; larger buckets also cost initialization and memory. No speed ratio follows.

72/6=12 initial runs. With fan-in 4, 12→3→1 means two merge passes. Each of run generation and two materialized merge passes transfers 144 GB; total 432 GB. Streaming final output removes the final 72 GB disk write, leaving 360 GB in this model. Buffers, heap state, sort workspace, record decoding, file handles, CPU, seeks and contention need separate accounting. Level 3 identifies how unequal record sizes or a different materialization contract changes the estimate.

A8 / C8

Keep (timestamp,shard_index,record) for one current head per nonempty shard; because at most one head per shard is present, timestamp and shard index suffice to avoid comparing payloads. Advancing that shard preserves within-shard order. Each head is its stream's least remaining item, so global extraction is safe. Initialization O(K), total O(K+N log(K+1)), state O(K), excluding output collected by the caller. A guarded generator can count pulls before the first output and reject reading an entire large stream. Source review establishes state growth.

Global arrival order across shards cannot be reconstructed from shard number and local order alone. A globally comparable arrival sequence or another specified ordering authority must accompany records; the merge key and source ordering must respect it. A heap cannot invent missing ordering information. Level 3 identifies both that information requirement and the need for correctly ordered input streams. Runtime measurements do not prove a memory bound.