This project focuses on research issues concerning integer based algorithms in which each word is capable of storing only a w-bit integer. The notion of the integer based computation differs from the traditional comparison based computation in that the model is more realistic and practical. The goals of this project are: (1) To study and compare comparison based computation and integer based computation and to develop methodologies, paradigms, strategies and techniques for designing integer based algorithms. (2) To quest for the ultimate limit of integer based computation and to discover algorithms(resp. lower bounds) of complexity that matches or approaches the lower (resp. upper) bound for fundamental problems such as sorting and searching. (3) To investigate and refine methods for designing integer based algorithms for a wide range of computational problems, e.g. graph problems and problems in algebra. (4) To investigate and propose integer based algorithms which are not only fast in big-O notion of complexity but also having a simpler structure, more intuitive and more practical.
Sorting is probably the most basic and fundamental problem in algorithm design. Sorting provides one of the most basic building blocks for the design of many other algorithms. With the speedup of the sorting algorithm, many other algorithms can be speeded up. In the past comparison sorting was used as one of the major tools for the design of algorithms for many problems. As fast integer sorting algorithms are discovered they can be used to replace comparison sorting in many situations. The techniques invented in the design of fast sorting and searching algorithms can be applied to the algorithm design for many other problems including minimum spanning tree, shortest path, network flow, etc.
Sorting and searching are problems encountered in many science and engineering problems. For example, sorting has been used in database design, computer graphics, computational geometry, network management, computational robotics, data mining, data warehouse, etc., etc.. Due to the vast wide applicability of sorting and searching, the impacts of fast integer sorting and searching algorithms are huge. Sorting and searching also serve as a basic vehicle for the education of computation for undergraduate and graduate students. Discovering fast integer sorting and searching algorithms can benefit this purpose. The simple structured integer sorting and searching algorithms can be lectured in the undergraduate courses and advanced integer sorting and searching algorithms can be lectured in graduate level courses. Education with integer sorting and searching algorithms will present to the students the common techniques in constructing an efficient algorithm.
