Advanced Heaps and Amortized Analysis Workshop

Budget 6–9 focused hours for P8–P14. Name the primitive costs and initial state in every proof. Preserve an attempt before feedback.

P8: binomial carries and ownership

Meld heaps of sizes 13 and 3. Trace root degrees and carries; justify final node count. Define destructive meld, self-meld rejection and donor reuse. Explain why an implementation scanning all roots per insert needs a different insertion analysis.

P9: Fibonacci-heap claims

For 5 roots and 3 marked nonroots compute the classical potential, then add one root. Explain how marks pay for cascading cuts and why logarithmic degree does not establish logarithmic height. State the queue operation mix required for Dijkstra's Fibonacci-heap bound.

P10: pairing schedule

Delete-min exposes roots [7,3,8,2,6]. Trace both passes of the classical two-pass merge. Explain why constant local cut/link work does not by itself prove constant amortized decrease-key and why a variant must be named.

P11: arbitrary append prefixes

For n=9 and n=17 derive cumulative write/copy cost and final capacity in the lab model. Prove a less-than-3n bound for every positive prefix and state what costs the model excludes.

P12: shrinking changes the proof

Construct a resize-thrashing sequence for doubling at full capacity and shrinking at half full. Propose separate growth/shrink thresholds and explain why a linear gap in operation count is needed between expensive resizes.

P13: two-stack queue charges

Count each stack push/pop as one primitive. Enqueue three elements, then dequeue three. Give actual counts, a credit account and a potential with correct coefficient. Explain why Phi=len(In) does not give constant charges in this primitive model.

P14: initial potential

Write the telescoping identity with nonzero initial potential. If initial Phi=10, final Phi=3 and summed amortized charges are 25, compute actual cost. Explain why ignoring initial potential understates the possible total.