March 1978 - Vol. 21 No. 3
Features
The use of an interactive information storage and retrieval system in medical research
This paper presents the results of a study of the use of an interactive computerized storage and retrieval system. A monitor built into the computer system provided usage data for the study. Additional data on user reactions were gathered from a questionnaire. The results show the important role played by frequently chosen laboratory reference leaders in influencing the use of this system. The implications of the study for the design of similar systems are discussed.
Management utilization of computers in American local governments
Traditional concepts of management information systems (MIS) bear little relation to the information systems currently in use by top management in most US local governments. What exists is management-oriented computing, involving the use of relatively unsophisticated applications. Despite the unsophisticated nature of these systems, management use of computing is surprisingly common, but also varied in its extent among local governments. Management computing is most prevalent in those governments with professional management practices where top management is supportive of computing and tends to control computing decisions and where department users have less control over design and implementation activities. Finally, management computing clearly has impacts for top managers, mostly involving improvements in decision information.
Value orientation of computer science students
Technological and nontechnological value orientations are investigated with special attention to the complexity of value structures. Computer science students, who are closely associated with technology, contrast with social science students, who are often technologically aloof. This is confirmed by the value ratings of 313 students at the University of Minnesota in 1972. Computer science majors were found to have a more complex value structure than social science majors.
Insertions and deletions in one-sided height-balanced trees
Recently Hirschberg has established that insertions into one-sided height-balanced trees can be done in O(log2N) steps. It is proved here that deletions can also be performed in O(log2N) steps, which answers the open problem posed by Hirschberg.
Preserving average proximity in arrays
Programmers and data structure designers are often forced to choose between alternative structures. In storing these structures, preserving logical adjacencies or “proximity” is usually an important consideration. The combinatorial problem of storing arrays as various kinds of list structures is examined. Embeddings of graphs are used to model the loss of proximity involved in such storage schemes, and an elementary proof that arrays cannot be stored as linear lists with bounded loss of proximity is presented. Average loss of proximity is then considered, and it is shown that arrays cannot be stored as linear lists with only bounded loss of average proximity, but can be so stored in binary trees. The former result implies, for instance, that row major order is an asymptotically optimal storage strategy for arrays.
Anomalies with variable partition paging algorithms
Five types of anomalous behaviour which may occur in paged virtual memory operating systems are defined. One type of anomaly, for example, concerns the fact that, with certain reference strings and paging algorithms, an increase in mean memory allocation may result in an increase in fault rate. Two paging algorithms, the page fault frequency and working set algorithms, are examined in terms of their anomaly potential, and reference string examples of various anomalies are presented. Two paging algorithm properties, the inclusion property and the generalized inclusion property, are discussed and the anomaly implications of these properties presented.
Implications of structured programming for machine architecture
Based on an empirical study of more than 10,000 lines of program text written in a GOTO-less language, a machine architecture specifically designed for structured programs is proposed. Since assignment, CALL, RETURN, and IF statements together account for 93 percent of all executable statements, special care is given to ensure that these statements can be implemented efficiently. A highly compact instruction encoding scheme is presented, which can reduce program size by a factor of 3. Unlike a Huffman code, which utilizes variable length fields, this method uses only fixed length (1-byte) opcode and address fields. The most frequent instructions consist of a single 1-byte field. As a consequence, instruction decoding time is minimized, and the machine is efficient with respect to both space and time.
