COMMENT ⊗   VALID 00019 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "setup.abs[bib,csr]" source file
C00005 00003	STAN-CS-79-729
C00007 00004	STAN-CS-79-730
C00008 00005	STAN-CS-79-731
C00011 00006	STAN-CS-79-732
C00013 00007	STAN-CS-79-733
C00015 00008	STAN-CS-79-734
C00017 00009	STAN-CS-79-735
C00018 00010	STAN-CS-79-736
C00019 00011	STAN-CS-79-737
C00021 00012	STAN-CS-79-738
C00023 00013	HPP-79-14
C00024 00014	STAN-CS-79-740
C00025 00015	STAN-CS-79-
C00026 00016	STAN-CS-79-
C00027 00017	STAN-CS-79-
C00028 00018	STAN-CS-79-
C00029 00019	STAN-CS-79-
C00030 ENDMK
C⊗;
.require "setup.abs[bib,csr]" source file;
.begin center
S T A N F O R D   U N I V E R S I T Y
MOST RECENT COMPUTER SCIENCE REPORTS - 1979
.end
.begin nofill
No. 4↔June

-↔-
-↔-
.end

@Listed here are abstracts of the most recent reports published by the
Department of Computer Science at Stanford University.

@TO REQUEST REPORTS:  Check the appropriate places on the enclosed order
form, and return the entire order form page (including mailing label) by
August 24, 1979.  In many cases we can print only a limited number of copies,
and requests will be filled on a first come, first serve basis.  If the code
(FREE) is printed on your mailing label, you will not be charged for hardcopy.
This exemption from payment is limited primarily to libraries.  (The costs
shown include all applicable sales taxes.  PLEASE SEND NO MONEY NOW, WAIT UNTIL 
YOU GET AN INVOICE.)

