This is being written on the day after the close of ACM 71 as I return to Europe for continuation of an interrupted vacation. Therefore, these remarks are going to be short, and they will not, of course, do justice to the results obtained from our annual meeting in Chicago.
September 1971 - Vol. 14 No. 9
Features
Education related to the use of computers in organizations
The ACM Curriculum Committee on Computer Education for Management has been carrying out a study on “Curriculum Development in Management Information Systems Education in Colleges and Universities” under a grant from the National Science Foundation. This position paper provides a framework for the study.
Preliminary conclusions are presented on the need for education in administrative information systems, and appropriate college curricula and courses are suggested. Also, the role of professional societies and organizations using computers is discussed, and the plans of the Committee are outlined.
The initial approach of the Committee has been to describe the education necessary for the effective use of computers in organizations, to classify the positions for which education is required, and to survey educational programs now available.
A efficient bit table technique for dynamic storage allocation of 2″-word blocks
An efficient bit table technique for dynamic storage allocation of 2n-word blocks, which requires a minimized amount of memory for bookkeeping purposes, is described. The technique has been tested in an implementation of the list processing language L6. A number of ideas incorporated in the processor are also described.
Canonical structure in attribute based file organization
A new file structure for attribute based retrieval is proposed in this paper. It allows queries involving arbitrary Boolean functions of the attribute-value pairs to be processed without taking intersections of lists. The structure is highly dependent on the way in which the file is to be used and is uniquely determined by the specification of the allowed queries. Thus, for example, the structure for retrieval on the basis of ranges of values on a given attribute would be very different from one where only retrieval on the basis of a single value is permitted.
The file organization being proposed is based on the atoms of a Boolean algebra generated by the queries. The desirable properties claimed for this structure are proved, and file maintenance questions are discussed.
A note on best one-sided approximations
In this note we consider the relationship between best approximations and best one-sided approximations for three different measures of goodness of fit. For these measures simple relationships exist between best approximations and best one-sided approximations. In particular it is shown that a best approximation and best one-sided approximation differ only by a multiplicative constant when the measure is the uniform norm of the relative error. In this case problems involving best one-sided approximations can be reduced to problems involving best approximations. The result is especially significant if one wants to numerically determine a best one-sided approximation, since algorithms exist for numerically determining best approximations when the measure is the uniform norm of the relative error (see, for example, [1]).
In the numerical solution of ordinary differential equations, certain implicit linear multistep formulas, i.e. formulas of type ∑kj=0 &agr;jxn+j - h ∑kj=0 &bgr;jxn+j = 0, (1) with &bgr;k> ≠ 0, have long been favored because they exhibit strong (fixed-h) stability. Lately, it has been observed [1-3] that some special methods of this type are unconditionally fixed-h stable with respect to the step size. This property is of great importance for the efficient solution of stiff [4] systems of differential equations, i.e. systems with widely separated time constants. Such special methods make it possible to integrate stiff systems using a step size which is large relative to the rate of change of the fast-varying components of the solution.
Average binary search length for dense ordered lists
A binary search is effective only when the list searched is ordered. It is efficient only when the list is dense—i.e. when records are in contiguous locations. It is easy to show that the maximum number of looks for a search L is given by [1]. L = [log2N+1], (1) where N is the number of records in the list and the square bracket means “integral part of.”
Comment on Cheney’s list-compaction algorithm
C.J. Cheney [2] implicitly assumes that cells of list storage are self-identifying. Cheney needs this assumption so that his algorithm, when linearly scanning the memory containing a copy of a list, can determine whether particular bit patterns within that memory are pointers to other list structure. The assumption is strong, and its effect is contrary to that of the list compaction which is his algorithm's purpose.
It is hard to recruit ACM members when there is no demonstrable relationship between membership and employment. Employers who recruit actuaries and accountants often specify the recognition applicants must have won from the relevant societies. I have not seen a requirement for ACM membership in help-wanted ads for programmers.