People who discover the power and beauty of high-level, abstract ideas often make the mistake of believing that concrete ideas at lower levels are relatively worthless and might as well be forgotten. The speaker will argue that, on the contrary, the best computer scientists are thoroughly grounded in basic concepts of how computers actually work, and indeed that the essence of computer science is an ability to understand many levels of abstraction simultaneously. Therefore he has put considerable effort into the design of a RISC machine called MMIX, as an aid to computer science educators. MMIX is intended to be simple and clean yet realistic. Many tools have been built to simulate the MMIX architecture, and more are under development.

Article A sequence of series for the Lambert W function Share on Authors: Robert M. Corless Department of Applied Mathematics, University of Western Ontario, London, Canada N6A 5B7 Department of Applied Mathematics, University of Western Ontario, London, Canada N6A 5B7View Profile , David J. Jeffrey Department of Applied Mathematics, University of Western Ontario, London, Canada N6A 5B7 Department of Applied Mathematics, University of Western Ontario, London, Canada N6A 5B7View Profile , Donald E. Knuth Computer Science Department, Gates 4B, Stanford University, Stanford, CA Computer Science Department, Gates 4B, Stanford University, Stanford, CAView Profile Authors Info & Claims ISSAC '97: Proceedings of the 1997 international symposium on Symbolic and algebraic computationJuly 1997 Pages 197–204https://doi.org/10.1145/258726.258783Online:01 July 1997Publication History 87citation1,653DownloadsMetricsTotal Citations87Total Downloads1,653Last 12 Months71Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Given n real numbers $0 \leq x_1 , \ldots , x_n < 1$ and a permutation $\sigma $ of $\{ 1, \ldots ,n \}$, we can always find $\bar x_1 , \cdots ,\bar x_n \in \{ 0,1 \}$ so that the partial sums $\bar x_1 + \cdots + \bar x_k $ and $\bar x_{\sigma 1} + \cdots + \bar x_{\sigma k} $ differ from the unrounded values $x_1 + \cdots + x_k $ and $x_{\sigma 1} + \cdots + x_{\sigma k} $ by at most $n/(n + 1)$, for $1 \leq k \leq n$. The latter bound is best possible. The proof uses an elementary argument about flows in a certain network, and leads to a simple algorithm that finds an optimum way to round.

This paper attaches a name to a natural class of combinatorial problems and points out that the class includes many important special cases. One special case, a simple problem of placing nonoverlapping labels on a rectangular map, is shown to be NP-complete.

It is possible to compute gcd $(x, y)$ efficiently with only $O(\log xy)$ additions and subtractions, when three arithmetic registers are available but not when there are only two. Several other functions, such as $x^y \bmod z$, are also efficiently computable in a small number of registers, using only addition, subtraction, and comparison.

Abstract This paper is a case study of program evolution. The author kept track of all changes made to TEX during a period of ten years, including the changes made when the original program was first debugged in 1978. The log book of these errors, numbering more than 850 items, appears as an appendix to this paper. The errors have been classified into fifteen categories for purposes of analysis, and some of the noteworthy bugs are discussed in detail. The history of the TEX project can teach valuable lessons about the preparation of highly portable software and the maintenance of programs that aspire to high standards of reliability.

This paper describes a technique for approximating real-valued pixels by two-valued pixels. The new method, called dot diffusion, appears to avoid some deficiencies of other commonly used techniques. It requires approximately the same total number of arithmetic operations as the Floyd-Steinberg method of adaptive grayscale, and it is well suited to parallel computation; but it requires more buffers and more complex program logic than other methods when implemented sequentially. A “smooth” variant of the method may prove to be useful in high-resolution printing.

Coding schemes in which each codeword contains equally many zeros and ones are constructed in such a way that they can be efficiently encoded and decoded.

It is shown that the multiplier, the increment, and the seed value of a linear congruential random number generator on a binary computer can be deduced from the leading bits of the "random" numbers that are generated.

An efficient algorithm for communicating letter-shape information from a high-speed computer with a large memory to a typesetting device that has a limited memory is presented. The encoding is optimum, in the sense that the total time for typesetting is minimized, using a model that generalizes well-known “demand paging” strategies to the case where changes to the cache are allowed before the associated information is actually needed. Extensive empirical data show that good results are obtained even when difficult technical material is being typeset on a machine that can store information concerning only 100 characters. The methods of this paper are also applicable to other hardware and software caching applications with restricted lookahead.

