Sign In

Communications of the ACM

Table of Contents


ACM President's Letter: barely started business


A simple linear model of demand paging performance

Predicting the performance of a proposed automatically managed multilevel memory system requires a model of the patterns by which programs refer to the information stored in the memory. Some recent experimental measurements on …

Computation of page fault probability from program transition diagram

An algorithm is given for calculating page fault probability in a virtual memory system operating under demand paging with various memory sizes and replacement rules. A first order Markov model of program behavior is assumed, …

Execution characteristics of programs in a page-on-demand system

h show the execution characteristics of two types of commonly used programs in a large-scale, time-shared computer system. A software monitoring facility built into the supervisor was used for data collection during normal system …

On Lion's counter example for Gotlieb's method for the construction of school timetables

The timetable problem is an essentially discrete problem. Although the discrete problem may have no feasible solution, there may exist a solution to the equivalent continuous problem. An example, is given, for which the nondiscrete …

Copying list structures using bounded workspace

Two new algorithms are presented for list structure copying using bounded workspace. The first, of primarily theoretical interest, shows that without cell tag bits the task can be performed in time n2. The second algorithm, assuming …

Parallelism in tape-sorting

Two methods for employing parallelism in tape-sorting are presented. Method A is the natural way to use parallelism. Method B is new. Both approximately achieve the goal of reducing the processing time by a divisor which is the …

A study of computer use in a graduate school of business


Graduate education: The Ph.D. glut: response and rebuttal


Ideal teaching machines—a solution to the pedagogic language problem


Some remarks on lookup of structured variables


Addendum to M.L. Patrick paper


An alternative approach to mutual recursion in Algol 60 using restricted compilers


An improved program-synthesizing algorithm and its correctness

An improved program-synthesizing algorithm based on the algorithm proposed by Waldinger and Lee in 1969 is given. In the old algorithm, the program-synthesizing problem is translated into a theorem-proving problem, and a program …

Scalar- and planar-valued curve fitting using splines under tension

The spline under tension was introduced by Schweikert in an attempt to imitate cubic splines but avoid the spurious critical points they induce. The defining equations are presented here, together with an efficient method for …

Six subprograms for curve fitting using splines under tension


Generator of set-partitions to exactly R subsets [G7]