September 1977 - Vol. 20 No. 9
Features
The framework for research in the theory of complexity of computations is described, emphasizing the interrelation between seemingly diverse problems and methods.…
Logic and programming languages
Logic has been long interested in whether answers to certain questions are computable in principle, since the outcome puts bounds on the possibilities of formalization.…
The GRE advanced test in computer science
This report describes the Advanced Test in Computer Science which was recently introduced in the Graduate Record Examination Program. The GRE program is described in…
An analysis of inline substitution for a structured programming language
An optimization technique known as inline substitution is analyzed. The optimization consists of replacing a procedure invocation by a modified copy of the procedure…
Hardware estimation of a process’ primary memory requirements
A minor hardware extension the Honeywell 6180 processor is demonstrated to allow the primary memory requirements of a process in Multics to be approximated. The…
Some new upper bounds on the generation of prime numbers
Given an integer N, what is the computational complexity of finding all the primes less than N? A modified sieve of Eratosthenes using doubly linked lists yields an…
Pagination of B*-trees with variable-length records
A strategy is presented for pagination of B*-trees with variable-length records. If records of each length are uniformly distributed within the file, and if a wide…