The author and his associates have been experimenting for the past several years with a programming language and documentation system called WEB. This paper presents WEB by example, and discusses why the new system appears to be an improvement over previous ones.

Abstract This paper discusses a new approach to the problem of dividing the text of a paragraph into lines of approximately equal length. Instead of simply making decisions one line at a time, the method considers the paragraph as a whole, so that the final appearance of a given line might be influenced by the text on succeeding lines. A system based on three simple primitive concepts called ‘boxes’, ‘glue’, and ‘penalties’ provides the ability to deal satisfactorily with a wide variety of typesetting problems in a unified framework, using a single algorithm that determines optimum breakpoints. The algorithm avoids backtracking by a judicious use of the techniques of dynamic programming. Extensive computational experience confirms that the approach is both efficient and effective in producing high‐quality output. The paper concludes with a brief history of line‐breaking methods, and an appendix presents a simplified algorithm that requires comparatively few resources.

An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings. The constant of proportionality is low enough to make this algorithm of practical use, and the procedure can also be extended to deal with some more general pattern-matching problems. A theoretical application of the algorithm shows that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time. Other algorithms which run even faster on the average are also considered.

This paper discusses dynamic properties of data structures under insertions and deletions It is shown that, in certain circumstances, the result of n random insertions and m random deletions will be equivalent to n-m random insertions, under various interpretations of the world "random" and under various constraints on the order of insertions and deletions.

A complicated expression for the average number of active modules, in a published model for interleaved memory, is shown to be a function well studied in other contexts.

Abstract : Some variants of the traditional hash method, making use of the numerical or alphabetical order of the keys, lead to faster searching at the expense of a little extra work when items are inserted. The paper presents the new algorithms and analyzes their average running time. (Author)

Abstract A sample of programs, written in FORTRAN by a wide variety of people for a wide variety of applications, was chosen ‘at random’ in an attempt to discover quantitatively ‘what programmers really do’. Statistical results of this survey are presented here, together with some of their apparent implications for future work in compiler design. The principal conclusion which may be drawn is the importance of a program ‘profile’, namely a table of frequency counts which record how often each statement is performed in a typical run; there are strong indications that profile‐keeping should become a standard practice in all computer systems, for casual users as well as system programmers. This paper is the report of a three month study undertaken by the author and about a dozen students and representatives of the software industry during the summer of 1970. It is hoped that a reader who studies this report will obtain a fairly clear conception of how FORTRAN is being used, and what compilers can do about it.

The techniques of automatic programming are useful for constructive proofs in automata theory. A formal definition of an elementary programming language for a stack automaton is given, and it is shown how this may be readily adapted to other classes of automata. The second part of this paper shows how this programming language can be applied to automata theory, as we prove there are non-context-sensitive languages accepted by a stack automaton.

This paper illustrates the use of SOL, a general-purpose algorithmic language useful for describing and simulating complex systems. Such a system is described as a number of individual processes which simultaneously enact a program very much like a computer program. (Some features of the SOL language are directly applicable to programming languages for parallel computers, as well as for simulation.) Once a system has been described in the language, the program can be translated by the SOL compiler into an interpretive code, and the execution of this code produces statistical information about the model. A detailed example of a SOL model for a multiple on-line console system is exhibited, indicating the notational simplicity and intuitive nature of the language.

This paper gives a formal definition of SOL, a general-purpose algorithmic language useful for describing and simulating complex systems. SOL is described using meta-linguistic formulas as used in the definition of ALGOL 60. The principal differences between SOL and problem-oriented languages such as ALGOL or FORTRAN is that SOL includes capabilities for expressing parallel computation, convenient notations for embedding random quantities within arithmetic expressions and automatic means for gathering statistics about the elements involved. SOL differs from other simulation languages such as SIMSCRIPT primarily in simplicity of use and in readability since it is capable of describing models without including computer-oriented characteristics.

The need for latency minimization m many programs for certain computers is qmte pronounced, as quantitative results indicate.OptHmzmg computer instructions includes many things besides merely assigning locations optimally.There are rigorous mathematmal methods for formulating the latency problem into a series of integer programming problems, and a mechamcal technique has also been developed for iterating on chosen locations in an attempt to improve the choices.The most practical way discovered for minimizing latency, however, has been to let people do the job manually with a semisystematic procedure and to use computers for the routine phases and for checking the human output. I. COMPARISON OF PRESENT METHODS