ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 17 Issue 4, Oct. 1970

An Analysis of Some Graph Theoretical Cluster Techniques
J. Gary Augustson, Jack Minker
Pages: 571-588
DOI: 10.1145/321607.321608
Several graph theoretic cluster techniques aimed at the automatic generation of thesauri for information retrieval systems are explored. Experimental cluster analysis is performed on a sample corpus of 2267 documents. A term-term similarity...

A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures
Hiroshi Akima
Pages: 589-602
DOI: 10.1145/321607.321609
A new mathematical method is developed for interpolation from a given set of data points in a plane and for fitting a smooth curve to the points. This method is devised in such a way that the resultant curve will pass through the given points...

Computer Interval Arithmetic: Definition and Proof of Correct Implementation
Donald I. Good, Ralph L. London
Pages: 603-612
DOI: 10.1145/321607.321610
A definition is given of computer interval arithmetic suitable for implementation on a digital computer. Some computational properties and simplifications are derived. An ALGOL code segment is proved to be a correct implementation of the...

Pseudo-Runge-Kutta Methods of the Fifth Order
William B. Gruttke
Pages: 613-628
DOI: 10.1145/321607.321611
A family of fifth-order pseudo-Runge-Kutta methods for the numerical solution of systems of ordinary differential equations is presented. A procedure for determining an “optimal” set of parameters is given, and several examples are...

A Method for Solving Large Matrix Equations Reduced From Fredholm Integral Equations of the Second Kind
Masahiro Hashimoto
Pages: 629-636
DOI: 10.1145/321607.321612
The method of reducing a Fredholm integral equation of the second kind to a matrix equation and then inverting the matrix is well suited to a machine computation. The number of the dimension of the matrix equation is desired to be large for a...

Accumulation of Round-Off Error in Fast Fourier Transforms
Toyohisa Kaneko, Bede Liu
Pages: 637-654
DOI: 10.1145/321607.321613
The fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier coefficients with a substantial time saving over conventional methods. The finite word length used in the computer causes an error in computing the Fourier...

Efficiency of a Procedure for Near-Minimax Approximation
L. F. Shampine
Pages: 655-660
DOI: 10.1145/321607.321614
A procedure using the minimax polynomial fit of degree n on the set of extrema of the Chebyshev polynomial Tn+1 is examined for its effectiveness in generating near-minimax fits on [-1, 1]....

Error Bounds for Zeros of a Polynomial Based Upon Gerschgorin's Theorems
Brian T. Smith
Pages: 661-674
DOI: 10.1145/321607.321615
Given N approximations to the zeros of an Nth-degree polynomial, N circular regions in the complex z-plane are determined whose union contains all the zeros, and each connected...

Necessary and Sufficient Conditions for Dynamic Programming of Combinatorial Type
P. Bonzon
Pages: 675-682
DOI: 10.1145/321607.321616
A general formulation of discrete deterministic dynamic programming is given. This definition is obtained formally by derivation of a simplified algorithm from a general algorithm, and gives simultaneously the class of concurrent problems....

Statistical Properties of the Buddy System
Paul W. Purdom, Jr., Stephen M. Stigler
Pages: 683-697
DOI: 10.1145/321607.321617
The utilization of space and the running speed of the buddy system are considered Equations are derived that give various statistical properties of the buddy system. For the bottom level with Poisson requests and exponential service times the...

The Unit Proof and the Input Proof in Theorem Proving
C. L. Chang
Pages: 698-707
DOI: 10.1145/321607.321618
A resolution in which one of the two parent clauses is a unit clause is called a unit resolution, whereas a resolution in which one of the two parent clauses is an original input clause is called an input resolution. A unit (input) proof is a...

On the Efficiency of Algorithms
David Pager
Pages: 708-714
DOI: 10.1145/321607.321619
A definition is given of the efficiency of an algorithm considered as a whole. This immediately raises the question of whether it is possible to find the most efficient or “optimum” algorithm. It is shown that an optimization problem...

The Generation of Optimal Code for Arithmetic Expressions
Ravi Sethi, J. D. Ullman
Pages: 715-728
DOI: 10.1145/321607.321620
The problem of evaluating arithmetic expressions on a machine with N ≥ 1 general purpose registers is considered. It is initially assumed that no algebraic laws apply to the operators and operands in the expression. An...

The Equivalence Problem of Simple Programs
D. Tsichritzis
Pages: 729-738
DOI: 10.1145/321607.321621
Many problems, some of them quite meaningful, have been proved to be recursively unsolvable for programs in general. The paper is directed toward a class of programs where many decision problems are solvable. The equivalence problem has been...

Errata: `` On the Periodic Representations and the Reducibility of Periodic Automata''
Jerzy W. Grzymala-Busse
Page: 739
DOI: 10.1145/321607.321622