Dave Brandin
Pages 619-620
Special Subcommittee on Self-Assessment
Pages 621-624
The framework for research in the theory of complexity of computations is described, emphasizing the interrelation between seemingly diverse problems and methods. Illustrative examples of practical and theoretical significance …
Michael O. Rabin
Pages 625-633
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. More recently, precise comparisons in the efficiency of
…
Dana S. Scott
Pages 634-641
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 general, and, the events leading to the establishment of the …
Richard H. Austing
Pages 642-645
An optimization technique known as inline substitution is analyzed. The optimization consists of replacing a procedure invocation by a modified copy of the procedure body. The general problem of using inline substitution to minimize …
Robert W. Scheifler
Pages 647-654
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 additional hardware required for this estimate to be computed consists …
David K. Gifford
Pages 655-663
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 algorithm of O
A(N) arithmetic complexity. This upper bound is …
Harry G. Mairson
Pages 664-669
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 distribution of record lengths exists within the file, then this …
Edward M. McCreight
Pages 670-674
Pages 678-680
CACM Staff
Pages 681-682
