COMMENT ⊗   VALID 00005 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:
C00023 ENDMK
C⊗;
.require "setup.csr[bib,csr]" source file;
.once center
%3Stanford University Computer Science Reports%1
List Number 10↔December 1980

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 (14 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 W. Matula, Yossi Shiloach and Robert E. 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.

-↔-