Search
Join ACM

Systems and Networking

Advertisement

Research and Advances Feb 1 1985

A specification language to assist in analysis of discrete event simulation models

Effective development environments for discrete event simulation models should reduce development costs and improve model performance. A model specification language used in a model development environment is defined. This approach is intended to reduce modeling costs by interposing an intermediate form between a conceptual model (the model as it exists in the mind of the modeler) and an executable representation of that model. As a model specification is constructed, the incomplete specification can be analyzed to detect some types of errors and to provide some types of model documentation. The primitives used in this specification language, called a condition specification (CS), are carefully defined. A specification for the classical patrolling repairman model is used to illustrate this language. Some possible diagnostics and some untestable model specification properties, based on such a representation, are summarized.
and
Research and Advances Feb 1 1985

Amortized efficiency of list update and paging rules

In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes &thgr;(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.
and
Research and Advances Jan 2 1985

An inverted taxonomy of sorting algorithms

An alternative taxonomy (to that of Knuth and others) of sorting algorithms is proposed. It emerges naturally out of a top-down approach to the derivation of sorting algorithms. Work done in automatic program synthesis has produced interesting results about sorting algorithms that suggest this approach. In particular, all sorts are divided into two categories: hardsplit/easyjoin and easysplit/hardjoin. Quicksort and merge sort, respectively, are the canonical examples in these categories. Insertion sort and selection sort are seen to be instances of merge sort and quicksort, respectively, and sinking sort and bubble sort are in-place versions of insertion sort and selection sort. Such an organization introduces new insights into the connections and symmetries among sorting algorithms, and is based on a higher level, more abstract, and conceptually simple basis. It is proposed as an alternative way of understanding, describing, and teaching sorting algorithms.
Research and Advances Jan 2 1985

Computer professionals whose scientific freedom and human rights have been violated—1984: a report of the ACM committee on scientific freedom and human rights

This is the third report prepared by the ACM Committee on Scientific Freedom and Human Rights (CSFHR). The first was published in the March 1981 Communications and the second in the December 1982 issue. This report is an update. Since the committee intends to publish future updates, it would appreciate receiving further information about computer scientists whose rights have been violated. Such information should be sent to: Jack Minker, Vice-Chairman, Committee on Scientific Freedom and Human Rights, Department of Computer Science, University of Maryland, College Park, MD 29742.Because those whose scientific freedom or human rights have been violated derive sustenance and support from contacts with their colleagues, the CSFHR has established a program in which ACM chapters “adopt” individual scientists and correspond with them. Such correspondence should touch on the personal and scientific and not discuss political matters. These letters greatly improve the morale of the recipients and are one of the few ways they can keep current with computer science and technology. This CSFHR program is directed by Helen Takacs (P.O. Drawer CS, Mississippi State, MS 39762).
Research and Advances Jan 2 1985

Reduced instruction set computers

Reduced instruction set computers aim for both simplicity in hardware and synergy between architectures and compilers. Optimizing compilers are used to compile programming languages down to instructions that are as unencumbered as microinstructions in a large virtual address space, and to make the instruction cycle time as fast as possible.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More