Date of Award

Spring 2-1-2022

Document Type


First Advisor

Mohammad Obiedat

Second Advisor

Jason Quinones


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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.