Accession Number : ADA118814

Title :   Algorithmic Complexity. Volume II.

Descriptive Note : Final technical rept. Jun 79-Aug 81,


Personal Author(s) : Lamagna,Edmund A ; Bass,Leonard J ; Anderson,Lyle A ; Bunker,Ralph E ; Janus,Philip J

PDF Url : ADA118814

Report Date : Jun 1982

Pagination or Media Count : 353

Abstract : The objective of this study was to conduct applied research directed toward understanding the relationship between the complexity or efficiency of algorithms and the overall quality of computer software. The final report is presented in a two volume series consisting of a total of eight parts. This volume, containing parts 3 through 8 describes the results of several technical investigations which are conducted. Part 3 is a tutorial on computational algebra, illustrating the nature of research in the area of algorithm analysis and computational complexity. Part 4 develops a systematic approach to the analysis of algorithms. Part 5 is an experimental analysis of a fast, new sorting method called DPS (distributive partitioning sorting). Part 6 applies order statistics to investigate the expected quality of several approximation algorithms for the Euclidean traveling salesman problem, known to be NP-complete. Part 7 presents a survey of data base access methods for both univariate and multivariate range queries. Part 8 describes an experimental evaluation of the frame memory model of a data base structure.

Descriptors :   *Algorithms, *Computer program reliability, Computer programs, Computations, Algebra, State of the art, Interrogation, Multivariate analysis, Machine translation, Loops, Subroutines, Semantics, Probability distribution functions, Sorting, Order statistics, Data bases, Access

Subject Categories : Statistics and Probability
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE