bluuebunny/crossref_metadata_2025 huggingface dataset:
A Stability Criterion for Numerical Integration
Authors: Wilf Herbert S.
Published: July 2002

A necessary and sufficient condition is given for the absolute stability of multipoint numerical integration formulas for differential equations. The condition is that a certain matrix of low order, whose elements are computable from the coefficients of the integration formula, be positive definite. Two simple examples are given.
Floating-Point Arithmetics
Authors: Wadey W. G.
Published: July 2002

Three types of floating-point arithmetics with error control are discussed and compared with conventional floating-point arithmetic. General multiplication and division shift criteria are derived (for any base) for Metropolis-type arithmetics. The limitations and most suitable range of application for each arithmetic are discussed.
Generalized Multistep Predictor-Corrector Methods
Authors: Gragg William B. , Stetter Hans J.
Published: July 2002

The order
p
which is obtainable with a stable
k
-step method in the numerical solution of
y′
=
f
(
x
,
y
) is limited to
p
=
k
+ 1 by the theorems of Dahlquist. In the present paper the customary schemes are modified by including the value of the derivative at one “nonstep point;” as usual, this value is gained from an explicit predictor. It is shown that the order of these generalized predictor-corrector methods is not subject to the above restrictions; stable
k
-step schemes with
p
= 2
k
+ 2 have been constructed for
k
≤ 4. Furthermore it is proved that methods of order
p
actually converge like

h
p

uniformly in a given interval of integration. Numerical examples give some first evidence of the power of the new methods.
Chebyshev Solution of n+1 Linear Equations in
n
+ 1
n
Unknowns
Authors: Moursund David
Published: July 2002

An algorithm is presented for finding a solution, and the value of a solution, to
n
+ 1 linear equations in
n
unknowns. The arrangement of the computation makes it convenient for use in computing Chebyshev-type approximations by polynomials. The algorithm is particularly efficient if only the value of a solution is desired.
Program and Addressing Structure in a Time-Sharing Environment
Authors: Arden B. W. , Galler B. A. , O'Brien T. C. , Westervelt F. H.
Published: July 2002

The problem studied is the effect of a time-sharing environment on the structure of programs and on the addressing strategies which may be employed in the hardware. An account is given of some very recent developments toward reduction in the system overhead needed to facilitate time-sharing. One hardware-software scheme designed to implement this reduction is described in some detail.
Numerical Inversion of Laplace Transforms Using Laguerre Functions
Authors: Weeks William T.
Published: July 2002

A method is described for the numerical inversion of Laplace transforms, in which the inverse is obtained as an expansion in terms of orthonormal Laguerre functions. In order for this to be accomplished, the given Laplace transform is expanded in terms of the Laplace transforms of the orthonormal Laguerre functions. The latter expansion is then reduced to a cosine series whose approximate expansion coefficients are obtained by means of trigonometric interpolation. The computational steps have been arranged to facilitate automatic digital computation, and numerical illustrations have been given.
On Context-Free Languages
Authors: Parikh Rohit J.
Published: July 2002

In this report, certain properties of context-free (CF or type 2) grammars are investigated, like that of Chomsky. In particular, questions regarding structure, possible ambiguity and relationship to finite automata are considered. The following results are presented:

The language generated by a context-free grammmar is linear in a sense that is defined precisely.

The requirement of unambiguity—that every sentence has a unique phrase structure—weakens the grammar in the sense that there exists a CF language that cannot be generated unambiguously by a CF grammar.

The result that not every CF language is a finite automaton (FA) language is improved in the following way. There exists a CF language
L
such that for any
L′
⊆
L
, if
L′
is FA, an
L″
⊆
L
can be found such that
L″
is also FA, L′ ⊆
L″
and
L″
contains infinitely many sentences not in
L′
.

A type of grammar is defined that is intermediate between type 1 and type 2 grammars. It is shown that this type of grammar is essentially stronger than type 2 grammars and has the advantage over type 1 grammars that the phrase structure of a grammatical sentence is unique, once the derivation is given.
Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
Authors: Karp Richard M.
Published: July 2002

Any sequential machine
M
represents a function

f
M

from input sequences to output symbols. A function
f
is
representable
if some finite-state sequential machine represents it. The function

f
M

is called an
n-th order approximation
to a given function
f
if

f
M

