ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 21 Issue 1, Jan. 1974

On a Statistical Model of Strand and Westwater for the Numerical Solution of a Fredholm Integral Equation of the First Kind
David G. Herr
Pages: 1-5
DOI: 10.1145/321796.321797
A statistical model is presented which is useful in the solution of a Fredholm integral equation of the first kind and equivalent to one proposed by Strand and Westwater. The model and the related problem presented here are familiar to...

Some a Posteriori Error Bounds in Floating-Point Computations
Nai-kuan Tsao
Pages: 6-17
DOI: 10.1145/321796.321798
Efficiently computable a posteriori error bounds are attained by using a posteriori models for bounding roundoff errors in the basic floating-point operations. Forward error bounds are found for inner product and polynomial evaluations. An...

Processing Times for Segmented Jobs with I/O Compute Overlap
L. W. Cotten, A. M. Abd-Alla
Pages: 18-30
DOI: 10.1145/321796.321799
Compute-output processing times are determined for n-segment jobs that are preloaded into main storage and processed with overlap. A queueing model with tandem servers is utilized for the performance analysis. In particular, the...

Some Distribution-Free Aspects of Paging Algorithm Performance
P. A. Franaszek, T. J. Wagner
Pages: 31-39
DOI: 10.1145/321796.321800
The topic of this paper is a probabilistic analysis of demand paging algorithms for storage hierarchies. Two aspects of algorithm performance are studied under the assumption that the sequence of page requests is statistically independent: the...

Finding Optimal Demand Paging Algorithms
Giorgio Ingargiola, James F. Korsh
Pages: 40-53
DOI: 10.1145/321796.321801
A cost is defined for demand paging algorithms with respect to a formal stochastic model of program behavior. This cost is shown to exist under rather general assumptions, and a computational procedure is given which makes it possible to...

Some Aspects of Hierarchical Memory Systems
Debasis Mitra
Pages: 54-65
DOI: 10.1145/321796.321802
A class of demand paging algorithms for some two-level memory hierarchies is analyzed. The typical memory hierarchy is comprised of the core and a backing device. A distance matrix characterizes the properties of the latter device. The sequence...

Scheduling for Minimum Total Loss Using Service Time Distributions
Kenneth C. Sevcik
Pages: 66-75
DOI: 10.1145/321796.321803
An analytic model of a single processor scheduling problem is investigated. The scheduling objective is to minimize the total loss incurred by a finite number of initially available requests when each request has an associated linear loss...

Some Topics in Code Optimization
Christopher Earnest
Pages: 76-102
DOI: 10.1145/321796.321804
Many compilers for higher order languages attempt to translate the source code into “good” object code. Cocke and Schwartz have described an algorithm for discovering when the computation of an expression is redundant (common), and...

Simulating Stable Stochastic Systems, I: General Multiserver Queues
Michael A. Crane, Donald L. Iglehart
Pages: 103-113
DOI: 10.1145/321796.321805
A technique is introduced for analyzing simulations of stochastic systems in the steady state. From the viewpoint of classical statistics, questions of simulation run duration and of starting and stopping simulations are addressed. This is...

Simulating Stable Stochastic Systems, II: Markov Chains
Michael A. Crane, Donald L. Iglehart
Pages: 114-123
DOI: 10.1145/321796.321806
A technique for simulating GI/G/s queues is shown to apply to simulations of discrete and continuous-time Markov chains. It is possible to address questions of simulation run duration and of starting and stopping simulations because of the...

An Implementation of the Model Elimination Proof Procedure
S. Fleisig, D. Loveland, A. K. Smiley, III, D. L. Yarmush
Pages: 124-139
DOI: 10.1145/321796.321807
The model elimination (ME) and resolution algorithms for mechanical theorem-proving were implemented so as to maximize shared features. The identical data structures and large amount of common programming permit meaningful comparisons when the...

Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems
Walter H. Kohler, Kenneth Steiglitz
Pages: 140-156
DOI: 10.1145/321796.321808
Branch-and-bound implicit enumeration algorithms for permutation problems (discrete optimization problems where the set of feasible solutions is the permutation group Sn) are characterized in terms of a...

A Theorem in the Theory of Compromise Merge Methods
P. S. Kritzinger, J. W. Graham
Pages: 157-160
DOI: 10.1145/321796.321809
Let r be the total number of cycles required to complete a compromise merge of a given number of initial strings. Define row vectors mr-j and...

On the Number of Multiplications for the Evaluation of a Polynomial and Some of Its Derivatives
Mary Shaw, J. F. Traub
Pages: 161-167
DOI: 10.1145/321796.321810
A family of new algorithms is given for evaluating the first m derivatives of a polynomial. In particular, it is shown that all derivatives may be evaluated in 3n - 2 multiplications. The best previous result...

The String-to-String Correction Problem
Robert A. Wagner, Michael J. Fischer
Pages: 168-173
DOI: 10.1145/321796.321811
The string-to-string correction problem is to determine the distance between two strings as measured by the minimum cost sequence of “edit operations” needed to change the one string into the other. The edit...