
Accession Number : ADA118814
Title : Algorithmic Complexity. Volume II.
Descriptive Note : Final technical rept. Jun 79Aug 81,
Corporate Author : RHODE ISLAND UNIV KINGSTON DEPT OF COMPUTER SCIENCE AND STATISTICS
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 NPcomplete. 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