Randomized, Range-Query and Version Clinic

Budget 7–10 focused hours for P15–P20. Use feedback only after a derivation. Implementations beyond the required lab APIs are optional.

P15: randomized shape

Draw min-priority treaps for keys 1,2,3 with priorities [40,10,30] and [10,20,30]. State the key/priority invariants, tie rule, independence model, and precondition for merging two treaps by separated key ranges.

P16: Bloom sizing and exactness

For n=1000, p=0.01 compute approximate m,k, integer choices and byte payload. Explain overload and repeated inserts. Build a one-bit false-positive example and show how an exact store must answer it. Name three assumptions behind no false negatives.

P17: Fenwick boundaries

Build internal cells for [1,2,3,4], add 2 at position 1 and compute prefix(3) and sum [1,3). Explain lowbit block ranges and why point updates must never start at internal zero. Explain why arbitrary range minimum cannot be obtained from prefix minima by subtraction.

P18: lazy composition

Derive affine add/assign actions on sums and tag composition new-after-old. Compare assign 5 then add 3 with the reverse. Then apply add 2 on [1,4) and assign -1 on [2,4) to [1,2,3,4]; report total and [1,3) sum. Explain why assignment zero is not an absent tag.

P19: persistent branching

Fork version 0 [1,2,3,4] twice: set position 0 to 9; separately set position 3 to -1. Give all sums, identify shared subtrees and bound new nodes per update. Describe tests that distinguish branching from latest-only updates and shared-node mutation from immutable copying.

P20: representation models

For bits [1,0,1,1,0], define rank(i) on [0,i) and zero-based select(k). Compute rank(3), select(2). Explain why packing bits alone does not establish constant-time rank, why tree shape excludes key payload, and which assumptions support an O(1+n/B) scan-transfer bound.