perm filename ELEVEN.PUB[BIB,CSR]2 blob sn#570032 filedate 1981-03-09 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00008 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .require "setup.csr[bib,csr]" source file C00004 00003 %3STAN-CS-80-828: C00018 00004 %3STAN-CS-80-829: C00020 00005 %3STAN-CS-80-830: C00022 00006 %3STAN-CS-80-831: C00025 00007 %3STAN-CS-81-839: C00027 00008 %3STAN-CS-80-831: C00031 ENDMK C⊗; .require "setup.csr[bib,csr]" source file; .once center %3Stanford University Computer Science Reports%1 List Number 11↔March 1981 Listed here are abstracts of the most recent reports published by the Department of Computer Science at Stanford University. %3Request Reports:%1 Complete the enclosed order form, and return the entire order form page (including mailing label) as soon as possible. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first served basis as the reports become available. 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. %2Please send no money now, wait until you get an invoice.%1) %3Alternatively:%1 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. -↔- %3STAN-CS-80-828: %2Breaking Paragraphs Into Lines%1 by Donald E. Knuth and Michael F. Plass (66 pages, November 1980) This paper discusses a new approach to the problem of dividing the text of a paragraph into lines of approximately equal length. Instead of simply making decisions one line at a time, the method considers the paragraph as a whole, so that the final appearance of a given line might be influenced by the text on succeeding lines. A system based on three simple primitive concepts called 'boxes', 'glue', and 'penalties' provides the ability to deal satisfactorily with a wide variety of typesetting problems in a unified framework, using a single algorithm that determines optimum breakpoints. This algorithm avoids backtracking by a judicious use of the techniques of dynamic programming. Extensive computational experience confirms that the approach is both efficient and effective in producing high-quality output. The paper concludes with a brief history of line-breaking methods, and an appendix presents a simplified algorithm that requires comparatively few resources. -↔- %3STAN-CS-80-829: %2The Dinner Table Problem%1 by Bengt Aspvall and Frank Liang (13 pages, December 1980) This report contains two papers inspired by the "dinner table problem": If %2n%1 people are seated randomly around a circular table for two meals, what is the probability that no two people sit together at both meals? We show that this probability approaches %2e∩[-2]%1 as %2n → %5α∞%1, and also give a closed form. We then observe that in many similar problems on permutations with restricted position, the number of permutations satisfying a given number of properties is approximately Poisson distributed. We generalize our asymptotic argument to prove such a limit theorem, and mention applications to the problems of derangements, menages, and the asymptotic number of Latin rectangles. -↔- %3STAN-CS-80-830: %2Two Linear-Time Algorithms for Five-Coloring a Planar Graph%1 by David Matula, Yossi Shiloach and Robert Tarjan (23 pages, December 1980) A "sequential processing" algorithm using bicolor interchange that five- colors an %2n%1 vertex planar graph in O(%2n%1↑2) time was given by Matula, Marble, and Isaacson [MMI 72]. Lipton and Miller used a "bach processing" algorithm with bicolor interchange for the same problem and achieved an improved O(%2n%1 log %2n%1)time bound [LM 78]. In this paper we use graph contraction arguments instead of bicolor interchange and improve both the sequential processing and batch processing methods to obtain five-coloring algorithms that operate in O(%2n%1) time. -↔- %3STAN-CS-80-831: %2An O(nm log n) Algorithm for Maximum Network Flow%1 by Daniel D. K. Sleator (Thesis, 81 pages, December 1980) This thesis presents a new algorithm for the maximum network flow problem. The problem is this: Given a directed network of %2m%1 edges and %2n%1 vertices with two distinguished vertices, a source and a sink, and with a nonnegative capacity associated with each edge, find a way of labeling the edges with nonnegative real numbers representing flow in such a way that: (1) The flow into each vertex equals the flow out (except at the source and sink). (2) The flow at each edge does not exceed the capacity at that edge. (3) The flow out of the source is a maximum over-all flow satisfying (1) and (2). Our algorithm finds a maximum flow in %2(nm%1log%2n%1) time, which is a factor of log %2n%1 faster than the previous fastest algorithm. Our algorithm finds a maximum flow in O(%2nm%1log%2n%1) time, which is a factor of log %2n%1 faster than the previous fastest algorithm. The central innovation of our algorithm is a sophisticated data structure that is used to represent a certain subset of edges that form a forest. The edges of this forest are further partitioned into two classes: broken and solid. Long paths of solid edges are grouped together and stored in a balanced tree data structure called a biased 2-3 tree. Each leaf of the biased 2-3 tree corresponds to an edge in the path. %3STAN-CS-81-839: %2Short Waits%1 by Arthur L. Samuel (37 pages, February 1981) This is an introductory manual describing the SU-AI timesharing system that is available primarily for sponsored research in the Computer Science Department. The present manual is written for the beginner and the user interested primarily in the message-handling capability as well as for the experienced computer user and programmer who either is unfamiliar with the SU-AI computer or who uses it infrequently. References are made to the available hard-copy manuals and to the extensive on-line document files where more complete information can be obtained. The principal advantages of this system are: 1) The availability of a large repertoire of useful system features; 2) The large memory; 3) The large file-storage system; 4) The ease with which one can access other computers via the ARPA net; 5) The file transfer facilities via the EFTP program and the ETHERNET; 6) The XGP and the DOVER printers and the large collections of fonts available for them; and 7) The fast and convenient E editor with its macro facilities. -↔- %3STAN-CS-80-831: %2An O(nm log n) Algorithm for Maximum Network Flow%1 by Daniel D. K. Sleator (81 pages, December 1980) This thesis presents a new algorithm for the maximum network flow problem. The problem is this: Given a directed network of %2m%1 edges and %2n%1 vertices with two distinguished vertices, a source and a sink, and with a nonnegative capacity associated with each edge, find a way of labeling the edges with nonnegative real numbers representing flow in such a way that: (1) The flow into each vertex equals the flow out (except at the source and sink). (2) The flow at each edge does not exceed the capacity at that edge. (3) The flow out of the source is a maximum over-all flow satisfying (1) and (2). Our algorithm finds a maximum flow in O(%2nm%1log%2n%1) time, which is a factor of log %2n%1 faster than the previous fastest algorithm. The central innovation of our algorithm is a sophisticated data structure that is used to represent a certain subset of edges that form a forest. The edges of this forest are further partitioned into two classes: broken and solid. Long paths of solid edges are grouped together and stored in a balanced tree data structure called a biased 2-3 tree. Each leaf of the biased 2-3 tree corresponds to an edge in the path. The most significant property of this data structure is that it allows a variety of operations to be performed in O(log %2n%1) time. Some of these are: The traversal from any leaf of the tree to the root while accumulating information about the edges along the path (e.g. finding the minimum capacity edge); the updating of information stored at each edge (e.g. changing the current value of the flow); certain types of tree rearrangements (e.g. removing a subtree and attaching it somewhere else). It appears that this data structure can be used to get fast algorithms for other problems such as the transshipment problem, the deepest common ancestor problem where a cut operation is allowed, and the two-color minimum spanning tree problem. -↔-