Practice Solutions and Feedback

Use after an attempt. Equivalent correct derivations and heap layouts are welcome; do not grade incidental implementation choices as if they were the contract.

P1

There are three strict inversions: A over B, A over D, C over D. Insertion passes give (1,B),(3,A),(3,C),(2,D), unchanged at the next key 3, then (1,B),(2,D),(3,A),(3,C). Three shifts remove those inversions. The strict comparison never moves an earlier equal key past a later one. Two tagged equal keys suffice to expose the non-strict version: (1,A),(1,B) becomes B,A.

P2

The final key regions are [1], [2,2,2], [3]; order within strict regions need not be stable. During partition, low/equal/unknown/high regions have boundaries lo,lt,i,gt,hi. Every step reduces gt-i. A swap from the unknown right end requires reexamining i. All-equal input finishes in one linear three-way pass. Lomuto sending equals to one side can recurse on n-1 entries each time, giving quadratic work despite randomized pivot indices.

P3

Six permutations require at least six leaves. Height two permits only four, so some path needs at least three comparisons. No distribution is required for this worst-case argument; uniformity enters the average-depth argument. The multiset has 4!/(2!2!)=6 distinguishable key orders. Treat payload identities and any stability requirement separately from distinct key orders.

P4

Counts [1,1,2], starting offsets [0,1,2]; placements A→2,B→0,C→3,D→1. Output B,D,A,C preserves tie order. Counting costs Theta(n+R) and O(n+R) auxiliary slots for this stable version. Ones pass [21,11,12,22], tens pass [11,12,21,22]. LSD costs Theta(d(n+b)), O(n+b) auxiliary slots. With d=ceil(k/w) at least one pass is required for nonempty fixed-width keys; processing all n records already rules out a sublinear full-sort claim.

P5

Ranges: 0→(0,0), 2→(1,4), 3→(4,4), 5→(5,5). Empty input returns (0,0). For [2], target 2 returns (0,1), target 1 (0,0), target 3 (1,1). Lower bound excludes < target below lo and >= target from hi onward; upper bound excludes <= target below lo and > target from hi onward. Sortedness preserves both; hi-lo strictly decreases. Two searches use O(log(n+1)) random accesses, whereas a sortedness scan adds Theta(n) work per query.

P6

The possible two-group splits have maxima 10,8,9. Minimum is 8 at [4,2] | [3,5]. Feasibility at threshold B can greedily fill a group until the next item would exceed B, then start another, rejecting any item>B. For nonnegative sizes this greedy prefix extends at least as far as any feasible first group; apply the argument inductively to minimize group count. Any feasible partition remains feasible at a larger B, proving monotonicity. Search integer B from max task=5 through total=14, with O(n log(total-max+2)) arithmetic work. With negatives, [6,-2] can fit threshold 4 even though 6 alone exceeds it; the rejection and greedy-prefix proof no longer apply.

P7

Pivot 1 removes two ranks in the equal region; rank 2 is the minimum of the remaining strict-high region and equals 4. Phase analysis charges an expected constant number of O(m) attempts until a pivot leaves at most about 3m/4 entries. Summing phase costs geometrically gives expected O(n). A fixed seed makes a run repeatable without proving a worst-case bound. Equal-key input ends after one three-way partition. The lab's copy costs O(n) storage and time even if the partition itself is in place.

P8

Sort once: O(n log n+q) time and implementation-dependent sort storage; each rank lookup is O(1). Independent quickselect queries: O(qn) expected time, O(n) copy storage reused per query in the nonmutating version. Dynamic sorted arrays can pay O(n) per insertion. An augmented balanced search tree can give O(log n) updates and rank/select plus O(log n+r) range output with a suitable iterator. A plain balanced tree needs subtree sizes for rank/select. Neither an arbitrary numeric crossover nor an omitted output cost is justified.

P9

Let I_y be the collision indicator for each stored y. Linearity gives E[sum I_y]=sum Pr[h(y)=h(x)]<=n/m. The family is randomly selected independently of these fixed keys; the indicators need not be mutually independent to sum their expectations. At capacity 16, keys 0,16,32,48 have load 1/4 but collide under modulo hashing. The chaining argument does not automatically establish a linear-probing bound.

P10

Faulty insertion stores the updated 8 at deleted slot 0 and leaves old 8 at 1. Deleting the new one can expose the stale value. Correct insertion continues to slot 1 and updates there, so final get(8) raises KeyError. First delete: live 3→2, used remains 3. Update changes neither. Second delete: live 2→1, used remains 3. A new key reusing a tombstone increments live but not used; using a never-used slot increments both. Keys 7,15,23 occupy 7,0,1 and exercise the same logic across the wraparound boundary.

P11

Key 8 belongs at home 0 with capacity 8, but home 8 with capacity 16. Copying its old position can put an empty slot before it on its new probe path. Rehash live entries. Geometric capacity sums bound allocated slots, not quadratic probes from a colliding reinsertion sequence. If growth occurs just above half full and shrinking just below half full, a growth can leave the new table close to the shrink threshold, causing repeated expensive changes. Use separated bands, such as growing when full and shrinking below one quarter, with a minimum capacity; account for the intervening linear number of operations. The lab map does not shrink and uses a deterministic hash, so no expected-O(1) claim follows.

P12

One heap is [1,3,1,5]. Pop returns 1; push 0; draining returns [0,1,3,5]. The count of nodes with height at least h is at most floor(n/2^h). Its sum over h>=1 is less than n, bounding total downward levels in heapify. Each level has constant comparison work. A lone left child satisfies 2i+1<n and 2i+2>=n. Choosing a larger child can leave the new parent larger than its other child, violating heap order immediately.

P13

There are 25 initial runs and two merge passes: 25→5→1. Each materialized stage reads and writes 100 GB, giving 600 GB including run generation. Streaming final output removes the final 100 GB disk write in this model: 500 GB. Account for input/output buffers, auxiliary sort space, heap records, decoded keys, file handles and runtime overhead. These are byte-model estimates, not measured times.

P14

Use (timestamp,unique_monotone_sequence,payload) so equal timestamps use arrival order without comparing payloads. Indexed cancellation needs identity→index mapping updated on every heap swap. Lazy cancellation needs identity/version validation on pop, monotonically distinct versions, and cleanup before stale entries violate the memory budget. Reinsertion must not revive an older version. State costs in physical entries for lazy heaps, not only live jobs.

P15

The abstract costs are Theta(4(n+256)) and Theta(2(n+65536)), with O(n+256) versus O(n+65536) auxiliary slots for stable counting passes. They do not directly price cache effects or convert to seconds. A fixed-width two's-complement sign-bit flip maps signed order to unsigned order. The bit width must be fixed and encoding specified. IEEE negative values, signed zero, infinities and NaNs require a separate ordering policy; an exponent-XOR shortcut is not the signed-integer rule.

P16

For merge, each nonempty stream contributes its smallest unread value. Removing the smallest head is therefore safe, and advancing only that stream preserves the invariant. Time O(K+N log(K+1)), extra state O(K), excluding collected output. For largest-K, keep a min-heap of at most K processed values; replace its minimum only when a larger value arrives. K=0 returns no retained values; if K exceeds the processed count, keep all. Heap contents need not be sorted; sorting the final K values adds O(K log K). Tests against every prefix catch errors that a single final-answer test can miss.