@make(PublicationOrderForm,Number 17,AnnouncementDate "June 1982")
@begin(center)
List Number 17
@end(center)
@Entry(Code "STAN-CS-82-901",
	Title "Optimal Font Caching",
	Author "David R. Fuchs and Donald E. Knuth",
	Price "$2.60",
	Mprice "$2.00",
	Note "19 pages",
	Date "May 1982")


An efficient algorithm is presented for communicating letter-shape 
information from a high-speed computer with a 
large memory to a typesetting device that has a limited memory. 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 shows 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.


@Entry(Code "STAN-CS-82-902",
	Title "Special Relations in Program-Synthetic Deduction",
	Author "Zohar Manna and Richard Waldinger",
	Price "$4.25",
	Mprice "$2.00",
	Note "75 pages",
	Date "May 1982",)


Program synthesis is the automated derivation of a computer program from a
given specification.  In the deductive approach, the synthesis of a
program is regarded as a theorem-proving problem.  
The desired program is constructed as a byproduct of the proof.
This paper presents a formal 
deduction system for program synthesis, with special features
for handling equality, the equivalence connective, and ordering relations.
 
In proving theorems involving the equivalence connective, it is awkward to
remove all the quantifiers prior to proving the theorem.  The system
therefore deals with partially skolemized sentences, in which some
of the quantifiers may be left in place.  A rule is provided for removing
individual quantifiers when required after the proof is underway.

The system is also nonclausal; i.e., the theorem does not need 
to be put into conjunctive normal form.  The equivalence, implication, 
and other connectives may be left intact.

@Entry(Code "STAN-CS-82-903",
	Title "Coloring Maps and the Kowalski Doctrine",
 	Author "John McCarthy",
	Price "$2.25",
	Mprice "$2.00",
	Note "8 pages",
	Date "April 1982")

It is attractive to regard an algorithm as composed of the logic
determining what the results are and the control determining how the result is
obtained.  Logic programmers like to regard programming as controlled deduction,
and there have been several proposals for controlling the deduction expressed
by a PROLOG program and not always using PROLOG's normal backtracking
algorithm.  The present note discusses a map coloring program proposed by
Pereira and Porto and two coloring algorithms that can be regarded as control
applied to its logic.  However, the control mechanisms required go far beyong
those that have been contemplated in the PROLOG literature.

@Entry(Code "STAN-CS-82-904",
	Title "Time-Split Methods for Partial Differential",
	Author "Randall John LeVeque",
	Price "$5.05",
	Mprice "$2.00",
	Note "102 pages",
	Date "April 1982")

This thesis concerns the use of time-split methods
for the numerical solution of time-dependent
partial differential equations.  Frequently the
differential operator splits additively into two or more pieces
such that the corresponding subproblems 
are each easier to solve than the original equation, or are best
handled by different techniques.  In the time-split method the solution
to the original equation is advanced by alternately solving the subproblems.
In this thesis a unified approach to splitting methods is developed which
simplifies their analysis.  Particular emphasis is given to splittings of hyperbolic 
problems into subproblems with disparate wave speeds.
 
Three main aspects of the method are considered.  The first is the
accuracy and efficiency of the time-split method relative to unsplit methods.  We derive a general
expression for the splitting error and use it to compute the overall truncation
error for the time-split method.  This is then used to analyze its efficiency,
measured by the amount of work required to obtain a given accuracy.    

The second topic is stability for split methods.  After
a demonstration that in general the product of two stable operators need not be stable, some 
important classes of hyperbolic splittings are identified for which the product of
stable approximate solution operators is in fact stable.  
 
The final topic is the proper specification of boundary data
for the intermediate solutions, e.g., the
solution obtained after solving only one of the subproblems.  A  procedure
is described which, for many problems, can be used to transform the 
given boundary conditions for the original equation
into arbitrarily accurate boundary conditions for the intermediate solutions.  
Stability of the initial-boundary value problem is also discussed.
 
The main emphasis is on hyperbolic problems, and the one-dimensional shallow water
equations are used as a specific example throughout.  
The final chapter is devoted to some other applications of the
theory. Two-dimensional hyperbolic problems, 
convection-diffusion equations, and the Peaceman-Rachford
ADI method for the heat equation are considered.


