February 1978 - Vol. 21 No. 2
Features
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.
The recursion removal algorithm presented by Strong and Walker is amplified and applied to a relatively complex PL/I program. The aim is to demonstrate systematic recursion-removal techniques on something more complex than Knuth's “sturdy toddler” and to obtain measurements of the cost of procedure linkage in PL/I and the savings achievable via procedure integration in the presence of recursion. First, the paper describes the recursion-removal process and the example on which it will be illustrated. Recursion removal is then applied to the two major parts of this example and the final result of the process is displayed. Our performance comparison results are presented, and our conclusions are briefly discussed
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.
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.
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.
Relaxation methods for image reconstruction
The problem of recovering an image (a function of two variables) from experimentally available integrals of its grayness over thin strips is of great importance in a large number of scientific areas. An important version of the problem in medicine is that of obtaining the exact density distribution within the human body from X-ray projections. One approach that has been taken to solve this problem consists of translating the available information into a system of linear inequalities. The size and the sparsity of the resulting system (typically, 25,000 inequalities with fewer than 1 percent of the coefficients nonzero) makes methods using successive relaxations computationally attractive, as compared to other ways of solving systems of inequalities. In this paper, it is shown that, for a consistent system of linear inequalities, any sequence of relaxation parameters lying strictly between 0 and 2 generates a sequence of vectors which converges to a solution. Under the same assumptions, for a system of linear equations, the relaxation method converges to the minimum norm solution. Previously proposed techniques are shown to be special cases of our procedure with different choices of relaxation parameters. The practical consequences for image reconstruction of the choice of the relaxation parameters are discussed.
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.
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.
