**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