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