Date of Award
Spring 2-1-2022
Document Type
Thesis
First Advisor
Mohammad Obiedat
Second Advisor
Jason Quinones
Abstract
Data structures are an essential part of almost all software programs. The primary operations of most data structures are searching, insertion, deletion, and finding the Kth smallest element. To be of practical use, operations on data structures should be fast and should not use much memory space; in other words, the time and space complexities should not be enormous. This research project provides an algorithm, called FindKth, for the order-statistic operations of finding the ATth smallest element in Lattice Data Structures. In the average case, our algorithm is of time complexity O(n3/2), and it is of time complexity O(n) for small searches. A Lattice Data Structure is a lattice-based structure where the total space of the structure is equal to the number of elements, such as if a group of elements was stored in an array. There is no single definition of an LDS, as many various LDS exist with their structure and definitions. The FindKth algorithm was developed using Obiedat's definition of a Lattice Data Structure and the discussion of different algorithms to sort and search to find values on arrays. This development is to help enhance future discussions in the field of data structure. With the consideration of Lattice Data Structure being cache conscious, this makes a great target to pursue the development of the new algorithm.
Recommended Citation
Mendis, Joseph, "Time-Efficient Algorithm for the Order-Statistic Operations in Lattice Data Structure" (2022). Undergraduate University Honors Capstones. 86.
https://ida.gallaudet.edu/honors_capstones/86
