Suggested Final Project Topics

Exponential Trees

Fusion trees were the first data structure designed for the transdichotomous machine model that are theo-

retically faster than comparison-based data structures in all cases, but they aren’t the last word on the sub-

ject. The exponential tree provides a way to convert from static integer data structures to dynamic integer

data   structures,   enabling   fast,   deterministic   algorithms   for   integer   sorting   that   are   much   faster   than

O(n log n).

Why they're worth studying: Studying exponential trees would be a great way to dive even deeper into

the worlds of word-level parallelism (along the lines of the fusion tree) and trie-based integer algorithms

(like the y-fast trie). They would also be a great way to study amortized analysis in depth, since the tech-

niques employed there are similar to what was used in y-fast tries and fusion trees.