Search

An interconnection pattern of processing elements, the cube-connected cycles (CCC), is introduced which can be used as a general purpose parallel processor. Because its design complies with present technological constraints, the CCC can also be used in the layout of many specialized large scale integrated circuits (VLSI). By combining the principles of parallelism and pipelining, the CCC can emulate the cube-connected machine and the shuffle-exchange network with no significant degradation of performance but with a more compact structure. We describe in detail how to program the CCC for efficiently solving a large class of problems that include Fast Fourier transform, sorting, permutations, and derived algorithms. [ABSTRACT FROM AUTHOR]

Examples of fruitful interaction between geometrical combinatorics and the design and analysis of algorithms are presented. A demonstration is given of the way in which a simple geometrical construction yields new and efficient algorithms for various searching and list manipulation problems. [ABSTRACT FROM AUTHOR]

The article presents a data structure for manipulating priority queues. A variety of applications directly require using priority queues--job scheduling, discrete simulation languages where labels represent the time at which events are to occur, as well as various sorting problems. Priority queues also play a central role in several good algorithms, such as optimal code constructions. The author describes the underlying combinatorial structure, called binomial trees. Binomial trees and forests appear in various data manipulation problems. Although the discussion in the article is an adequate presentation of the priority queue primitives for a very abstract machine model, it does not indicate how to actually code these algorithms on a digital computer. One still has to solve some problems, the first of which concerns the machine representation of labeled binomial forests. The data structure seems to be interesting in itself because of its conceptual simplicity and of the connections it establishes among various data manipulation problems.

Following the fixpoint theory of Scott, the semantics of computer programs are defined in terms of the least fixpoints of recursive programs. This allows not only the justification of all existing verification techniques, but also their extension to the handling, in a uniform manner of various properties of computer programs, including correctness, termination, and equivalence. [ABSTRACT FROM AUTHOR]

Discusses inductive methods for proving properties of recursive programs. Clarification and extension of known results about computation of recursive programs; Difference between theoretical and practical approaches.