COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "setup.abs[bib,csr]" source file
C00003 00003	.begin center
C00005 00004	STAN-CS-79-729
C00007 00005	STAN-CS-79-730
C00008 00006	STAN-CS-79-731
C00011 00007	STAN-CS-79-732
C00013 00008	STAN-CS-79-733
C00015 00009	STAN-CS-79-734
C00017 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↔(month)

-↔-
-↔-
.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.
.skip
.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 ubareas 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().  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
-↔-