Problem Set 5

Due Tuesday, May 26 at 1:00 pm Pacific

This assignment may be completed individually or with a partner.

This problem set is all about amortized efficiency and how to design powerful data structures that fit into that paradigm. In this problem set, you’ll get to play around with the data structures we saw in lecture, plus a few others from earlier. By the time you’ve finished this problem set, you’ll have an excellent handle on how amortization works and how to think about problem-solving in a new way.

$\LaTeX$ Template

Assignments are required to be typed. We've provided a $\LaTeX$ template for this assignment, though you're not required to use it.

🖋 PS5 $\LaTeX$ Template

Problem One: Stacking the Deque

A deque (double-ended queue, pronounced “deck”) is a data structure that acts as a hybrid between a stack and a queue. It represents a sequence of elements and supports the following four operations:

deque.push_front(x), which adds $x$ to the front of the sequence.
deque.push_back(x), which adds $x$ to the back of the sequence.
deque.pop_front(), which removes (but does not return) the front element of the sequence.
deque.pop_back(), which removes (but does not return) the last element of the sequence.

Design a deque that internally is implemented using three stacks such that each of the above operations takes amortized time $O(1)\text.$ You may not use any auxiliary or helper data structures other than these stacks.

In writing up your answer, avoid pseudocode unless absolutely necessary. Then, define a potential function $\Phi$ and use the potential method to argue that the amortized cost of each operation is $O(1)\text.$ You do not need to argue correctness. We’re expecting your amortized analysis to be written up in a manner similar to the formal analyses we did in lecture of the two-stack queue, dynamic array, and B-tree construction algorithm.

Problem Two: 2-Fibonacci Heaps

Consider the following variation of Fibonacci heaps, which we'll call 2-Fibonacci heaps. These work exactly the same way as a regular Fibonacci heap, except that each node is allowed to lose at most two children due to decrease-key operations before it must be cut from its parent.

Let's define a 2-maximally-damaged tree of order $k$ to be a binomial tree of order $k$ that has lost as many nodes as possible, without cutting any direct children of the root, and subject to the restriction that each node in the tree may lose at most two children.

Draw a 2-maximally-damaged tree of order 7.

The golden ratio, which appears in the analysis of Fibonacci heaps, is the positive real number $\varphi \approx 1.618\dots$ that satisfies $\varphi^2 = 1 + \varphi\text.$ To analyze 2-Fibonacci heaps, we will need to use the 2-golden ratio, the real number $\psi \approx 1.457\dots$ that satisfies $\psi^3 = 1 + \psi^2\text.$ (Its exact formula is $\psi = \frac{1}{3} \left( 1 + \sqrt[3]{\frac{1}{2} \left( 29 - 3 \sqrt{93} \right)} + \sqrt[3]{\frac{1}{2} \left( 29 + 3 \sqrt{93} \right) } \right)\text,$ in case you're curious, but you shouldn't need to use this fact.)

Let $d_k$ denote the number of nodes in a 2-maximally-damaged tree of order $k\text.$ Prove that $\psi^k \le d_k \le \psi^{k+1}$ for all $k \ge 0\text.$

Compare the asymptotic and actual amortized costs of the enqueue, extract-min, and decrease-key operations between Fibonacci heaps and 2-Fibonacci heaps. Based on your analysis, in which situations would a Fibonacci heap be preferable, and when would a 2-Fibonacci heap be preferable?

Problem Three: Meldable Heaps with Addition

Meldable priority queues support the following operations:

new-pq(), which constructs a new, empty priority queue;
pq.enqueue(v, k), which inserts element $v$ with key $k\text;$
pq.find-min(), which returns an element with the least key;
pq.extract-min(), which removes and returns an element with the least key; and
meld(pq₁, pq₂), which destructively modifies priority queues $pq_1$ and $pq_2$ and produces a single priority queue containing all the elements and keys from $pq_1$ and $pq_2\text.$

Some graph algorithms also require the following operation:

pq.add-to-all(Δk), which adds $\Delta k$ to the keys of each element in the priority queue.

It’s possible to implement add-to-all without touching all the items in a priority queue.

Show how to modify an eager (non-lazy) binomial heap so that new-pq, enqueue, find-min, extract-min, and add-to-all each run in worst-case $O(\log n)$ time and the meld operation runs in time $O(\log m + \log n)\text,$ where $m$ and $n$ are the sizes of the respective heaps. Briefly argue correctness.

