g-Off.net | Geoffrey Foster

COMP 5408 – Advanced Data Structures

Simple methods of data structure design and analysis that lead to efficient data structures for several problems. Topics include randomized binary search trees, persistence, fractional cascading, self-adjusting data structures, van Emde Boas trees, tries, randomized heaps, and lowest common ancestor queries.

This was an awesome course that was both fun and loaded with useful information. I would highly recommend it. There were three assignments (although two of them were combined together) where we had the option of choosing between theory or implementation. I chose to code. The first assignment involved implementing a Treap and the second/third were implementing a Splay-tree, a Suffix-tree and a "Working Set".

For the final project I examined four different possible underlying data structures that could be used for a priority queue. They were the Pairing Heap, the Min-Heap, a Randomized Meldable Queue and a Heater

View the paper: Priority Queue Implementations Experimental Analysis (it's not all that interesting or surprising)

View/Download the Source-code:

Pairing Heap
pairing_heap.h
pairing_heap.c

Min Heap
min_heap.h
min_heap.c

Randomized Meldable Queue
randomized_meldable_queue.h
randomized_meldable_queue.c

Heater
heater.h
heater.c