Practice Solutions and Feedback

Preserve independent attempts first. Equivalent valid representations and tied choices are accepted when their contracts and invariants agree. A correct final number without the requested explanation is insufficient.

P1–P7: ordering and partitions

P1. Key 12 violates inherited upper bound 10. Check lower/upper bounds and unique node identity during traversal. Replacing a map key changes payload, not node count. Two-child deletion must move the successor's key and value, then remove its old occurrence and repair metadata.

P2. After 10,5,15,1, red parent 5 and red uncle 15 become black; 10 is recolored then blackened as root. With b internal black nodes per root-to-NIL path, n is at least 2^b-1 and paths have at most 2b internal nodes. The height bound does not reduce O(n) traversal-output work.

P3. Insertion 3,1,2 needs left rotation at 1 then right at 3. Root 2 has height 2, size 3. After replacing 1 and deleting 3, keys are [1,2], root height 2, size 2; rank(2)=1, select(1) gives key 2 and its payload. Metadata remains necessary even when a height happens not to change. Deletion can shrink several ancestors and trigger further repairs.

P4. Expected level-5 nodes are 1024/32=32. Any height at least 20 has probability at most 1024/2^20=1/1024. The union bound controls heights, not the full distribution of search work; one realization may still be unfavorable.

P5. Arbitrary merging can move lists of sizes 1 through n-1 for quadratic total. Smaller-list moves at least double the moved element's component, limiting each element to log n moves. The deeper alpha bound applies to forests with specified compression/linking, not to this list argument.

P6. Changed flags are true,true,true,false,false. Final components are {0,1,2,3}, {4}, {5}, count 3. Root sizes are 4,1,1; representatives are implementation choices. Nonroot size slots are not authoritative component sizes.

P7. Connectivity after each insertion is true, after deleting one copy still true, after deleting the final copy false. Ordinary DSU has no split information. Reverse-time processing must know the final graph and each edge's active multiplicity so it unions only when reverse processing restores presence.

P8–P14: heaps and amortization

P8. Degrees 0,2,3 meld with 0,1; carries through 0,1,2,3 create a single degree-4 root, 16 nodes. Destructive meld transfers ownership and empties the donor. Later donor insertion must not appear in the receiver. Carry-only insertion has its root-count proof; scanning all roots on every insert adds work not paid solely by the number of links.

P9. Potential is 11, then 12 after insertion. Marked-node cuts release potential while adding roots. Degree bounds control consolidation, not arbitrary tree height. Dijkstra's stated benefit needs O(V) extractions and O(E) live-handle decreases under nonnegative weights; duplicate-entry implementations have different counts.

P10. First pass links 7/3 and 8/2, leaving 6. Second pass links 2 with 6, then 3 with the resulting root 2. Final minimum is 2. Local cut/link work can influence later delete-min cost; it is not by itself a constant amortized decrease-key proof for every pairing variant.

P11. n=9: writes 9, copies 15, total 24, capacity 16. n=17: writes 17, copies 31, total 48, capacity 32. Copied powers of two sum to less than 2n, giving total less than 3n. Allocation/zeroing and runtime overheads are excluded from this abstract ledger; including them needs a stated model.

P12. Near half/full thresholds, an append can grow capacity c to 2c, then a delete can shrink it back; repeating copies Θ(c) per pair. Grow at full and shrink at one-quarter full to half capacity leaves Θ(c) size changes before the next opposite resize, except bounded small-capacity cases. This separation motivates a new proof; it is not supplied by the append-only theorem.

P13. Actual primitive total is 3+6+3=12. Charge enqueues 3 and dequeues 1, or use Phi=2*len(In). Each transferred item requires two primitives. Phi=len(In) leaves k unpaid for a transfer of k, so it does not give the asserted constant potential charge under this model.

P14. Actual cost is 25+10-3=32. Nonnegative final potential only lets one upper-bound actual by charges plus initial potential; ignoring the initial 10 would understate that bound. Starting at zero is convenient, not mandatory.

P15–P20: randomness, ranges and history

P15. Priorities 40,10,30 give root key 2 with children 1,3; priorities 10,20,30 give a right chain from 1. Keys follow BST order, priorities min-heap order. Define ties explicitly. Logarithmic expectations require the relevant independent random-priority model; merge requires all left-tree keys below all right-tree keys.

P16. Approximate m≈9585.1, choose 9586; k≈6.64, choose 7; payload 1199 bytes. Distinct-key overload can increase occupancy; reinserting the same key sets the same bits. With one bit every query becomes positive after one insertion, so exact confirmation is essential. Stable encoding/hashes, retained bits and completed insertion are among the no-false-negative conditions.

P17. Cells excluding unused zero start [1,3,3,10], then become [1,5,3,12]. Prefix(3)=8 and sum [1,3)=7. Cell i covers external [i-lowbit(i),i); internal zero has lowbit zero and cannot advance an update. Prefix minima lack the inverse operation needed to remove the preceding prefix.

P18. Sum action is a*S+b*length; new-after-old tags compose as (a2*a1,a2*b1+b2). Assign 5 then add 3 yields constant 8; reversing yields constant 5. Mixed fixture becomes [1,4,-1,-1], total 3 and [1,3) sum 3. Identity (1,0) differs from assignment-zero (0,0).

P19. Version sums are 10,18,5. Modified paths are new; untouched sibling subtrees can share identity. Each fixed-size balanced-tree update allocates O(log(n+1)) nodes plus one version root entry. Recheck every old range after each fork; inspecting only the newest total misses corruption of history.

P20. rank(3)=2 and select(2)=3. Packed bits reduce payload but need additional indexing or scanning to answer rank. Tree-shape encodings do not include arbitrary keys/values. A contiguous scan's O(1+n/B) transfer bound assumes the specified block/ideal-cache model, not every hardware behavior.

Repair protocol

Classify the failure as API, representation, metadata, ownership, update order, history, probability model or cost model. Keep the shortest reproducer, repair the invariant and solve a fresh sequence without the key. Use competencies to decide what needs rechecking; do not replace missing reasoning with more timings.