Decomposable Searching Problems.
Abstract
Although searching is one of the most important problems in computer science and many particular results are known for searching problems, there really is no satisfactory, 'theory of searching.' In this paper we propose a first step toward such a theory by defining the class of decomposable searching problems and them proving three theorems about problems in this class. These theorems are all of the form 'given a data structure D for a decomposable searching problem we can transform D into a new data structure D' for a related problem'. The correctness and complexity analysis of D are then used to establish the correctness and complexity of D'. We present transforms for converting a static structure into a dynamic structure, for adding 'range variables' to queries, and for making preprocessing/query time tradeoffs. These transforms have already been used to develop a number of best known 'theoretical' algorithms, and promise to be an important tool in software engineering. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1978
- Accession Number
- ADA061627
Entities
People
- Jon Louis Bentley
Organizations
- Carnegie Mellon University