@Entry(Code "STAN-CS-82-905",
	Title "Wave Propagation and Stability for Finite Difference Schemes",
	Author "Lloyd N. Trefethen",
	Price "$8.20",
	Mprice "$2.00",
	Note "207 pages",
	Date "April 1982")

This dissertation investigates the behavior of finite difference
models of linear hyperbolic partial differential equations.
Whereas a hyperbolic equation is nondispersive and nondissipative,
difference models are invariably dispersive, and often dissipative too.
We set about analyzing them by means of existing techniques
from the theory of dispersive wave propagation, making extensive use in
particular of the concept of it group velocity, the velocity
at which energy propagates.
The first three chapters present a general analysis
of wave propagation in difference models.
We describe systematically the effects of dispersion on numerical
errors, for both smooth and parasitic waves.
The reflection and transmission of waves at boundaries and
interfaces are then studied at length.
The key point for this is a distinction introduced here between it leftgoing
and it rightgoing signals, which is based not on the characteristics
of the original equation, but on the group velocities of the numerical model.

The last three chapters examine it stability for finite
difference models of it initial boundary value problems.
We show that the abstract stability criterion of Gustafsson, Kreiss, and
Sundstrom (GKS) is equivalent to the condition
that the boundary permit no rightgoing signals in the absence of leftgoing ones.
Wave propagation arguments yield a proof that for the typical instability
of ``strictly rightgoing'' type, one has unstable 
growth in the l2 norm, not just in the complicated GKS norm.
We prove that this growth is at least proportional to the number of time steps
n for models driven by boundary data, and
to sqrt n for models driven by initial data.
We show further that most GKS-unstable boundaries exhibit it
infinite reflection coefficients, which gives
an alternative explanation of instability with respect to initial data.
We conjecture
that when an infinite reflection coefficient is present, the unstable growth rate
increases from sqrt n to n.

Throughout the dissertation, wave propagation ideas are also applied to
various more specialized stability problems.
We identify new classes of unstable formulas,
including some in two space dimensions;
derive new results relating stability to dissipativity;
give new estimates on unstable growth for problems
with two boundaries or interfaces; examine borderline cases
that are GKS-unstable but l2-stable or nearly so;
and present an explanation based on dispersion for
known results on instability in Lp norms.

@Entry(Code "STAN-CS-82-906",
	Title "Truncated-Newton Methods",
	Author "Stephen G. Nash",
	Price "$5.60",
	Mprice "$2.00",
	Note "120 pages",
	Date "May 1982")

	The problem of minimizing a real-valued function F of n variables
arises in many contexts.  Most methods for solving this problem have their
roots in Newton's method, i.e. they are based on approximating F by a
quadratic function Q.  If the number of variables n is large, then Newton's
method can be problematic since it requires the computation and storage of the 
Hessian matrix of second derivatives.
	We examine a flexible class of methods, called truncated-Newton 
methods.  They are based on approximately minimizing the quadratic function Q 
using an iterative scheme.  A truncated-Newton algorithm is made up of
two sub-algorithms:  an outer non-linear algorithm controlling the entire
minimization, and an inner linear algorithm for approximately minimizing Q.
	The most important choice is the selection of the inner algorithm.
When the Hessian matrix is known to be positive-definite everywhere, then
the basic linear conjugate-gradient algorithm can be used.  If not, Q may not
have a minimum.  We have used the correspondence between the linear 
conjugate-gradient algorithm and the Lanczos algorithm for tridiagonalizing
a symmetric matrix to develop methods for the indefinite case.
	The performance of the inner algorithm can be greatly improved
through the use of preconditioning strategies.  A number of 
preconditioning strategies are derived here.
	Numerical tests show that a carefully chosen truncated-Newton method
can perform significantly better than the best non-linear conjugate-gradient
algorithms available today.  This is important since the two classes of methods
have comparable storage and operation counts, and they are the only methods
available for solving many large-scale problems.

@Entry(Code "STAN-CS-82-907",
	Title "Combinatorial Algorithms I",
	Author "Ernst W. Mayr",
	Price "$4.50",
	Mprice "$2.00",
	Note "83 pages",
	Date "May 1982")

