Skip to main content

Independent Mastery Assessment

Attempt after the practice and labs. Allow 2–3 hours for a first independent attempt plus a separate review. Do not consult solutions or the reference implementation during the attempt. Disclose any assistance. A tool-assisted attempt is useful practice but needs a fresh independent recheck for mastery. See scoring and evidence before beginning.

A1. Stable record contract​

Sort (3,Z),(1,Y),(3,X),(1,W) by numeric key while preserving arrival order among equal keys. Give the result, a merge invariant, and a smallest failure for taking the right-hand record on ties. Explain why sorting full tuples is not equivalent. State time and auxiliary storage for your merge implementation.

Return the equal range for 2 and for 3 in [0,2,2,5,5,5]. Write or derive both boundary loops with excluded-region invariants and a strictly decreasing measure. Explain behavior on empty input and the cost of checking sortedness on every call.

A3. Selection and randomization​

Find zero-based rank 3 in [8,2,2,6,1,6]. Show a three-way partition using pivot 2 and identify the remaining subproblem. Give an expected-linear argument that accounts for bad attempts. Does a public fixed seed imply worst-case linear work? Explain input-preserving storage costs and all-equal behavior.

A4. Stateful dictionary correctness​

With capacity 8 and home slot key mod 8, insert (7,A),(15,B),(23,C); delete 7; update 15 to D; delete 15. Show slots and live/used counts at each step. What should get(23) and get(15) do? Exhibit a failure caused by treating a tombstone as never-used empty, and one caused by inserting before checking for an existing key. Explain why doubling capacity requires rehashing.

A5. Qualify a performance guarantee​

A design note says: "Our deterministic modulo table is only 40% full, so every operation is O(1). Doubling makes even a resize O(1)." Correct both claims with a concrete collision family and a sequence-cost argument. Derive the expected chaining collision bound under a separately specified universal-family model. Explain what this derivation does not establish for linear probing.

A6. Heap correctness and cost​

Heapify [4,2,5,1,2], pop once, push 0, then drain. Give any valid intermediate heap and the observable output sequence. Derive linear bottom-up construction without multiplying n by the root's worst-case height. Explain how to make equal priority events FIFO without comparing payload objects.

A7. Representation and I/O​

First, price unsigned 32-bit LSD sorting using four 8-bit passes and explain why it cannot run in Theta(n/log n) by choosing wider digits. Second, sort a synthetic 72 GB file using 6 GB usable runs and fan-in 4. Count initial runs, materialized merge passes, total read/write traffic including run generation, and the change if final output streams directly to a consumer. State excluded resource costs.

A8. Unfamiliar transfer​

A log service merges sorted finite shard iterators, some empty, under a memory budget that cannot hold all records. Equal timestamps must be ordered by shard number, then original order within a shard. Design the queue entries, invariant, complexity, and a test that catches eager flatten-and-sort. Change the requirement to global arrival order across shards: what additional information is necessary? Explain why timings alone cannot establish the claimed memory bound.

After submission, use Assessment Solutions and Scoring.