Accession Number:

ADA061627

Title:

Decomposable Searching Problems.

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1978-10-01

Pagination or Media Count:

15.0

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 preprocessingquery 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

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE