March 1973 - Vol. 16 No. 3
Features
A computer science course program for small colleges
The ACM Subcommittee on Small College Programs of the Committee on Curriculum in Computer Science (C3S) was appointed in 1969 to consider the unique problems of small colleges and universities, and to make recommendations regarding computer science programs at such schools. This report, authorized by both the subcommittee and C3S, supplies a set of recommendations for courses and necessary resources.
Implementation problems are discussed, specifically within the constraints of limited faculty and for the purposes of satisfying a wide variety of objectives. Detailed descriptions of four courses are given; suggestions are made for more advanced work; and an extensive library list is included.
Common phrases and minimum-space text storage
A method for saving storage space for text strings, such as compiler diagnostic messages, is described. The method relies on hand selection of a set of text strings which are common to one or more messages. These phrases are then stored only once. The storage technique gives rise to a mathematical optimization problem: determine how each message should use the available phrases to minimize its storage requirement. This problem is nontrivial when phrases which overlap exist. However, a dynamic programming algorithm is presented which solves the problem in time which grows linearly with the number of characters in the text. Algorithm 444 applies to this paper.
Telecommunications using a front-end minicomputer
The use of a front-end minicomputer to provide varied remote terminal access to a large scale computer is considered. The problems of embedding telecommunications I/O within an operating system are discussed, and it is shown how the decentralization of intelligence acquired by front-end processing vastly simplifies the problem. A specific implementation is discussed with emphasis on the main processor-minicomputer link, the hardware-software implementation, the effect on the main processor operating system, and an assessment of the advantages over a hardwired line controller.
The effects of multiplexing on a computer-communications system
A study is made of the way in which asynchronous time division multiplexing changes the stochastic nature of the arrival process from a user to the computer and, consequently, affects the performance of a time-shared computer-communications system. It is concluded that while, for certain values of system parameters, there is noticeable improvement in the performance of the computer (model), in the sense that time-shared scheduling delays are reduced, these improvements are offset by the transmission delays imposed by multiplexing so that there may be little or no change in the computer-communications system performance.
Analytical and simulation results are based on the model of the computer-communications system being an M/D/1 queue (the multiplexor) in tandem with a single exponential server (the computer). Analytical results include a general description of the output process of an M/D/1 queue and the conditions under which this output process is approximately Poisson.
Design and implementation of a diagnostic compiler for PL/I
PL/C is a compiler for a dialect for PL/I. The design objective was to provide a maximum degree of diagnostic assistance in a batch processing environment. For the most part this assistance is implicit and is provided automatically by the compiler. The most remarkable characteristic of PL/C is its perseverance—it completes translation of every program submitted and continues execution until a user-established error limit is reached. This requires that the compiler repair errors encountered during both translation and execution, and the design of PL/C is dominated by this consideration.
PL/C also introduces several explicit user-controlled facilities for program testing. To accommodate these extensions to PL/I without abandoning compatibility with the IBM compiler, PL/C permits “pseudo comments”—constructions whose contents can optionally be considered either source text or comment.
In spite of the diagnostic effort PL/C is a fast and efficient processor. It effectively demonstrates that compilers can provide better diagnostic assistance than is customarily offered, even when a sophisticated source language is employed, and that this assistance need not be prohibitively costly.
Gray code and the ± sign sequence when ±f(±f(±f(•••±f(x)•••))) is ordered
A previous note gives a rule for determining the sequence of + and - signs to obtain the ith largest value of +ƒ(±ƒ(±ƒ(··· ±ƒ(x)···))) when ƒ(x) is positive and monotonic [1, p. 46, §2]. Shortly after publication the writer received a letter dated March 9, 1972, from John Murchland, of the Planning & Transport Research & Computation Co. Ltd., London, in which he mentioned that the conversion scheme for obtaining the ± sign sequence from i - 1 happens to be also the standard way of going from a binary number to its Gray code equivalent, when after the conversion every plus sign is replaced by 0 and every minus sign by 1.
On Harrison’s substring testing technique
This note comments on a technique by Malcolm Harrison [1] that tests whether a given string of characters, S1, is a substring of another string of characters, S2. This technique first transforms S2 into the set consisting of all the smaller fixed size substrings of length k and then hashes each of these segments into the m positions of a computer “word”; the bit corresponding to a position in this word is turned on if at least one segment is hashed onto it; else it is zero. The test is based on the observation that the same procedure applied to an arbitrary substring of the first string will not turn on any new bits. In the following we shall assume that S1 and S2 are decomposed into l1 and l2 segments respectively.
Graduate education: the Ph.D. glut
[Two years ago the author was elected by the Washington State University faculty to a three-year term as a faculty representative to a Graduate Studies Committee charged “to examine and evaluate proposed changes in the policy of the Graduate School.” After his experiences and considerable study, the author says he feels compelled to express his observations and opinions to his fellow members of the Association for Computing Machinery.]