This report is an edited collection of the class notes prepared for course
253A of the same title which was taught by the author at the Department of
Computer Science at Stanford University in the Winter Quarter 1982.  The topics
selected for an covered during the first part of this two quarter graduate
course were Higher Level Data Structures, Selection, Minimum Spanning Trees,
Path Compression, Pattern Matching in Strings, Searching Graphs with Applications,
Maximum Matchings in Graphs, and Maximum Flow in Networks.

@newpage

@Entry(Code "STAN-CS-82-908",
	Title "Neomycin-Reconfiguring A Rule-Based Expert System for Application
		to Teaching",
	Author "Willlam J. Clancey and Reed Letsinger",
	Price "$2.40",
	Mprice "$2.00",
	Note "12 pages",
	Date "May 1982")

	NEOMYCIN is a medical consultation system in which MYCIN's knowledge
base is reorganized and extended for use in GUIDON, a teaching program.
The new system constitutes a psychological model for doing diagnosis, 
designed to provide a basis for interpreting student behavior and teaching 
diagnostic strategy.  The model separates out kinds of knowledge that are 
procedurally embedded in MYCIN's rules and so inaccessible to the
teaching program.  The key idea is to represent explicitly and separately:
a domain-independent diagnostic strategy in the form of meta-rules,
knowledge about the structure of the problem space, causal and 
data/hypothesis rules, and world facts.
	As a psychological model, NEOMYCIN captures the forward-directed, 
"compiled association" mode of reasoning that characterizes expert behavior.
Collection and interpretation of data are focused by the "differential" or 
working memory of hypotheses.   Moreover, the knowledge base is broadened
so that GUIDON can teach a student when to consider a specific infectious 
disease and what competing hypotheses to consider, essentially the knowledge
a human would need in order to use the MYCIN consultation system properly.

@Entry(Code "STAN-CS-82-909",
	Title "Plan Recognition Strategies in Student Modeling:  Prediction and
		Description",
	Author "Bob London and William J. Clancey",
	Price "$2.40",
	Mprice "$2.00",
	Note "13 pages",
	Date "May 1982")

	This paper describes the student modeler of the GUIDON2 tutor,
which understands plans by a dual search strategy.  It first produces
multiple predictions of student behavior by a model-driven simulation of
the expert.  Focused, data-driven searches then explain incongruities.  By
supplementing each other, these methods lead to an efficient and robust
plan understander for a complex domain.

@Entry(Code "STAN-CS-82-910",
	Title "Exploration of Teaching and Problem-Solving Strategies, 1979-1982",
	Author "Willlam J. Clancey and Bruce G. Buchanan",
	Price "$2.50",
	Mprice "$2.00",
	Note "17 pages",
	Date "May 1982")

	This is the final report for ONR Contract N-00014-79-C-0302, covering
the period of 15 March 1979 through 14 March 1982.  The goal of the project
was to develop methods for representing teaching and problem-solving
knowledge in computer-based tutorial systems.  One focus of the work was 
formulation of principles for managing a case method tutorial dialogue; the 
other major focus was investigation of the use of 
a production rule representation for the subject material of 
tutorial program.  The main theme pursued by this research is that
representing teaching and problem-solving knowledge separately and explicitly
enhances the ability to build, modify and test complex tutorial programs.

@Entry(Code "STAN-CS-82-911",
	Title "Bibliography of Stanford Computer Science Reports 1963-1982",
	Author "Barbara J. Roberts and Irris Marashian",
	Price "$4.00",
	Mprice "$2.00",
	Note "61 pages",
	Date "May 1982")

This is a bibliography of Computer Science Reports from 1963 through 1982.
Each report is listed with an availability listing and the cost.

@send(order <@b{@\Sub-totals@\@Ux(@hsp(.5 inch))@\@Ux(@hsp(.5 inch))}>)
@send(order <@b{@\Publications total@\@Ux(@hsp (.5 inch))}>)
@send(order <@b{@\Sales tax@\@Ux(@hsp (.5 inch))}>)
@send(order <@b{@\Total enclosed@\@Ux(@hsp (.5 inch))}>)