A note on this problem: if it weren’t for meld, you could support add-to-all in time $O(1)\text.$ (Do you see why?) We recommend that, from the beginning, you think about how you’d meld together two different heaps that have had different $\Delta k\text{'s}$ added to them.

Show how to modify a lazy binomial heap so that new-pq, enqueue, find-min, meld, and add-to-all all run in amortized time $O(1)$ and extract-min runs in amortized time $O(\log n)\text.$ Briefly argue correctness, then do an amortized analysis with the potential method to prove runtime bounds. Some hints:
1. Try to make all operations have worst-case runtime $O(1)$ except for extract-min. Your implementation of extract-min will probably do a lot of work, but if you've set it up correctly the amortized cost will only be $O(\log n)\text.$ This means, in particular, that you will only propagate the $\Delta k\text{'s}$ through the data structure in extract-min.
2. If you only propagate $\Delta k\text{'s}$ during an extract-min as we suggest, you'll run into some challenges trying to meld two lazy binomial heaps with different $\Delta k\text{'s.}$ To address this, we recommend that you change how meld is done to be even lazier than the lazy approach we discussed in class. You might find it useful to construct a separate data structure tracking the melds that have been done and then only actually combining together the heaps during an extract-min.
3. Depending on how you set things up, to get the proper amortized time bound for extract-min, you may need to define your potential function both in terms of the structure of the lazy binomial heaps and in terms of the auxiliary data structure hinted at by the previous point.
In your writeup, don’t just describe the final data structure all at once. Instead, walk us through the design. Explain why each piece is there, why it’s needed, and how the whole structure comes together. Briefly argue correctness, and prove that you meet the required amortized time bounds by defining a potential function $\Phi$ and working out the amortized costs of each operation.

We’re expecting your amortized analysis to be written up in a manner similar to the formal analyses we did in lecture of the two-stack queue, dynamic array, and B-tree construction algorithm.

Once you finish this last problem, reflect on just how far you've come over the course of the quarter. Did you imagine you'd be able to create something like this?

Problem Four: Splay Trees in Practice

In lecture, we talked about a number of wonderful theoretical properties of splay trees. How well do they hold up in practice? In this problem, you’ll find out!

In class we presented bottom-up splaying where, after each query is performed, we applied a series of rotations from the queried node up to the root. This approach is a messy in practice because we need to keep track of the access path. There are a few ways to do this, all of which have drawbacks:

We could have each node store a pointer back up to its parent. This increases the overhead associated with each node, which impacts cache-friendliness and reduces the maximum size of the trees that we can hold in memory. Plus, it requires additional pointer reassignments during rotations.
We could implement splaying recursively, using the call stack to remember the nodes we’ve visited. This can cause problems with stack overflows if the tree gets too imbalanced and we do an extremely deep lookup.
We could maintain a dynamically-allocated list of the nodes that we visited during a lookup. This requires extra memory allocations per lookup, which slows down the implementation.

In this problem, we’d like you to use the top-down splaying procedure described in Section 4 of Sleator and Tarjan’s paper on splay trees. Top-down splaying works by reshaping the tree during the top-down tree search and requires only $O(1)$ auxiliary storage space. While giving the same asymptotic time bounds as bottom-up splay, top-down splaying is faster in practice. As a heads-up, the resulting tree shape after an operation is not the same when doing top-down versus bottom-up splaying; keep this in mind as you are implementing this variation.

Copy the assignment starter files from /usr/class/cs166/assignments/ps5/ and extract them somewhere convenient. There are a number of files there, of which you should only need to edit the SplayTree.h and SplayTree.cpp file, plus (optionally) SplayTreeTests.cpp. These starter files contain a partial implementation of a SplayTree type. Finish the implementation by implementing the contains member function. This should perform a lookup and a top-down splay.

You’ll need to do a little legwork to figure out top-down splaying from Sleator and Tarjan’s description. As with most research papers, the provided pseudocode skips over some important $\text{C++}$-level details, which you will need to figure out by looking at the diagrams and through thorough testing. Don’t just translate the code directly; draw some pictures to make sure you understand how top-down splaying works and what, conceptually, it’s trying to accomplish. You might want to look at the operational description of the rotate-to-root heuristic as a starting point for understanding how top-down splaying works.

There are two versions of top-down splaying presented in Section 4. Implement the full rather than the simplified version of top-down splaying, since the simplified version is slower in practice.

You can test your implementation by running ./run-tests. Once you’ve implemented everything, edit the Makefile to crank the optimizer up to maximum (set the flags -Ofast -march=native), rebuild everything, and run ./time-tests. Those tests include sequential and reverse sequential access (great for trees with the dynamic finger property), tests doing lookups focused on small batches of elements (great for trees with the working set property), tests where lookups tend to be close to previous lookups (also great for trees with the dynamic finger property), tests over uniform distributions (great for trees with the balance property), and tests over Zipfian distributions (great for trees with the entropy property). Do those numbers surprise you? See anything interesting there?

For full credit, your solution should compile cleanly (-Wall -Werror), should run cleanly under valgrind on myth, and should be easy to read.