perm filename FOUR[BIB,CSR]2 blob sn#436930 filedate 1979-04-30 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00019 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .require "setup.abs[bib,csr]" source file C00006 00003 STAN-CS-79-729 C00008 00004 STAN-CS-79-730 C00009 00005 STAN-CS-79-731 C00012 00006 STAN-CS-79-732 C00014 00007 STAN-CS-79-733 C00016 00008 STAN-CS-79-734 C00018 00009 STAN-CS-79-735 C00019 00010 STAN-CS-79-736 C00020 00011 STAN-CS-79-737 C00022 00012 STAN-CS-79- C00023 00013 STAN-CS-79- C00024 00014 STAN-CS-79- 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↔(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 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 and 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- 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 -↔- 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 -↔-