Implementation and Transfer Studio

Complete correctness and explanation before adding an optional time limit. Fast recall alone is not the completion criterion.

P13. Resource budget

Plan an external sort for 100 GB input, 4 GB usable run memory, and fan-in 5. Count runs, merge passes, and fully materialized read/write traffic. Recompute when the final result streams to a consumer. List memory omitted by a naive "all RAM belongs to records" calculation.

P14. Stable event ties

Events (time=5,A) then (time=5,B) must be processed FIFO on equal timestamps. Specify a heap key that never compares arbitrary payloads. Add cancellation and reinsertion of the same identity: choose indexed deletion or lazy versioning, and state the extra invariants and retained-memory costs.

P15. Representation changes

Compare four 8-bit versus two 16-bit passes for unsigned 32-bit records. Give cost expressions including bucket initialization and auxiliary storage. Explain why the smaller number of passes is not a measured speed claim. Extend the encoding to fixed-width signed integers; explain why floats require a different contract. Implement the integer extension after stable counting sort works.

P16. Streaming transfer

Implement merge of sorted finite generators using one head each, then implement largest-K streaming values using a bounded min-heap. Compare each processed prefix with a trusted sort. Test K=0, K larger than the prefix, ties, and empty streams. State whether the final top-K output is sorted and price that separately.

Attempt independently, then consult Practice Solutions. Submit a proof or counterexample as requested; code output alone is insufficient.