The need to efficiently store and access data is central to modern computing, and the design and analysis of methods to store and access data constitutes the field of data structures. This project will investigate the discovery of provably best data structures for several fundamental problems, including the dictionary and the priority queue. The dictionary supports the efficient insertion, deletion, and search of ordered data. The priority queue supports insertion and the removal of the minimum element.
Data structures will be designed and analyzed under the paradigm of instance-based optimality. In this model, a data structure's performance on a sequence of operations is evaluated based on how well it compares to the speed of the best structure for that sequence among a naturally-defined class of structures. The classes of structures that will be examined include binary search trees and heaps. Binary search trees and heaps are arguably the most fundamental nontrivial classes of data structures in computer science. Despite their origins at the dawn of computing, a complete understanding of these classes of structures has remained elusive to this day.
Other operations on fundamental data structures will be investigated. The ability to decrease the value of an item in a heap is vital to some algorithms, notably Dijkstra's algorithm for finding single-source shortest paths in a graph. Yet, it is not completely understood what types of structures can support this operation efficiently. Also, there is no known efficient method to support the splitting and merging of dictionaries; one goal of this project is to design a comparison-based dictionary do this in amortized logarithmic time.
