perm filename DEC.ABS[BIB,CSR]3 blob sn#386190 filedate 1978-10-10 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00007 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE C00003 00003 .once center <<general instructions>> C00005 00004 %3STAN-CS-78-681 SET REPRESENTATION AND SET INTERSECTION C00009 00005 %3STAN-CS-78-683 STORING A SPARSE TABLE C00012 00006 %3STAN-CS-78-685 SPARSE AND PARALLEL MATRIX COMPUTATIONS C00016 00007 %3 C00018 ENDMK C⊗; .REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE .every heading (December Reports,,{Page}) .at "∞" ⊂"%4α∞%*"⊃ .next page .once center <<general instructions>> %3MOST RECENT CS REPORTS - DECEMBER 1978%1 @Listed below are abstracts of the most recent reports published by the Computer Science Department of 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 December 4, 1978. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first serve basis. In 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 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 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-681 SET REPRESENTATION AND SET INTERSECTION %3Author:%1 Luis Trabb Pardo↔(Thesis) .end @%3Abstract:%1@This work discusses the representation and manipulation of sets based on two different concepts: tries, and hashing functions. @The sets considered here are assumed to be static: once created, there will be no further insertions or deletions. For both trie- and hash-based strategies, a series of representation is introduced which together with the availability of preprocessing reduces the average sizes of the sets to nearly optimal values, yet retains the inherently good retrieval characteristics. @The intersection procedure for trie-based representations is based on the traversal in parallel of the tries representing the sets to be intersected, and it behaves like a series of binary searches when the sets to be intersected are of very different sizes. Hashed intersection runs very fast. The average time is proportional to the size of the smallest set to be intersected and is independent of the number of sets (except for the intersection set itself which has to be checked for every set). .break .begin nofill No. of pages: 85 Cost: $ 4.10 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-682 PARSING FLOWCHARTS AND SERIES-PARALLEL GRAPHS %3Author:%1 Jacobo Valdes ↔(Thesis) .end @%3Abstract:%1@The main results presented in this work are an algorithm for the recognition of General Series Parallel (GSP) digraphs and an approach to the structural analysis of the control flow graphs of programs. @The GSP recognition algorithm determines in %2O(n+m)%1 steps whether an acyclic digraph with %2n%1 vertices and %2m%1 edges is GSP, and if it is, describes its structure in terms of two simple operations on digraphs. The algorithm is based on the relationship between GSP digraphs and the more standard class of TTSP multidigraphs. @Our approach to the analysis of flow graphs uses the triconnected components algorithm to find single-entry, single-exit regions. Under certain conditions -- that we identify -- this method will produce structural information suitable for the global flow analysis of control flow graphs in time proportional to the numer of vertices and edges of the graph being analyzed. .break .begin nofill No. of pages: 233 Available in microfiche only. %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-683 STORING A SPARSE TABLE %3Author:%1 Robert Endre Tarjan .end @%3Abstract:%1@The problem of storing and searching large sparse tables arises in compiling and in other areas of computer science. The standard technique for storing such tables is hashing, but hashing has poor worst-case performance. We consider good worst-case methods for storing a table of %2n%1 entries, each an integer between %2O%1 and %2N-1%1. For dynamic tables, in which look-ups and table additions are intermixed, the use of a trie requires %2O(kn)%1 storage and allows %2O(log↓k(N/n))%1 worst-case access time, where %2k%1 is an arbitrary parameter. For static tables, in which the entire table is constructed before any look-ups are made, we propose a method which requires %2O(n log∩[(l)]n)%1 storage and allow %2O(l log↓n N)%1 access time, where %2l%1 is an arbitrary parameter. Choosing %2l = log↑* n%1 gives a method with %2O(n)%1 storage and %2O((log↑* n)(log↓n N))%1 access time. .begin nofill No. of pages: 23 Cost: $ 2.35 %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-684 THE MATRIX INVERSE EIGENVALUE PROBLEM FOR PERIODIC JACOBI MATRICES %3Authors:%1 D. L. Boley and G. H. Golub↔SU326 P30-64 .end @%3Abstract:%1@A stable numerical algorithm is presented for generating a periodic Jacobi matrix from two sets of eigenvalues and the product of the off-diagonal elements of the matrix. The algorithm requires a simple generalization of the Lanczos algorithms. It is shown that the matrix is not unique, but the algorithm will generate all possible solutions. .begin nofill No. of pages: 18 Available in microfiche only. %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-685 SPARSE AND PARALLEL MATRIX COMPUTATIONS %3Author:%1 Franklin Tai-cheung Luk↔(Thesis) .end @%3Abstract:%1@This thesis deals with four important matrix problems: (1) the application of many variants of the conjugate gradient method for solving matrix equations, (2) the solution of lower and upper bounds quadratic programs associated with M-matrices, (3) the construction of a Block Lanczos method for computing the greatest singular values of a matrix, and (4) the computation of the singular value decomposition of a matrix of the ILLIAC-IV computer. .begin nofill No. of pages: 168 Available in microfiche only. %4-------------------------------------------------------------------------------------%1 %3STAN-CS-78-686 EXTERNAL HASHING SCHEMES FOR COLLECTIONS OF DATA STRUCTURES %3Author(s):%1 Richard J. Lipton, Arnold L. Rosenberg and Andrew C. Yao .end @%3Abstract:%1@We study the use of external hashing schemes for storing broad classes of data structures. Our general framework considers a class of data structures partitioned into smaller classes by the number of positions in the structure. For instance, we could start with the class of all binary trees and partition that class into the subclasses %2C%1↓1,%2C%1↓2,...%1 , each %2C↓n%1 comprising all %2n%1-node binary trees. The main results establish nonconstructively the existence of an external hashing scheme %2h↓n%1 with %2O(n)%1 -storage demand and %2O(1)%1 -expected access time, that will store any structure in %2C%1↓1%2α∪C%1↓2%2α∪...α∪C↓n%1 , provided %2C↓n%1 contains a number of structures growing at most exponentially in %2n%1. Classes of data structures subsumed by these results include ragged arrays, binary trees, string-indexed arrays, and refinable arrays. .begin nofill No. of pages: 33 Cost: $ 2.65 %4-------------------------------------------------------------------------------------%1 %3 %3Author:%1 .end @%3Abstract:%1@ .begin nofill No. of pages: Cost: $ %4-------------------------------------------------------------------------------------%1 %3 %3Author:%1 .end @%3Abstract:%1@ .begin nofill No. of pages: Cost: $ %4-------------------------------------------------------------------------------------%1