is equal to
f
for all input sequences of length less than or equal to
n
. It is proved that, for an arbitrary nonrepresentable function
f
, there are infinitely many
n
such that any sequential machine representing an
n
th order approximation to
f
has more than
n
/2 + 1 states. An analogous result is obtained for two-way sequential machines and, using these and related results, lower bounds are obtained for two-way sequential machines and, using these and related results, lower bounds are obtained on the amount of work tape required online and offline Turing machines that compute nonrepresentable functions.
Tree Structures for Optimal Searching
Authors: Stanfel L. E.
Published: July 2002

It is shown that, owing to certain restrictions placed upon the set of admissible structures, some previous solutions have not characterized trees in which expected search time is minimized. The more general problem is shown to be a special case of a coding problem, which was previously formulated and solved as a linear integer programming problem, and in the special case of equally probable key requests is found to be solvable almost by inspection. Some remarks are given regarding the possibility of realizing a shorter computational procedure than would be expected from an integer programming algorithm, along with a comparison of results from the present method with those of the previous.
A Note on Dijkstra's Shortest Path Algorithm
Authors: Johnson Donald B.
Published: July 2002

An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in
O
(
n
3
) steps is disproved by showing a set of networks which take
O
(
n
2

n

) steps.
Some Aspects of Hierarchical Memory Systems
Authors: Mitra Debasis
Published: July 2002

A class of demand paging algorithms for some two-level memory hierarchies is analyzed. The typical memory hierarchy is comprised of the core and a backing device. A distance matrix characterizes the properties of the latter device. The sequence of address references directed to the hierarchy by the CPU and channels is modeled as a Markov process. A compact expression for the mean time required to satisfy the page demands is derived and this expression provides the basis for some optimization problems concerning partitionings and rearrangements of pages in the backing device. In connection with these problems, a class of random processes is defined in terms of an ordering property of a joint probability matrix which is central to memory hierarchies. Three results are given on the ordering property, its relation specifically to partitionings inherent in hierarchies and the problem of optimal rearrangements. Finally, for such a class of ordered processes, certain results due to the author are specialized to yield the solution to the problem of optimal rearrangement of pages on an assembly of magnetic bubble loops.
Testing for the Church-Rosser Property
Authors: Sethi Ravi
Published: July 2002

The central notion in a replacement system is one of a transformation on a set of objects. Starting with a given object, in one “move” it is possible to reach one of a set of objects. An object from which no move is possible is called irreducible. A replacement system is Church-Rosser if starting with any object a unique irreducible object is reached. A generalization of the above notion is a replacement system (
S
, ⇒, ≡), where
S
is a set of objects, ⇒ is a transformation, and ≡ is an equivalence relation on
S
. A replacement system is Church-Rosser if starting with objects equivalent under ≡, equivalent irreducible objects are reached. Necessary and sufficient conditions are determined that simplify the task of testing if a replacement system is Church-Rosser. Attention will be paid to showing that a replacement system (
S
, ⇒, ≡) is Church-Rosser using information about parts of the system, i.e. considering cases where ⇒ is ⇒
1
∪ ⇒
2
, or ≡ is (≡
1
∪ ≡
2
)
*
.
Numerical Inversion of Laplace Transforms Using a Fourier Series Approximation
Authors: Crump Kenny S.
Published: July 2002

A method is presented for numerically inverting a Laplace transform that requires, in addition to the transform function itself, only sine, cosine, and exponential functions. The method is conceptually much like the method of Dubner and Abate, which approximates the inverse function by means of a Fourier cosine series. The method presented here, however, differs from theirs in two important respects. First of all, the Fourier series contains additional terms involving the sine function selected such that the error in the approximation is less than that of Dubner and Abate and such that the Fourier series approximates the inverse function on an interval of twice the length of the corresponding interval in Dubner and Abate's method. Second, there is incorporated into the method in this paper a transformation of the approximating series into one that converges very rapidly. In test problems using the method it has routinely been possible to evaluate inverse transforms with considerable accuracy over a wide range of values of the independent variable using a relatively few determinations of the Laplace transform itself.
Canonical Coin Changing and Greedy Solutions
Authors: Chang Lena , Korsh James F.
Published: July 2002

A natural, and readily computable, first guess at a solution to the coin changing problem is the canonical solution. This solution is a special case of the greedy solution which is a reasonable heuristic guess for the knapsack problem. In this paper, efficient tests are given to determine whether all greedy solutions are optimal with respect to a given set of knapsack objects or coin types. These results improve or extend previous tests given in the literature. Both the incomplete and complete cases are considered.
A Queueing Model of Multiprogrammed Computer Systems Under Full Load Conditions
Authors: Brandwajn Alexandre
Published: July 2002

