November 1979 - Vol. 22 No. 11

This paper addresses the question: What does a person know following learning of BASIC programming? Several underlying conceptual structures are identified: (1) a transaction is an event that occurs in the computer and involves some operation on some object at some location, (2) a prestatement is a set of transactions corresponding to a line of code, (3) chunks are frequently occurring configurations of prestatements corresponding to several lines of code.

This paper describes the history of the design of the password security scheme on a remotely accessed time-sharing system. The present design was the result of countering observed attempts to penetrate the system. The result is a compromise between extreme security and ease of use.

Substitution ciphers are codes in which each letter of the alphabet has one fixed substitute, and the word divisions do not change. In this paper the problem of breaking substitution ciphers is represented as a probabilistic labeling problem. Every code letter is assigned probabilities of representing plaintext letters. These probabilities are updated in parallel for all code letters, using joint letter probabilities. Iterating the updating scheme results in improved estimates that finally lead to breaking the cipher. The method is applied successfully to two examples.

The problem of storing and searching large sparse tables is ubiquitous in computer science. The standard technique for storing such tables is hashing, but hashing has poor worst-case performance. We propose a good worst-case method for storing a static table of n entries, each an integer between 0 and N - 1. The method requires O(n) words of storage and allows O(logn N) access time. Although our method is a little complicated to use in practice, our analysis shows why a simpler algorithm used for compressing LR parsing tables works so well.