May 1975 - Vol. 18 No. 5
Features
Copying cyclic list structures in linear time using bounded workspace
A bounded workspace copying algorithm for arbitrary list structures is given. This algorithm operates in linear time and does not require tag bits. The best previous bounded workspace copying algorithms achieved n2 time without tag bits and n log n time with one tag. The only restriction on the algorithm given here is that the copy must be placed into a contiguous section of memory. The method is applicable to fixed or variable size nodes.
Analysis and performance of inverted data base structures
The need to envision and architecture data base systems in a hierarchical level by level framework is stressed. The inverted data base (file) organization is then analyzed, considering implementation oriented aspects. The inverted directory is viewed realistically as another large data base which itself is subjected to inversion. Formulations are derived to estimate average access time (read only) and storage requirements, formalizing the interaction of data base content characteristics, logical complexity of queries, and machine timing and blocking specifications identified as having a first-order effect on performance. The formulations presented are necessary to be used in conjunction with any index selection criteria to determine the optimum set of index keys.
An intelligent analyzer and understander of English
The paper describes a working analysis and generation program for natural language, which handles paragraph length input. Its core is a system of preferential choice between deep semantic patterns, based on what we call “semantic density.” The system is contrasted:
with syntax oriented linguistic approaches, and
with theorem proving approaches to the understanding problem.
The PL/I procedure BASIC_GENERATOR is an implementation of Paton's algorithm [1] for finding a set of basic (fundamental) cycles of a finite undirected graph from its vertex adjacency matrix.
In a recent paper [4], Minieka proposes an algorithm for finding kth shortest paths between all pairs of nodes in an N node network. His claimed time is O(k2N3).
A syntactic algorithm for peak detection in waveforms with applications to cardiography
Peaks in a digitized waveform are detected by an algorithm incorporating piecewise linear approximation and tabular parsing techniques. Several parameters serve to identify the waveform context enabling accurate measurement of peak amplitude, duration, and shape. The algorithm is of sufficient speed to allow on-line real-time processing. An example of its application is demonstrated on an electrocardiogram.
A heuristic problem solving design system for equipment or furniture layouts
The Designer Problem Solver (DPS) demonstrates that the computer can perform simple design tasks. In particular, it designs furniture and equipment layouts. This task was chosen because it is simple, well defined, and characteristic of many design tasks in architecture, engineering, urban planning, and natural resource management. These space planning tasks usually involve manipulating two-dimensional representations of objects to create feasible or optimal solutions for problems involving topological and metric spatial constraints. The paper describes extensive tests performed on the program.
DPS is a heuristic problem solver with a planning phase prefixed to it. It uses the planning process to give it a sense of direction, diagnostic procedures to locate difficulties, and remedial actions to recover from difficulties. It uses a convex polygon representation to accurately describe the objects and the layout. This representation allows topological and metric constraints to be tested and the design to be easily updated.
DPS has been applied to 50 problems. While it is slow and limited in scope, the ideas behind it are general. It demonstrates the need for selectivity in controlling search and the methods used to achieve it: task-specific information, planning, diagnostic procedures, remedial actions, and selective alternative generators.
