Hashing and Priority-Queue Clinic

P9. Name the probability space

For fixed absent key x and n stored keys, derive the expected number of colliders under a universal family into m buckets. Explain why independence between collision indicators is unnecessary for the expectation. Give a low-load counterexample for deterministic modulo hashing.

P10. Tombstone update bug

At capacity 8, insert keys 0,8,16, delete 0, update 8, then delete 8. Trace a faulty insertion that uses the first tombstone immediately and the correct insertion that searches further. State live/used counter changes and the behavior of a final get(8). Repeat with keys 7,15,23 to check wraparound.

P11. Resize reasoning

Explain why copying a linear-probing array to double capacity without rehashing is wrong. Separate geometric allocation cost from collision-probe cost. Construct grow/shrink thrashing with equal half-full thresholds and suggest separated thresholds. Explain why the lab deliberately claims no expected O(1) guarantee.

P12. Heap construction

Heapify [5,1,1,3], then pop, push 0, and drain. Prove bottom-up heapify's O(n) bound using a height sum. Give the index formula for a lone left child and explain why choosing the smaller child during sift-down is necessary.

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