This paper presents a queueing model of a multiprogrammed computer system with virtual memory. Two system organizations are considered: (i) all the processes present in the system share primary storage; (ii) processes which have generated a file request (slow I/O) lose their memory space until the I/O is completed. Our model assumes balanced memory allocation among processes, and accounts for the memory sharing effect through the use of lifetime functions. The model explicitly takes into account the fact that, if a written-onto page is to be replaced at the moment of a page fault, it first has to be saved in the secondary memory. An approximate closed form solution is obtained by using an equivalence and decomposition approach. A procedure for evaluating the accuracy of the approximation is presented. The numerical examples illustrate the influence of the system and program behavior parameters taken into account in our model.
Scheduling multithreaded computations by work stealing
Authors: Blumofe Robert D. , Leiserson Charles E.
Published: July 2002

This paper studies the problem of efficiently schedulling fully strict (i.e., well-structured) multithreaded computations on parallel computers. A popular and practical method of scheduling this kind of dynamic MIMD-style computation is “work stealing,” in which processors needing work steal computational threads from other processors. In this paper, we give the first provably good work-stealing scheduler for multithreaded computations with dependencies.

Specifically, our analysis shows that the expected time to execute a fully strict computation on
P
processors using our work-stealing scheduler is
T
1
/
P
+
O
(
T
∞
, where
T
1
is the minimum serial execution time of the multithreaded computation and (
T
∞
is the minimum execution time with an infinite number of processors. Moreover, the space required by the execution is at most
S
1
P
, where
S
1
is the minimum serial space requirement. We also show that the expected total communication of the algorithm is at most
O
(
PT
∞
( 1 +

n
d

)
S
max
), where
S
max
is the size of the largest activation record of any thread and

n
d

is the maximum number of times that any thread synchronizes with its parent. This communication bound justifies the folk wisdom that work-stealing schedulers are more communication efficient than their work-sharing counterparts. All three of these bounds are existentially optimal to within a constant factor.
Algorithms for trie compaction
Authors: Al-Suwaiyel M. , Horowitz E
Published: July 2002

The trie data structure has many properties which make it especially attractive for representing large files of data. These properties include fast retrieval time, quick unsuccessful search determination, and finding the longest match to a given identifier. The main drawback is the space requirement. In this paper the concept of trie compaction is formalized. An exact algorithm for optimal trie compaction and three algorithms for approximate trie compaction are given, and an analysis of the three algorithms is done. The analysis indicate that for actual tries, reductions of around 70 percent in the space required by the uncompacted trie can be expected. The quality of the compaction is shown to be insensitive to the number of nodes, while a more relevant parameter is the alphabet size of the key.
The holodeck ray cache
Authors: Ward Gregory , Simmons Maryann
Published: July 2002

We present a new method for rendering complex environments using interactive, progressive, view-independent, parallel ray tracing. A four-dimensional
holodeck
data structure serves as a rendering target and caching mechanism for interactive walk-throughs of nondiffuse environments with full global illumination. Ray sample density varies locally according to need, and on-demand ray computation is supported in a parallel implementation. The holodeck file is stored on disk and cached in memory by a server using a least-recently-used (LRU) beam-replacement strategy. The holodeck server coordinates separate ray evaluation and display processes, optimizing disk and memory usage. Different display systems are supported by specialized drivers, which handle display rendering, user interaction, and input. The display driver creates an image from ray samples sent by the server and permits the manipulation of local objects, which are rendered dynamically using approximate lighting computed from holodeck samples. The overall method overcomes many of the conventionl limits of interactive rendering in scenes with complex surface geometry and reflectance properties, through an effective combination of ray tracing, caching, and hardware rendering.
Mechanizing UNITY in Isabelle
Authors: Paulson Lawrence C.
Published: July 2002

UNITY is an abstract formalism for proving properties of concurrent systems, which typically are expressed using guarded assignments [Chandy and Misra 1988]. UNITY has been mechanized in higher-order logic using Isabelle, a proof assistant. Safety and progress primitives, their weak forms (for the substitution axiom), and the program composition operator (union) have been formalized. To give a feel for the concrete syntax, this article presents a few extracts from the Isabelle definitions and
proofs. It discusses a small example, two-process mutual exclusion. A mechanical theory of unions of programs supports a degree of compositional reasoning. Original work on extending program states is presented and then illustrated through a simple example involving an array of processes.
Creating creativity
Authors: Shneiderman Ben
Published: July 2002

A challenge for human-computer interaction researchers and user interf ace designers is to construct information technologies that support creativity. This ambitious goal can be attained by building on an adequate understanding of creative processes. This article offers a four-phase framework for creativity that might assist designers in providing effective tools for users: (1)Collect: learn from provious works stored in libraries, the Web, etc.; (2)Relate: consult with peers and mentors at early, middle, and late stages, (3)Create: explore, compose, evaluate possible solutions; and (4)Donate: disseminate the results and contribute to the libraries. Within this integrated framework, this article proposes eight activities that require human-computer interaction research and advanced user interface design. A scenario about an architect illustrates the process of creative work within such an environment.
Fast and flexible word searching on compressed text
Authors: Silva de Moura Edleno , Navarro Gonzalo , Ziviani Nivio , Baeza-Yates Ricardo
Published: July 2002

We present a fast compression technique for natural language texts. The novelties are that (1) decompression of arbitrary portions of the text can be done very efficiently, (2) exact search for words and phrases can be done on the compressed text directly, using any known sequential pattern-matching algorithm, and (3) word-based approximate and extended search can also be done efficiently without any decoding. The compression scheme uses a semistatic word-based model and a Huffman code where the coding alphabet is byte-oriented rather than bit-oriented. We compress typical English texts to about 30% of their original size, against 40% and 35% forCompressandGzip, respectively. Compression time is close to that ofCompressand approximately half of the time ofGzip, and decompression time is lower than that ofGzipand one third of that ofCompress. We present three algorithms to search the compressed text. They allow a large number of variations over the basic word and phrase search capability, such as sets of characters, arbitrary regular expressions, and approximate matching. Separators and stopwords can be discarded at search time without significantly increasing the cost. When searching for simple words, the experiments show that running our algorithms on a compressed text is twice as fast as running the best existing software on the uncompressed version of the same text. When searching complex or approximate patterns, our algorithms are up to 8 times faster than the search on uncompressed text. We also discuss the impact of our technique in inverted files pointing to logical blocks and argue for the possibility of keeping the text compressed all the time, decompressing only for displaying purposes.
Geometric approaches to nonplanar quadric surface intersection curves
Authors: Miller James R.
Published: July 2002

Quadric surfaces occur frequently in the design of discrete piece parts in mechanical CAD/CAM. Solid modeling systems based on quadric surfaces must be able to represent intersection curves parametrically and in a fashion that allows the underlying surfaces to be partitioned. An algebraic approach originally developed by Levin meets these needs but is numerically sensitive and based on solutions to fourth-degree polynomial equations. In this paper we develop geometric approaches that are robust and efficient, and do not require solutions to polynomials of degree higher than 2.
The 1984 Snowbird Report
Authors: ASL Committee on Logic Education CORPORATE
Published: July 2002

This workshop reports that no core description of computer science is universally accepted. A model of the discipline must emphasize global issues over isolated objectives, cooperation over competition.
On the effective use and reuse of HCI knowledge
Authors: Sutcliffe Alistair
Published: July 2002

The article argues that new approaches for delivering HCI knowledge from theory to designers will be necessary in the new millennium. First the role of theory in HCI design to date is reviewed, including the progress made in cognitive theories of interaction and their impact on the design pr ocess. The role of bridging models that build on models of interaction is described, but it is argued that direct application of cognitive theory to design is limited by scalability problems. The alternative of representing HCI knowledge as claims and the role of the task-artefact approach to theory-based design are introduced. Claims are proposed as a possible bridging representation that may enable theories to frame appropriate recommendations for designers and, vice versa, enable designers to ask appropriate questions for theoretical research. However, claims provide design advice grounded in specific scenarios and examples, which limits their generality. The prospects for reuse becoming an important mode of development and the possible directions in generalizing claims for reuse are discussed, including generalizing claims beyond their original context, providing a context for reuse of claims by linking them to generic task and domain models. It is argued that generic models provide a way forward for developing reusable libraries of interactive components. The approach is illustrated from a case study of extracting claims from one information ret rieval application, generalizing claims for future reuse in information-searching tasks, and reapplying claims in the Web-based Multimedia Broker application. The article concludes by proposing that HCI knowledge should be theory-grounded, and development of reusable “designer-digestible” packets will be an important contribution in the future.
A note on the formation of free list
Authors: Waite William M. , Schorr H.
Published: July 2002

The concept of an available-space list was introduced by Newell and Shaw [1] in 1957, and has since been incorporated into a number of different systems [2-5]. The
available-space list
(or “free list”) is a list of all available memory locations. It should initially be as large as possible, and ideally it would contain every cell not used by the program. The subject of this note is the initial formation of a free list on the IBM 7090-7094, using the FORTRAN II monitor, version 2. The method presented originated while the authors were working on an implementation of the WISP [5] system for the 7090 in cooperation with Prof. M. V. Wilkes and his colleagues.
Machine controls for analysis of variance
Authors: Weldon Roger J.
Published: July 2002

A major problem in using the analysis of variance, as the number of factors increases, is the exponential rise in the number of interactions. Even though the experimenter may not be interested in these interactions it is impossible to ignore them in most experimental designs because of the problem of getting error terms.

It is natural therefore to look to the computer to handle the bulk of work involved in computing the interactions. A program device to get the computer to do this is described.
A note on the calculation of probabilities in an
F
-distribution
Authors: Smillie K. W. , Anstey T. H.
Published: July 2002

Tests of significance based on analysis of variance calculations often require the determination of the probabilities of obtaining values of
F
greater than those arising from the analysis. These probabilities are customarily obtained from tables of the
F
-distribution. However, when the calculations are done on a computer, it would be convenient if estimates of these probabilities could be calculated by the analysis of variance program and presented in the output of the results. This note gives a simple method of doing so.
Another use of FORTRAN II chaining
Authors: Drath D. G.
Published: July 2002

The letter by Ackermann appearing in the
Communications of the ACM
of May 1964, presented one of a number of the very interesting uses of the FORTRAN II CHAIN procedure. Another unusual application of this procedure has been used by some at Lockheed Missiles & Space Company for realizing a very efficient program library tape.
Additional results on key-to-address transform techniques
Authors: Lum V. Y. , Yuen P. S. T.
Published: July 2002

In an earlier paper by Lum, Yuen, and Dodd [1] experimental results comparing six commonly used key-to-address transformation techniques were presented. One transformation in that study referred to as “Lin's method” is an elaborate technique based on radix transformation. Andrew Lin has since pointed out to the authors that his method of transformation [2] consists of not just a radix transformation algorithm but also the specific ways the values of
p
and
q
are chosen as well as hardware implementation to carry out the steps of this transformation in an efficient manner. Since our study was intended for general radix transformations rather than Lin's specific implementation, we think it is more appropriate to change the label of that transformation in [1] from “Lin's method” to “generalized radix transformation method” and we use this term here.
Emancipating instances from the tyranny of classes in information modeling
Authors: Parsons Jeffrey , Wand Yair
Published: July 2002

Database design commonly assumes, explicitly or implicitly, that instances must belong to classes. This can be termed the
assumption of inherent classification
. We argue that the extent and complexity of problems in schema integration, schema evolution, and interoperability are, to a large degree, consequences of inherent classification. Furthermore, we make the case that the assumption of inherent classification violates philosophical and cognitive guidelines on classification and is, therefore, inappropriate in view of the role of data modeling in representing knowledge about application domains.

As an alternative, we propose a layered approach to modeling in which information about instances is separated from any particular classification. Two data modeling layers are proposed: (1) an
instance model
consisting of an instance base (i.e., information about instances and properties) and operations to populate, use, and maintain it; and (2) a
class model
consisting of a class base (i.e., information about classes defined in terms of properties) and operations to populate, use, and maintain it. The two-layered model provides
class independence
. This is analogous to the arguments of data independence offered by the relational model in comparison to hierarchical and network models. We show that a two-layered approach yields several advantages. In particular, schema integration is shown to be partially an artifact of inherent classification that can be greatly simplified in designing a database based on a layered model; schema evolution is supported without the complexity of operations currently required by class-based models; and the difficulties associated with interoperability among heterogeneous databases are reduced because there is no need to agree on the semantics of classes among independent databases. We conclude by considering the adequacy of a two-layered approach, outlining possible implementation strategies, and drawing attention to some practical considerations.
Computer matching
Authors: Dallaire Gene
Published: July 2002

Since discovering the technique of computer matching several years ago, government managers have been invoking this computer tool in the attempt to root out waste and fraud in their programs. Is computer matching an indispensable tool for government administrators? Or a trampling on individual rights? In the following articles, two experts debate the pros and cons.
From Washington: Secrecy versus scientific communication
Authors: Steier Rosalie
Published: July 2002

There are many issues that affect the health of science but none more pervasive than the problem of “secrecy vs. scientific communication.” Unfortunately much of the debate on this issue, which is concern to all scientists, is being held behind closed doors among a few “key people.” The status of this debate was discussed in the August issue of
Communications
. More recent developments are reviewed here.
From Washington
Authors: Steier Rosalie
Published: July 2002

The American Association for the Advancement of Science (AAAS) has recently passed a resolution opposing “continuing governmental efforts to restrict the communication or publication of unclassified research.” This statement reaffirms an AAAS resolution passed in 1982, which was against “governmental restrictions on the dissemination, exchange, or availability of unclassified knowledge.” According to the AAAS Committee on Scientific Freedom and Responsibility, the second resolution was prompted by what the society considers excessive Administration efforts to prevent export of U.S. technology to Soviet bloc countries. These measures include requesting prepublication review of unclassified technical papers, inhibiting communication of unclassified scientific research in university classrooms and research laboratories, limiting foreign student access to university research projects and results, censoring technical papers at professional society meetings, and restricting otherwise unclassified meetings to U.S. citizens.
The “Wolf Fence” algorithm for debugging
Authors: Gauss Edward J.
Published: July 2002

The “Wolf Fence” method of debugging time-sharing programs in higher languages evolved from the “Lions in South Africa” method that I have taught since the vacuum-tube machine language days. It is a quickly converging iteration that serves to catch run-time errors.
Software engineering for the Cobol environment
Authors: Evans Michael
Published: July 2002

In a attempt to improve the productivity of their 70 development staff, Skandinaviska Enskilda Banken has built an integrated set of manual and automatic tools for the implementation of Cobol programs. It was possible to use a number of modern programming techniques, including software engineering methods, in a Cobol environment. The project required 31 person-months; the aims, current status, and initial results are reported.
Computer programs for detecting and correcting spelling errors
Authors: Peterson James L.
Published: July 2002

With the increase in word and text processing computer systems, programs which check and correct spelling will become more and more common. Peterson investigates the basic structure of several such existing programs and their approaches to solving the problems which arise when this type of program is created. The basic framework and background necessary to write a spelling checker or corrector are provided.
Curriculum '78: recommendations for the undergraduate program in computer science— a report of the ACM curriculum committee on computer science
Authors: Austing Richard H. , Barnes Bruce H. , Bonnette Della T. , Engel Gerald L. , Stokes Gordon
Published: July 2002

Contained in this report are the recommendations for the undergraduate degree program in Computer Science of the Curriculum Committee on Computer Science (C
3
S) of the Association for Computing Machinery (ACM).

The core curriculum common to all computer science undergraduate programs is presented in terms of elementary level topics and courses, and intermediate level courses. Elective courses, used to round out an undergraduate program, are then discussed, and the entire program including the computer science component and other material is presented. Issues related to undergraduate computer science education, such as service courses, supporting areas, continuing education, facilities, staff, and articulation are presented.
The use of normal multiplication tables for information storage and retrieval
Authors: Motzkin Dalia
Published: July 2002

This paper describes a method for the organization and retrieval of attribute based information systems, using the normal multiplication table as a directory for the information system. Algorithms for the organization and retrieval of information are described. This method is particularly suitable for queries requesting a group of information items, all of which possess a particular set of attributes (and possibly some other attributes as well). Several examples are given; the results with respect to the number of disk accesses and disk space are compared to other common approaches. Algorithms evaluating the appropriateness of the above approach to a given information system are described. For a certain class of information systems, the normal multiplication table method yields far more rapid retrieval with a more economical space requirement than conventional systems. Moreover this method incorporates an improved modification of the inverted file technique.
Some new methods of detecting step edges in digital pictures
Authors: Schachter Bruce J. , Rosenfeld Azriel
Published: July 2002

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.
Preserving average proximity in arrays
Authors: DeMillo Richard A. , Eisenstat Stanley C. , Lipton Richard J.
Published: July 2002

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.
Convex hulls of finite sets of points in two and three dimensions
Authors: Preparata F. P. , Hong S. J.
Published: July 2002

The convex hulls of sets of n points in two and three dimensions can be determined with O(n log n) operations. The presented algorithms use the “divide and conquer” technique and recursively apply a merge procedure for two nonintersecting convex hulls. Since any convex hull algorithm requires at least O(n log n) operations, the time complexity of the proposed algorithms is optimal within a multiplicative constant.
A linear algorithm for incremental digital display of circular arcs
Authors: Bresenham Jack
Published: July 2002

Circular arcs can be drawn on an incremental display device such as a cathode ray tube, digital plotter, or matrix printer using only sign testing and elementary addition and subtraction. This paper describes methodology for producing dot or step patterns closest to the true circle.
Improving the access time for random access files
Authors: Clapson Philip
Published: July 2002

Clustering in the key set is decreased by smoothing the key-to-address transformation, and by adding shadow buckets to an open chaining file. The keys are pre-hashed before the address division, to remove the effect of sequential properties in the key set. Shadow buckets in the key search sequence reduce the effect of nonuniformity in file loading, and decrease the number of maximum probes needed to locate a record. The combined effects of these techniques lead to improved file performance for secondary storage devices, as shown by empirical studies.
Can programming be liberated from the von Neumann style?
Authors: Backus John
Published: July 2002

Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor—the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.

An alternative functional style of programming is founded on the use of combining forms for creating programs. Functional programs deal with structured data, are often nonrepetitive and nonrecursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable. Combining forms can use high level programs to build still higher level ones in a style not possible in conventional languages.

Associated with the functional style of programming is an algebra of programs whose variables range over programs and whose operations are combining forms. This algebra can be used to transform programs and to solve equations whose “unknowns” are programs in much the same way one transforms equations in high school algebra. These transformations are given by algebraic laws and are carried out in the same language in which programs are written. Combining forms are chosen not only for their programming power but also for the power of their associated algebraic laws. General theorems of the algebra give the detailed behavior and termination conditions for large classes of programs.

A new class of computing systems uses the functional programming style both in its programming language and in its state transition rules. Unlike von Neumann languages, these systems have semantics loosely coupled to states—only one state transition occurs per major computation.
A fast algorithm for computing longest common subsequences
Authors: Hunt James W. , Szymanski Thomas G.
Published: July 2002

Previously published algorithms for finding the longest common subsequence of two sequences of length n have had a best-case running time of O(n
2
). An algorithm for this problem is presented which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match. Thus in the worst case the algorithm has a running time of O(n
2
log n). However, for those applications where most positions of one sequence match relatively few positions in the other sequence, a running time of O(n log n) can be expected.
A bounded storage algorithm for copying cyclic structures
Authors: Robson J. M.
Published: July 2002

A new algorithm is presented which copies cyclic list structures using bounded workspace and linear time. Unlike a previous similar algorithm, this one makes no assumptions about the storage allocation system in use and uses only operations likely to be available in a high-level language. The distinctive feature of this algorithm is a technique for traversing the structure twice, using the same spanning tree in each case, first from left to right and then from right to left.
Systems design education
Authors: Lyons Norman R.
Published: July 2002

One of the problems facing managers of computer installations is the problem of configuring the computer system to meet the demands made by the mix of jobs that the computer center must service, This paper presents a management game that allows the player to configure a computer system to meet a hypothetical job mix. The job mix is under the control of a game administrator and can be varied to simulate a variety of real-world situations (I/0 bound jobs, compute bound jobs, etc.). The player of the game receives a set of detailed reports on the cost of his choices and a simulated run of the center operating under his choices.
Tools and philosophy for software education
Authors: Donovan John J.
Published: July 2002

This paper describes a set of tools and a philosophy for teaching software that have been found very useful in courses at MIT over the past seven years. The tools include programs such as simulators, graders, compilers, and monitors. These allow the instructor to augment the basic concepts with relevant, exciting, and economical student project activities.
Efficient generation of the binary reflected gray code and its applications
Authors: Bitner James R. , Ehrlich Gideon , Reingold Edward M.
Published: July 2002

Algorithms are presented to generate the n-bit binary reflected Gray code and codewords of fixed weight in that code. Both algorithms are efficient in that the time required to generate the next element from the current one is constant. Applications to the generation of the combinations of n things taken k at a time, the compositions of integers, and the permutations of a multiset are discussed.
The design and implementation of a table driven, interactive diagnostic programming system
Authors: Wilcox Thomas R. , Davis Alan M. , Tindall Michael H.
Published: July 2002

CAPS is a highly interactive diagnostic compiler/interpreter that allows beginning programmers to prepare, debug, and execute fairly simple programs at a graphics display terminal. Complete syntax checking and most semantic analysis is performed as the program is entered and as it is subsequently edited. Analysis is performed character by character.

The most remarkable feature of CAPS is its ability to automatically diagnose errors both at compile time and at run time. Errors are not automatically corrected. Instead, CAPS interacts with the student to help him find the cause of his error.

Most components of CAPS are table driven, both to reduce the space needed for implementation and to increase the flexibility of the multilingual system. Over 500 students have used CAPS to learn Fortran, PL/I, or Cobol in conjunction with a computer assisted course on introductory computer science.
An interactive graphic display for region partitioning by linear programming
Authors: Cheung To-Yat
Published: July 2002

Using linear programming, an interactive graphic display system has been implemented to solve the region design problem of partitioning a region into
N
nonoverlapping subregions in such a way that their areas are in specified proportions and that the total cost of servicing them is a minimum. In a conversational manner, a user can easily obtain different partitionings by specifying and modifying the boundary, the service centers' locations, the area proportions, and the cost functions. Examples are included.
Blocks—a new datatype for SNOBOL4
Authors: Gimpel James F.
Published: July 2002

A new datatype, called a block, has been implemented for SNOBOL4. A block is a three-dimensional aggregate of characters in the form of a right parallelepiped, best thought of as a three-dimensional extension to a string. (The third dimension is used for overstriking.) Blocks may be printed, concatenated in any of three dimensions, and merged on the basis of program-defined connection points. Some blocks adapt in size and shape to their environment.

Blocks and their operations are mainly used for composing printable output. A variety of graphical problems (including flowcharting, bargraphs, logic diagrams, mathematical-equation formation, and text justification and preparation) have been programmed on a printer in what appears to be an easy and natural way. In addition to these somewhat specialized applications, blocks appear to be a good general purpose device-independent output formation mechanism especially suitable for nonnumerical work.

The concept of a block is largely language independent. That is, blocks require little in the way of specialized syntax and could readily be absorbed into the external structure of most programming languages.
Graduate education
Authors: Payne W. H.
Published: July 2002

[Two years ago the author was elected by the Washington State University faculty to a three-year term as a faculty representative to a Graduate Studies Committee charged “to examine and evaluate proposed changes in the policy of the Graduate School.” After his experiences and considerable study, the author says he feels compelled to express his observations and opinions to his fellow members of the Association for Computing Machinery.]
An algorithm for the construction of bounded-context parsers
Authors: Loeckx Jacques
Published: July 2002

An algorithm is described which accepts an arbitrary context-free grammar and constructs a bounded-context parser for it whenever such a parser exists.

In the first part of the paper the definition of a context-free grammar and the working of a bounded-context parser are recalled. The notion of reduction class for a context-free grammar is then introduced and its connection with the structure of a bounded-context parser is indicated. Next, pushdown automata which generate the different reduction classes of a context-free grammar are defined. Finally, the algorithm is described; it essentially carries out an exhaustive study of all possible runs of the pushdown automata generating the reduction classes.

In the second part, the utility of the algorithm is discussed in the light of the experience gained from its use in compiler design. The algorithm is claimed to be particularly useful in the simultaneous design of a language and a compiler for it.
Comment on London's certification of algorithms 245
Authors: Redish K. A.
Published: July 2002

In his Certification of Algorithm 245 [1], Ralph L. London exhibits a common confusion between an
algorithm
, its
representation
, and its implementation on a processor—a
code
. In the present state of the art we can attempt, in general, to
prove
an algorithm and to
test
a code. For example, London states that “… the algorithm TREESORT 3 [2] is proved to perform properly its claimed task of sorting an array
M
[1:
n
] into ascending order.” While this is true of the
algorithm
, it is not true of the
code
unless we place restrictions on the array elements. The trouble arises in this example from the finite precision of processors; the Boolean expression
A
≥
B
(real
A
,
B
) will usually be implemented as
A
-
B
≥ 0, which can fail due to floating point overflow or underflow.
A language extension for graph processing and its formal semantics
Authors: Pratt Terrence W. , Friedman Daniel P.
Published: July 2002

A simple programming language “extension,” Graspe, for processing directed graphs is defined. Graspe consists of a type of directed graph data structure and a set of primitive operations for manipulating these structures. Graspe may be most easily implemented by embedding it in a host language. Emphasis is placed both on Graspe itself and on its method of definition. Commonly, the definition of a language involves definition of the syntactic elements and explanation of the meaning to be assigned them (the semantics). The definition of Graspe here is solely in terms of its semantics; that is, the data structures and operations are defined precisely but without assignment of a particular syntactic representation. Only when the language is implemented is assignment of an explicit syntax necessary. An example of an implementation of Graspe embedded in Lisp is given as an illustration. The advantages and disadvantages of the definition of a language in terms of its semantics are discussed.