Suggested Final Project Topics

Why they’re worth studying: We’ve spent a lot of time this quarter focusing on worst-case analyses of

data structures (amortization is a variation on this theme), plus expected performance. The fishspear occu-

pies an interesting place in that its analysis is somewhat output-sensitive (the longer an item is in the fishs-

pear, the more expensive it is to insert it), allowing for a more nuanced understanding of the data struc-

ture. This would be a great launching point for a further exploration of how to analyze data structures be-

yond just thinking about the most pessimal case.

---

 11 / 22

Queaps

The queap is a hybrid between a queue and a heap (hence the name) that’s layered on top of a 2-3-4 tree.

Like the fishspear, the queap’s performance depends on how the data structure actually ends up getting

used. Specifically, the queap has the property that the cost of removing an element depends purely on how

many elements have been in the queap longer than the removed element. This means that if the elements

inserted into the queap are mostly sorted, the runtime will approach that of a queue.