Computing Applications
Advertisement
Economical encoding of commas between strings
A method for insertion of delimiters between strings without using new symbols is presented. As the lengths of the strings increase, the extra cost, in terms of prolongation, becomes vanishingly small compared to the lengths of the strings.
A data structure for manipulating priority queues
A data structure is described which can be used for representing a collection of priority queues. The primitive operations are insertion, deletion, union, update, and search for an item of earliest priority.
Orderly enumeration of nonsingular binary matrices applied to text encryption
Nonsingular binary matrices of order N, i.e., nonsingular over the field {0, 1}, and an initial segment of the natural numbers are placed in one-to-one correspondence. Each natural number corresponds to two intermediate vectors. These vectors are mapped into a nonsingular binary matrix. Examples of complete enumeration of all 2 × 2 and 3 × 3 nonsingular binary matrices were produced by mapping the intermediate vectors to the matrices.
The mapping has application to the Vernam encipherment method using pseudorandom number sequences. A bit string formed from bytes of text of a data encryption key can be used as a representation of a natural number. This natural number is transformed to a nonsingular binary matrix. Key leverage is obtained by using the matrix as a “seed” in a shift register sequence pseudorandom number generator.
Secure communications over insecure channels
According to traditional conceptions of cryptographic security, it is necessary to transmit a key, by secret means, before encrypted massages can be sent securely. This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained. A method is described which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key. The method provides a logically new kind of protection against the passive eavesdropper. It suggests that further research on this topic will be highly rewarding, both in a theoretical and a practical sense.
A technique for isolating differences between files
A simple algorithm is described for isolating the differences between two files. One application is the comparing of two versions of a source program or other file in order to display all differences. The algorithm isolates differences in a way that corresponds closely to our intuitive notion of difference, is easy to implement, and is computationally efficient, with time linear in the file length. For most applications the algorithm isolates differences similar to those isolated by the longest common subsequence. Another application of this algorithm merges files containing independently generated changes into a single file. The algorithm can also be used to generate efficient encodings of a file in the form of the differences between itself and a given “datum” file, permitting reconstruction of the original file from the diference and datum files.
Assembling code for machines with span-dependent instructions
Many modern computers contain instructions whose lengths depend on the distance from a given instance of such an instruction to the operand of that instruction. This paper considers the problem of minimizing the lengths of programs for such machines. An efficient solution is presented for the case in which the operand of every such “span-dependent” instruction is either a label or an assembly-time expression of a certain restricted form. If this restriction is relaxed by allowing these operands to be more general assembly-time expressions, then the problem is shown to be NP-complete.
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.
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.
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.
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.
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.
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.
The B-tree and its variants have, with increasing frequency, been proposed as a basic storage structure for multiuser database applications. Here, three potential problems which must be dealt with in such a structure that do not arise in more traditional static directory structures are indicated. One problem is a possible performance penalty.
This paper explores a technique for proving the correctness and termination of programs simultaneously. This approach, the intermittent-assertion method, involves documenting the program with assertions that must be true at some time when control passes through the corresponding point, but that need not be true every time. The method, introduced by Burstall, promises to provide a valuable complement to the more conventional methods.
The intermittent-assertion method is presented with a number of examples of correctness and termination proofs. Some of these proofs are markedly simpler than their conventional counterparts. On the other hand, it is shown that a proof of correctness or termination by any of the conventional techniques can be rephrased directly as a proof using intermittent assertions. Finally, it is shown how the intermittent-assertion method can be applied to prove the validity of program transformations and the correctness of continuously operating programs.
Computer science faculties: the current status of minorities and women
The results of a survey conducted in the fall of 1975 to determine the status of women and minority faculty members in academic computer science are presented. Faculty members were compared with respect to professional background, salaries, teaching load, publication records, and research grants. Analysis of the data indicated that the over-all verdict is one of general equality among women, minorities, and men.
A method for obtaining digital signatures and public-key cryptosystems
An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n.
Some new methods of detecting step edges in digital pictures
This note describes two operators that respond to step edges, but not to ramps. The first is similar to the digital Laplacian, but uses the max, rather than the sum, of the x and y second differences. The second uses the difference between the mean and median gray levels in a neighborhood. The outputs obtained from these operators applied to a set of test pictures are compared with each other and with the standard digital Laplacian and gradient. A third operator, which uses the distance between the center and centroid of a neighborhood as an edge value, is also briefly considered; it turns out to be equivalent to one of the standard digital approximations to the gradient.
Covering edges by cliques with regard to keyword conflicts and intersection graphs
Kellerman has presented a method for determining keyword conflicts and described a heuristic algorithm which solves a certain combinatorial optimization problem in connection with this method. This optimization problem is here shown to be equivalent to the problem of covering the edges of a graph by complete subgraphs with the objective of minimizing the number of complete subgraphs. A relationship between this edge-clique-cover problem and the graph coloring problem is established which allows algorithms for either one of these problems to be constructed from algorithms for the other. As consequences of this relationship, the keyword conflict problem and the edge-clique-cover problem are shown to be NP-complete, and if P ≠ NP then they do not admit polynomial-time approximation algorithms which always produce solutions within a factor less than 2 from the optimum.
A comparison of numerical techniques in Markov modeling
This paper presents several numerical methods which may be used to obtain the stationary probability vectors of Markovian models. An example of a nearly decomposable system is considered, and the results obtained by the different methods examined. A post mortem reveals why standard techniques often fail to yield the correct results. Finally, a means of estimating the error inherent in the decomposition of certain models is presented.
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