Sign In

Communications of the ACM

Table of Contents


ACM President's Letter: a fond farewell


An optimal method for deletion in one-sided height-balanced trees

A one-sided height-balanced tree is a binary tree in which every node's right subtree has a height which is equal to or exactly one greater than the height of its left subtree. It has an advantage over the more general AVL tree …

A selective traversal algorithm for binary search trees

The problem of selecting data items from a binary search tree according to a list of range conditions is considered. The process of visiting a minimal number of nodes to retrieve data satisfying the range conditions is called …

Analyses of deterministic parsing algorithms

This paper describes an approach for determining the minimum, maximum, and average times to parse sentences acceptable by a deterministic parser. These quantities are presented in the form of symbolic formulas, called time-formulas …

Automatic error recovery for LR parsers

In this paper we present a scheme for detecting and recovering from syntax errors in programs. The scheme, which is based on LR parsing, is driven by information which is directly and automatically obtainable from the information …

Characteristics of application software maintenance

Maintenance and enhancement of application software consume a major portion of the total life cycle cost of a system. Rough estimates of the total systems and programming resources consumed range as high as 75-80 percent in each …

Some basic determinants of computer programming productivity

The purpose of this research was to examine the relationship between processing characteristics of programs and experience characteristics of programmers and program development time. The ultimate objective was to develop a technique …

Automated welfare client-tracking and service integration: the political economy of computing

The impacts of an automated client-tracking system on the clients, caseworkers, administrators, and operations of the welfare agencies that use it are reported. The major impact of this system was to enhance the administrative …

Performance of rollback recovery systems under intermittent failures

A mathematical model of a transaction-oriented system under intermittent failures is proposed. The system is assumed to operate with a checkpointing and rollback/recovery method to ensure reliable information processing. The  …

General equations for idealized CPU-I/O overlap configurations

General equations are derived for estimating the maximum possible utilization of main storage partitions, CPU and I/O devices under different conditions in an idealized CPU-I/O overlap model of multiprogrammed computer systems …

ACM forum