perm filename FOUR[BIB,CSR] blob sn#442816 filedate 1979-05-18 generic text, type C, neo UTF8

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 -↔-