Amortization and Persistence via Lazy Evaluation

Prev: Fundamentals of Amortization Next: Eliminating Amortization

Prev: Fundamentals of Amortization Next: Eliminating Amortization

6.1 Execution Traces and Logical Time

Exercises

Exercise 6.1

Draw an execution trace for the following set of operations. Annotate each node in the trace with the number of logical futures at that node.

val a = snoc (empty, 0)
val b = snoc (a, 1)
val c = tail b
val d = snoc (b, 2)
val e = c ++ d
val f = tail c
val g = snoc (d, 3)

6.3 The Banker’s Method

Exercises

Exercise 6.2

Suppose we change the invariant from $|f|>|r|$ to $2|f|>|r|$.

1. Prove that the $O(1)$ amortized bounds still hold.
2. Compare the relative performance of the two implementations on a sequence of one hundred snocs followed by one hundred tails.

6.4 The Physicist’s Method

Exercises

Exercise 6.3

Prove that findMin, deleteMin, and merge also run in $O(\log n)$ amortized time.

Exercise 6.4

Suppose that we remove the lazy keyword from the definitions of merge and deleteMin, so that these functions evaluate their arguments immediately. Show that both functions still run in $O(\log n)$ amortized time.

Exercise 6.5

An unfortunate consequence of suspending the list of trees is that the running time of isEmpty degrades from $O(1)$ worst-case time to $O(\log n)$ amortized time. Restore the $O(1)$ running time of isEmpty by explicitly maintaining the size of every heap.

Rather than modifying this implementation directly, implement a functor SizedHeap, similar to the ExplicitMin functor of Exercise 3.7, that transforms any implementation of heaps into one that explicitly maintains the size.

Exercise 6.6

Show why each of the following proposed “optimizations” actually breaks the $O(1)$ amortized time bounds.

1. Observe that check forces f during a rotation and installs the result in w. Wouldn’t it be lazier, and therefore better, to never force f until w becomes empty?
2. Observe that, during a tail, we replace f with $tl (force f). Creating and forcing suspensions have non-trivial overheads that, even if $O(1)$, can contribute to a large constant factor. Wouldn’t it be lazier, and therefore better, to not change f, but instead merely decrement lenf to indicate that the element has been removed?

Exercise 6.7

Change the representation from a suspended list of lists to a list of streams.

1. Prove the bounds on add and sort using the banker’s method.
2. Write a function to extract the $k$ smallest elements from a sortable collection. Prove that your function runs in no more than $O(k\log n)$ amortized time.

6.5 Lazy Pairing Heaps

6.6 Chapter Notes