Artificial Intelligence and Machine Learning
Advertisement
The selection of optimal tab settings
A new generation of computer terminals allows tab settings to be selected and set by the computer. This feature can be used to reduce the number of characters that are needed to represent a document for transmission and printing. In this note, an algorithm is given for selecting the optimal set of tab stops for minimizing the number of characters transmitted. An implementation of the algorithm has reduced the number of characters transmitted by from 7 to 30 percent, but requires a prepass through the document to compute a matrix used in determining the optimal set of tab stops. The use of fixed tab stops, as a heuristic alternative, can achieve about 80 percent of optimal with no prepass.
The findings of a study designed to address the pressing problems associated with the strategic planning of the computing effort in higher education are presented here. A planning methodology was developed and tested through implementation at a university. Two years after the methodology was implemented, the effectiveness of the planning methodology was assessed in terms of the improvement of the delivery of computing services to the major institutional roles of instruction, research, and administration. Two control institutions were employed to contrast the improvements at the test institution. The results of the research indicate the planning methodology significantly enhanced the delivery of computing services.
Reverse path forwarding of broadcast packets
A broadcast packet is for delivery to all nodes of a network. Algorithms for accomplishing this delivery through a store-and-forward packet switching computer network include (1) transmission of separately addressed packets, (2) multidestination addressing, (3) hot potato forwarding, (4) spanning tree forwarding, and (5) source based forwarding. To this list of algorithms we add (6) reverse path forwarding, a broadcast routing method which exploits routing procedures and data structures already available for packet switching. Reverse path forwarding is a practical algorithm for broadcast routing in store-and-forward packet switching computer networks. The algorithm is described as being practical because it is not optimal according to metrics developed for its analysis in this paper, and also because it can be implemented in existing networks with less complexity than that required for the known alternatives.
Optimizing decision trees through heuristically guided search
Optimal decision table conversion has been tackled in the literature using two approaches, dynamic programming and branch-and-bound. The former technique is quite effective, but its time and space requirements are independent of how “easy” the given table is. Furthermore, it cannot be used to produce good, quasioptimal solutions. The branch-and-bound technique uses a good heuristic to direct the search, but is cluttered up by an enormous search space, since the number of solutions increases with the number of test variables according to a double exponential. In this paper we suggest a heuristically guided top-down search algorithm which, like dynamic programming, recognizes identical subproblems but which can be used to find both optimal and quasioptimal solutions. The heuristic search method introduced in this paper combines the positive aspects of the above two techniques. Compressed tables with a large number of variables can be handled without deriving expanded tables first.
A linear sieve algorithm for finding prime numbers
A new algorithm is presented for finding all primes between 2 and n. The algorithm executes in time proportional to n (assuming that multiplication of integers not larger than n can be performed in unit time). The method has the same arithmetic complexity as the algorithm presented by Mairson [6]; however, our version is perhaps simpler and more elegant. It is also easily extended to find the prime factorization of all integers between 2 and n in time proportional to n.
The new class of Pk trees is presented, where height balance is maintained for the nodes lying on particular paths. The number of nodes of a Pk tree asympotically grows as a power of the height, in the worst case. A procedure for node insertion is given, and the class of trees considered is restricted to IPk trees, which are buildable by such a procedure. The average behavior of such trees, studied by an extensive set of simulation runs, is close to that of AVL trees. In particular, the family of IP0 trees whose main advantage is the reduced number of restructurings required after node insertion, is analyzed.
A simply extended and modified batch environment graphical system (SEMBEGS)
SEMBEGS is a complete batch environment graphical system containing components for handling graphical data files, for displaying the contents of these files on a variety of graphical hardware, and for performing graphical batch input operations. SEMBEGS is easy to extend and modify to meet the growing needs of a large batch environment, and is even extendable to a fully interactive system. The paper presents the conceptual view of graphics leading to the design of SEMBEGS and outlines the major components of the system. The design of SEMBEGS is founded upon the basic assumption that the true aim of computer graphics is to describe graphical entities, rather than, as commonly held, to provide graphical input and output functional capabilities. SEMBEGS is built around a Basic Graphical Data Management System (BAGDAMS) which provides a common means of communicating the descriptions of graphical entities between the various components of SEMBEGS. BAGDAMS provides facilities for storing, retrieving, and manipulating the descriptions of graphical entities provided by, and received by application programs, graphics packages, and graphical devices.
Distributed processes: a concurrent programming concept
A language concept for concurrent processes without common variables is introduced. These processes communicate and synchronize by means of procedure calls and guarded regions. This concept is proposed for real-time applications controlled by microcomputer networks with distributed storage. The paper gives several examples of distributed processes and shows that they include procedures, coroutines, classes, monitors, processes, semaphores, buffers, path expressions, and input/output as special cases.
Performance evaluation of highly concurrent computers by deterministic simulation
Simulation is presented as a practical technique for performance evaluation of alternative configurations of highly concurrent computers. A technique is described for constructing a detailed deterministic simulation model of a system. In the model a control stream replaces the instruction and data streams of the real system. Simulation of the system model yields the timing and resource usage statistics needed for performance evaluation, without the necessity of emulating the system. As a case study, the implementation of a simulator of a model of the CPU-memory subsystem of the IBM 360/91 is described. The results of evaluating some alternative system designs are discussed. The experiments reveal that, for the case study, the major bottlenecks in the system are the memory unit and the fixed point unit. Further, it appears that many of the sophisticated pipelining and buffering techniques implemented in the architecture of the IBM 360/91 are of little value when high-speed (cache) memory is used, as in the IBM 360/195.
Systems design education: a gaming approach
One of the problems facing managers of computer installations is the problem of configuring the computer system to meet the demands made by the mix of jobs that the computer center must service, This paper presents a management game that allows the player to configure a computer system to meet a hypothetical job mix. The job mix is under the control of a game administrator and can be varied to simulate a variety of real-world situations (I/0 bound jobs, compute bound jobs, etc.). The player of the game receives a set of detailed reports on the cost of his choices and a simulated run of the center operating under his choices.
Using synthetic images to register real images with surface models
A number of image analysis tasks can benefit from registration of the image with a model of the surface being imaged. Automatic navigation using visible light or radar images requires exact alignment of such images with digital terrain models. In addition, automatic classification of terrain, using satellite imagery, requires such alignment to deal correctly with the effects of varying sun angle and surface slope. Even inspection techniques for certain industrial parts may be improved by this means.
We achieve the required alignment by matching the real image with a synthetic image obtained from a surface model and known positions of the light sources. The synthetic image intensity is calculated using the reflectance map, a convenient way of describing surface reflection as a function of surface gradient. We illustrate the technique using LANDSAT images and digital terrain models.
Median split trees: a fast lookup technique for frequently occuring keys
Split trees are a new technique for searching sets of keys with highly skewed frequency distributions. A split tree is a binary search tree each node of which contains two key values—a node value which is a maximally frequent key in that subtree, and a split value which partitions the remaining keys (with respect to their lexical ordering) between the left and right subtrees. A median split tree (MST) uses the lexical median of a node's descendents as its split value to force the search tree to be perfectly balanced, achieving both a space efficient representation of the tree and high search speed. Unlike frequency ordered binary search trees, the cost of a successful search of an MST is log n bounded and very stable around minimal values. Further, an MST can be built for a given key ordering and set of frequencies in time n log n, as opposed to n2 for an optimum binary search tree. A discussion of the application of MST's to dictionary lookup for English is presented, and the performance obtained is contrasted with that of other techniques.
Synthesizing constraint expressions
A constraint network representation is presented for a combinatorial search problem: finding values for a set of variables subject to a set of constraints. A theory of consistency levels in such networks is formulated, which is related to problems of backtrack tree search efficiency. An algorithm is developed that can achieve any level of consistency desired, in order to preprocess the problem for subsequent backtrack search, or to function as an alternative to backtrack search by explicitly determining all solutions.
Scatter tables for open addressing benefit from recursive entry displacements, cutoffs for unsuccessful searches, and auxiliary cost functions. Compared with conventional methods, the new techniques provide substantially improved tables that resemble exact-solution optimal packings. The displacements are depth-limited approximations to an enumerative (exhaustive) optimization, although packing costs remain linear—O(n)—with table size n. The techniques are primarily suited for important fixed (but possibly quite large) tables for which reference frequencies may be known: op-code tables, spelling dictionaries, access arrays. Introduction of frequency weights further improves retrievals, but the enhancement may degrade cutoffs.
Models for parallel processing within programs: application to CPU: I/O and I/O: I/O overlap
Approximate queueing models for internal parallel processing by individual programs in a multiprogrammed system are developed in this paper. The solution technique is developed by network decomposition. The models are formulated in terms of CPU:I/O and I/O:I/O overlap and applied to the analysis of these problems. The percentage performance improvement from CPU:I/O overlap is found to be greatest for systems which are in approximate CPU:I/O utilization balance and for low degrees of multiprogramming. The percentage improvement from I/O:I/O overlap is found to be greatest for systems in which the I/O system is more utilized than the CPU.
Optimal histogram matching by monotone gray level transformation
This paper investigates the problem of optimal histogram matching using monotone gray level transformation, which always assigns all picture points of a given gray level i to another gray level T(i) such that if i ≥ j, then T(i) ≥ T(j). The objective is to find a transformed digital picture of a given picture such that the sum of absolute errors between the gray level histogram of the transformed picture and that of a reference picture is minimized. This is equivalent to placing k1 linearly ordered objects of different sizes one by one into k2 linearly ordered boxes of assorted sizes, such that the accumulated error of space underpacked or overpacked in the boxes is minimized; the placement function is monotonic, which ensures a polynomial time solution to this problem. A tree search algorithm for optimal histogram matching is presented which has time complexity O(k1 × k2). If the monotone property is dropped, then the problem becomes NP-complete, even if it is restricted to k2 = 2.
A comparison of heaps and the TL structure for the simulation event set
Following publication of our paper [2], questions arose with respect to the superiority of the TL structure over heaps,1 particularly in the face of the remarks of Gonnet [3], concerning the use of heaps for the physical realization of the simulation event set. Gonnet's communication was in response to the Vaucher and Duval paper [5], and suggested the heap to be a more efficient structure than any proposed in [5]. As regards a comparison of heaps and the TL structure we can make the following remarks:
An algorithm using symbolic techniques for the Bel-Petrov classification of gravitational fields
In this note, an algorithm is presented for the symbolic calculation of certain algebraic invariants of the Weyl tensor which permits the determination of the Bel-Petrov types of a gravitational field. This algorithm, although more specialized than that of D'Inverno and Russell-Clark, requires neither the use of a special coordinate system nor the spin coefficient formalism. The algorithm has been implemented in FORMAC and is designed to complete the classification scheme proposed by Petrov in his book. An appendix contains examples illustrating the use of the algorithm.
Hybrid simulation models of computer systems
This paper describes the structure and operation of a hybrid simulation model in which both discrete-event simulation and analytic techniques are combined to produce efficient yet accurate system models. In an example based on a simple hypothetical computer system, discrete-event simulation is used to model the arrival and activation of jobs, and a central-server queueing network models the use of system processors. The accuracy and efficiency of the hybrid technique are demonstrated by comparing the result and computational costs of the hybrid model of the example with those of an equivalent simulation-only model.
Event manipulation for discrete simulations requiring large numbers of events
The event-manipulation system presented here consists of two major parts. The first part addresses the familiar problem of event scheduling efficiency when the number of scheduled events grows large. The second part deals with the less apparent problem of providing efficiency and flexibility as scheduled events are accessed to be executed. Additional features and problems dealt with include the proper handling of simultaneous events; that certain events must be created, scheduled, and executed at the same points in simulated time; that infinite loops caused by the concatenation of such “zero-time” events are possible and must be diagnosed; that maintaining various event counts is practical and economical; and that a capability for handling “time-displaceable” events is desirable and possible.
Insertion and deletion algorithms are provided for the class of right (or one-sided) brother trees which have O (log n) performance. The importance of these results stems from the close relationship of right brother trees to one-sided height-balanced trees which have an insertion algorithm operating in O (log2 n). Further, although both insertion and deletion can be carried out in O (log n) time for right brother trees, it appears that the insertion algorithm is inherently much more difficult than the deletion algorithm—the reverse of what one usually obtains.
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 InvolvedCommunications 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