@ALTERNATIVELY:  Copies of most Stanford CS Reports may be obtained by writing
(about 2 months after the MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL
INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161.
Stanford Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North
Zeeb Road, Ann Arbor, Michigan 48106.
.begin nofill
-↔-
-↔-
STAN-CS-79-729
@A UNIFIED APPROACH TO PATH PROBLEMS
Author:  Robert Endre Tarjan
43 pages↔Cost: $2.90
.end

@We describe a general method for solving path problems on directed graphs.
Such path problems include finding shortest paths, solving sparse systems of
llinear equations, and carrying out global flow analysis of computer programs.
Our method consists of two steps.  First, we construct a collection of regular
expressions representing sets of paths in the graph.  This can be done by using
any standard algorithm, such as Gaussian or Gauss-Jordan elimination.  Next,
we apply a natural mapping from regular expressions into the given problem
domain.  We exhibit the mappings required to find shortest paths, solve sparse
systems of linear equations, and carry out global flow analysis.  Our results
provide a general-purpose algorithm for solving any path problem, and show
that the problem of constructing path expressions is in some sense the most
general path problem.
.begin nofill
-↔-
STAN-CS-79-730
@QUALIFYING EXAMINATIONS IN COMPUTER SCIENCE, 1965-1978
Editor:  Frank M. Liang
238 pages↔Cost: $8.40
.end

@Since 1965, the Stanford Computer Science Department has periodically given
"qualifying examinations" as one of the requirements of its graduate program.
These examinations are given in each of six subareas of computer science:  Programming
Languages and Systems, Artificial Intelligence, Numerical Analysis, Computer
Design, Theory of Computation, and Analysis of Algorithms.  This report presents
the questions from these examinations, and also the associated reading lists.
.begin nofill
-↔-
STAN-CS-79-731
@STANFORD PASCAL VERIFIER USER MANUAL
Authors:  D.C. Luckham, S.M. German, F.W. von Henke, R.A. Karp, P.W. Milne, D.C. Oppen, 
              W. Polak & W.L. Scherlis
? pages↔Cost: $
.end

@The Stanford Pascal verifier is an interactive program verification system.
It automates much of the work necessary to analyze a program for consistency
with its documentation, and to give a rigorous mathematical proof of such
consistency or to pin-point areas of inconsistency.  It has been shown to have
applications an an aid to programming, and to have potential for development
as a new and useful tool in the production of reliable software.

@This verifier is a prototype system.  It has inadequacies and shortcomings.
It is undergoing continuous improvement, and is expected to be used
eventually in conjunction with other kinds of program analyzers.  The
purpose of this manual is to introduce the verifier to a wider group of
users for experimentation.  We hope to encourage both feedback to help
improve this system, and the development of other program analyzers.

@The verfier is coded in Maclisp, a version of Lisp developed at M.I.T.
for PDP-10 computers.  Versions of the verifier run under the TOPS 20
operating system and the Stanford WAITS operating system.
.begin nofill
-↔-
STAN-CS-79-732
@NOTES ON INTRODUCTORY COMBINATORICS
Author:	Donald R. Woods
120 pages↔Cost: $5.10
.END

@In the spring of 1978, Professors George Polya and Robert Tarjan
teamed up to teach CS 150 -- Introduction to Combinatorics.  This report
consists primarily of the class notes and other handouts produced by the
author as teaching assistant for the course.

@Among the topics covered are elementary subjects such as
combinations and permutations, mathematical tools such as generating
functions and Polya's Theory of Counting, and analyses of specific problems
such as Ramsey Theory, matchings, and Hamiltonian and Eulerian paths.
.BEGIN NOFILL
-↔-
STAN-CS-79-733
@A LOWER BOUND TO FINDING CONVEX HULLS
Author:	Andrew Chi-Chih Yao
22 pages↔Cost: $2.35
.end

@Given a set S of %2n%1 distince points %2{(x↓i,y↓i) | 0 ≤ i < n}%1,
the %2convex hull problem%1 is to determine the vertices of the convex
hull H(S).  All the known algorithms for solving this problem have
a worst-case running time of %2cn log n%1 or higher, and employ only
%2quadratic tests%1, i.e., tests of the form
%2f(x↓0,y↓0,x↓1,y↓1,...,x∪[n-1],y∪[n-1])#:#0%1
with %2f%1 being any polynomial of degree not exceeding 2.  In this
paper, we show that any algorithm in the %2quadratic decision-tree model%1
must make %2cn log n%1 tests for some input.
.begin nofill
-↔-
STAN-CS-79-734
@FAST ALGORITHMS FOR SOLVING PATH PROBLEMS
Author:	Robert Endre Tarjan
49 pages↔Cost: $3.10
.end

@Let G = (V,E) be a directed graph with a distinguished source vertex %2s%1.
The %2single-source path expression problem%1 is to find, for each vertex %2v%1,
a regular epression P%2(s,v)%1 which represents the set of all paths in G
from %2s%1 to %2v%1.  A solution to this problem can be used to solve shortest
path problems, solve sparse systems of linear equations, and carry out 
global flow analysis [30].  We describe a method to compute
path expressions by dividing G into components, computing path expressions
on the components by Gaussian elimination, and combining the solutions.
This method requires O%2(m#αα(m,n))%1 time on a reducible flow graph, where
%2n%1 is the number of vertices in G, %2m%1 is the number of edges in G, and
%2αα%1 is a functional inverse of Ackermann's function.  The method makes use
of an algorithm for evaluating functions defined on paths in trees [9,29].
A simplified version of the algorithm, which runs in O%2(m log n)%1 time on
reducible flow graphs, is quite easy to implement and efficient in practice.
.begin nofill
-↔-
STAN-CS-79-735
@KRONECKER'S CANONICAL FORM AND THE QZ ALGORITHM
Author:  J. H. Wilkinson
23 pages↔Available in microfiche only.
.end

@In the QZ algorithm the eigenvalues of A%2x = %5l%1B%2x%1 are computed
via a reduction to the form %6~%1A%2x = %5l%6~%1B%2x%1 where %6%1A and %6%1B
are upper triangular.  The eigenvalues are given by %5l%2↓i = a∪[ii]/b∪[ii]%1.
It is shown that when the pencil %6~%1A - %5l%6~%1B is singular or nearly
singular a value of %5l%2i%1 may have no significance even when
%6~%2a∪[ii]%1 and %6~%2b∪[ii]%1 are of full size.
.begin nofill
-↔-
STAN-CS-79-736
@NOTE ON THE PRACTICAL SIGNIFICANCE OF THE DRAZIN INVERSE
Author:  J. H. Wilkinson
20 pages↔Available in microfiche only.
.end

@The solution of the differential system B%2x = %1A%2x + f%1 where A
and B are %2n %3x %2n%1 matrices and A - %5l%1B is not a singular
pencil may be expressed in terms of the Drazin inverse.  It is shown
that there is a simple reduced form for the pencil A - %5l%1B which
is adequate for the determination of the general solution and that
although the Drazin inverse could be determined efficiently from this
reduced form it is inadvisable to do so.
.begin nofill
-↔-
STAN-CS-79-737
@ON THE AVERAGE-CASE COMPLEXITY OF SELECTING THE %2k%1-th BEST
Author:  Andrew C. Yao & F. Frances Yao
45 pages↔Cost: $3.00
.end

@Let %6¬%1V%2↓(n)%1 be the minimum average number of pairwise comparisons
needed to find the %2k%1-th largest of %2n%1 numbers %2(k ≥ 2)%1, assuming
that all %2n!%1 orderings are equally likely.  D.W. Matula proved that,
for some absolute constant %2c%1, %6¬%1V%2↓k(n)-n ≥ c k log log n%1 as
%2n → α∞%1.  In the present paper, we show that there exists an absolute
constant %2c' > 0%1 such that %6¬%1V%2↓k(n)-n ≥ c' k log log n%1 as
%2n → α∞%1, proving a conjecture of Matula.
.begin nofill
-↔-
STAN-CS-79-738
@COMPUTATIONS RELATED TO G-STABILITY OF LINEAR MULTISTEP METHODS
Authors:  Randall LeVeque, Germund Dahlquist & Dan Andree
27 pages↔Available in microfiche only.
.end

@In Dahlquist's recent proof of the equivalence of A-stability and
G-stability[1], an algorithm was presented for calculating a G-stability
matrix for any A-stable linear multistep method.  Such matrices, and various
quantities computable from them, are useful in many aspects of the study
of the stability of a given method.  For example, information may be gained
as to the shap of the stability region, or the rate of growth of unstable
solutions.  We present a summary of the relvant theory and the results of
some numerical calculations performed for several backward differentiation,
Adams-Bashforth, and Adams-Moulton methods of low order.
.begin nofill
-↔-
HPP-79-14
@INDUCTION OVER LARGE DATA BASES
Author:  J. R. Quinlan
19 pages↔Cost: $2.25
.end

@Techniques for discovering rules by induction from large collections of
instances are developed.  These are based on an iterative scheme for dividing
the instances into two sets, only one of which needs to be randomly accessible.
These techniques have made it possible to discover complex rules from data
bases containing many thousands of instances.  Results of several experiments
using them are reported.
.begin nofill
-↔-
STAN-CS-79-740
@THE LOGIC OF ALIASING
Authors:  R. S. Cartwright and D. C. Oppen
?  pages↔Cost: $
.end

@We give a new version of Hoare's logic which correctly handles programs
with aliased variables.   The central proof rules of the logic (procedure
call and assignment) are proved sound and complete.
.begin nofill
-↔-
STAN-CS-79-

Author:  
   pages↔Cost: $
.end

.begin nofill
-↔-
STAN-CS-79-

Author:  
   pages↔Cost: $
.end

.begin nofill
-↔-
STAN-CS-79-

Author:  
   pages↔Cost: $
.end

.begin nofill
-↔-
STAN-CS-79-

Author:  
   pages↔Cost: $
.end

.begin nofill
-↔-
STAN-CS-79-

Author:  
   pages↔Cost: $
.end

.begin nofill
-↔-