July 1971 - Vol. 14 No. 7
Features
The state of computer oriented curricula in business schools 1970
The ACM Committee on Computer Education for Management, supported by a National Science Foundation Grant, is established to appraise the state of the art and to develop a series of recommendations for improving computer education for management. To provide the Committee with material for its study of curricular needs, five regional meetings in the United States were held in 1970, at each of which a broad cross section of invited academicians and practitioners considered the state of curricula in business schools. Three topics were covered: curricula for the general manager; computer-related material in required and functional courses; and curricula for students concentrating on computer-based information systems.
An analysis of the minutes of the meetings revealed a common set of experiences which raised similar pedagogic and economic issues. This presentation gives a summary of the discussions; a condensation of the pedagogic and substantive concerns raised; and consideration of the resource allocation issues involved.
Preliminary to the Committee's recommendations for improving computer education for management, this report has been prepared to provide the participants and the administrators of their institutions with background information for the ongoing task of course development.
Chairman of the ten-man Committee is Daniel Teichroew (The University of Michigan).
A programmmer training project
A project is described whose purpose is to train selected black residents of the Albany-Schenectady area in computer programming and arrange for jobs for them in the computer field. Both the organization and curriculum of the course are discussed.
A class of context-free grammars, called the “Simple LR(k)” or SLR(k) grammars is defined. This class has been shown to include weak precedence and simple precedence grammars as proper subsets. How to construct parsers for the SLR(k) grammars is also shown. These parser-construction techniques are extendible to cover all of the LR(k) grammars of Knuth; they have been implemented and by direct comparison proved to be superior to precedence techniques, not only in the range of grammars covered, but also in the speed of parser construction and in the size and speed of the resulting parsers.
A language extension for graph processing and its formal semantics
A simple programming language “extension,” Graspe, for processing directed graphs is defined. Graspe consists of a type of directed graph data structure and a set of primitive operations for manipulating these structures. Graspe may be most easily implemented by embedding it in a host language. Emphasis is placed both on Graspe itself and on its method of definition. Commonly, the definition of a language involves definition of the syntactic elements and explanation of the meaning to be assigned them (the semantics). The definition of Graspe here is solely in terms of its semantics; that is, the data structures and operations are defined precisely but without assignment of a particular syntactic representation. Only when the language is implemented is assignment of an explicit syntax necessary. An example of an implementation of Graspe embedded in Lisp is given as an illustration. The advantages and disadvantages of the definition of a language in terms of its semantics are discussed.
An algorithm for the blocks and cutnodes of a graph
An efficient method is presented for finding blocks and cutnodes of an arbitrary undirected graph. The graph may be represented either (i) as an ordered list of edges or (ii) as a packed adjacency matrix. If w denotes the word length of the machine employed, the storage (in machine words) required for a graph with n nodes and m edges increases essentially as 2(m + n) in case (i), or n2/w in case (ii). A spanning tree with labeled edges is grown, two edges finally bearing different labels if and only if they belong to different blocks. For both representations the time required to analyze a graph on n nodes increases as n&ggr; where &ggr; depends on the type of graph, 1 ≤ &ggr; ≤ 2, and both bounds are attained. Values of &ggr; are derived for each of several suitable families of test graphs, generated by an extension of the web grammar approach. The algorithm is compared in detail with that proposed by Read for which 1 ≤ &ggr; ≤ 3.
Buffer allocation in merge-sorting
A fixed buffer allocation for merge-sorting is presented here which minimizes the number of input-output operations for a given order of merge. When sorting on movable arm disks, the number of seeks is equal to the number of input-output operations, and the seek time usually controls the sort time. First some standard terminology is introduced. Then the input buffer allocation method is described, followed by an analysis of the improvement to be expected over more conventional allocation. This analysis makes use of a particular distribution function. An analysis of a completely different distribution is given which yields similar results. This suggests that the results do not depend on a particular distribution function. An optimum output buffer size is also determined. It is concluded that this buffering allocation can significantly reduce the time of merge sorting on movable arm disks when the input data are not random, and that this output buffer allocation should be used whether the data is random or not.
Subexpression ordering in the execution of arithmetic expressions
An arithmetic expression can often be broken down into its component subexpressions. Depending on the hardware environment in which the expression is to be executed, these subexpressions can be evaluated in serials, in parallel, or in a combination of these modes. This paper shows that expression execution time can be minimized only if consideration is given to the ordering of the subexpressions. In particular, subexpressions should be executed in order of decreasing memory and processor time requirements. This observation is valid for configurations ranging from a uniprocessor with an unbuffered main memory to a multiprocessor with a “cache” buffer memory. If the number of subexpressions which can be executed in parallel exceeds the number of available processors, then execution of some of these subexpressions must be postponed. A procedure is given which combines this requirement with the earlier ordering considerations to provide an optimal execution sequence.
The original work of Gale and Shapley on an assignment method using the stable marriage criterion has been extended to find all the stable marriage assignments. The algorithm derived for finding all the stable marriage assignments is proved to satisfy all the conditions of the problem. Algorithm 411 applies to this paper.
