Preprints of Recent Papers
Electronic approximations to most of the papers I've written since 1990 can be
downloaded by clicking appropriate links below. In general, these files
are in plain TeX format, and they represent the initial form of the paper
before copy editing and other improvements made by the publishers.
To typeset many of these files you will need
Macros for illustrations
picmac.tex (2458 bytes).
Sometimes you also need to generate illustrations with the
MetaPost
source files provided. The published papers often include illustrations that
are not available in electronic form.
Of course users of these files should not violate the copyrights
of the publishers.
These preprints are classified into four categories:
In each group the papers are listed in reverse chronological order.
Identification numbers like P156 and Q133 refer to my
list of publications,
where complete bibliographic data can be found.
Refereed Papers
The following papers have been refereed:
- P160 Efficient coroutine generation of constrained Gray sequences, aka ``Deconstructing coroutines'' (written with Frank Ruskey).
- TeX file deco.tex;
MetaPost illustrations;
another illustration;
Compressed PostScript
- P159 Dancing links.
- TeX file;
MetaPost illustrations (B&W);
MetaPost illustrations (color);
Compressed PostScript (black-and-white version);
Compressed PostScript (color version);
Wassermann's beautiful solutions to the Aztec Diamond challenge
- P158 Linear probing and graphs.
- TeX file
lpg.tex (7558 bytes)
- P157 Shellsort with three increments.
- TeX file
swti.tex (15822 bytes)
- P156 Overlapping Pfaffians.
- TeX file
op.tex (14020 bytes)
- P154 The Knowlton-Graham partition problem.
- TeX file
kgpp.tex (5134 bytes)
- P153 Partitioned tensor products and their spectra.
- TeX file
ptpats.tex (7678 bytes);
MetaPost file
ptpats.mp (1465 bytes)
- P152 On the inversion of y-to-the-alpha times e-to-the-y
by means of associated Stirling numbers.
- TeX file
cr.tex (4792 bytes);
TeX refs file
crrefs.tex (824 bytes)
- P151 Irredundant intervals.
- CWEB file
interval.w (17672 bytes);
change file
interval-verbose.ch (337 bytes)
- P150 Aztec diamonds, checkerboard graphs, and spanning trees.
- TeX file
aztec.tex (7265 bytes)
- P149 An exact analysis of stable allocation.
- TeX file
easa.tex (10384 bytes)
- P148 The sandwich theorem.
- TeX file
sand.tex (38988 bytes);
MetaPost file
sand.mp (618 bytes)
- P147 Leaper graphs.
- TeX file
lg.tex (23749 bytes)
- P146 Polynomials involving the floor function.
- TeX file
piff.tex (7384 bytes)
- P145 Two-way rounding.
- TeX file
twr.tex (13408 bytes)
- P144 Mini-indexes for literate programs.
- TeX file
milp.tex (15415 bytes);
CWEB file
ham.w (2911 bytes);
change file
ham.ch (524 bytes);
CTWILL file
system.bux (288 bytes)
- P143 Bracket notation for the coefficient-of operator.
- TeX file
bnfc.tex (10866 bytes)
- P142 Johann Faulhaber and sums of powers.
- TeX file
jfsp.tex (18858 bytes)
- P141 Convolution polynomials.
- TeX file
cp.tex (21312 bytes)
- P140 The birth of the giant component.
- TeX file
bgc.tex (113574 bytes)
- P139 Context-free multilanguages.
- TeX file
cfm.tex (13272 bytes)
- P138 Theory and practice.
- TeX file
tap.tex (10741 bytes)
- P137 Two notes on notation.
- TeX file
tnn.tex (25788 bytes)
- P136 A note on digitized angles.
- TeX file
nda.tex (8439 bytes)
- P135 Textbook examples of recursion.
- TeX file
ter.tex (15168 bytes)
- P134 Nested satisfiability.
- TeX file
ns.tex (5653 bytes)
- P132 The problem of compatible representatives.
- TeX file
pcr.tex (8326 bytes)
- P127 Stable husbands.
- TeX file
sh.tex (15411 bytes)
- P123 Efficient representation of perm groups.
- TeX file
erpg.tex (13113 bytes)
Unrefereed Papers
The following invited papers did not benefit from the formal refereeing
mechanisms:
- Q241 Randomness in music
- Compressed PostScript file
randomness.ps.gz (254K bytes)
- Q204 Three Catalan bijections
- Compressed PostScript file
tcb.ps.gz (70K bytes)
- Q201 Robert W Floyd, In Memoriam
- Compressed PostScript file
floyd.ps.gz (741K bytes)
- Q171 Teach Calculus with Big O (unabridged version)
- TeX file
ocalc.tex (7860 bytes)
- Q145 Foreword to A=B by Petkovsek, Wilf, and Zeilberger.
- TeX file
pwz.tex (1487 bytes)
- Q133 This Week's Citation Classic: Artistic programming.
- TeX file
artprog.tex (2390 bytes)
- Q130 Icons for TeX and METAFONT.
- TeX file
icons.tex (7112 bytes)
- Q115 Memories of Andrei Ershov.
- TeX file
ershov.tex (2317 bytes)
- Q114 The genesis of attribute grammars.
- TeX file
gag.tex (17167 bytes)
Unpublications
The following documents are essentially notes to myself and a few colleagues;
I don't intend to polish them for publication, although they might form
the nucleus of later work. I suggest that you download them only if you
haven't been able to find anything more exciting to read on the World Wide Web.
- Bipermutations (96.06.28)
- TeX file
biperm.tex (5785 bytes)
- Squared differences of uniform deviates (95.07.18)
- TeX file
sdud.tex (1588 bytes)
- An interesting bijection (95.05.17)
- TeX file
ib.tex (5047 bytes)
- Solution to AMM problem 10430 (95.02.24)
- TeX file
10430.tex (2145 bytes)
- Solution to AMM problem 10424 (95.02.24)
- TeX file
10424.tex (744 bytes)
- Labeled bipartite trees (94.04.05)
- TeX file
lbt.tex (1543 bytes)
- Nonattacking kings on a chessboard (94.02.23)
- TeX file
nkc.tex (2674 bytes)
- Combinatorial matrices (93.01.07)
- TeX file
cm.tex (6621 bytes)
- A bilinear identity (91.23.08)
- TeX file
abi.tex (1847 bytes)
- An integer programming problem unsolved for 35 years (99.03.06)
- TeX file
prob.tex (4069 bytes);
data file (4781 bytes)
- A curious sequence of sets (08.01.17)
- Compressed PostScript file
curious.ps.gz (266328 bytes)
- Diamonds and dragons: Notes on generalized dragon curves (10.09.24)
- Compressed PostScript file
diamonds-and-dragons.ps.gz (75351 bytes)
- Comments on JRM problem 2680 (11.01.10)
- TeX file
JRM2680.tex (7731 bytes);
PDF (82032 bytes)
- Problems that Philippe would have loved (14.06.16)
- PDF (405217 bytes)
- Conjectures about set partitions and generating functions (18.01.06)
- text file (3K bytes)
- A conjecture about noncrossing partitions (19.02.06)
- PDF (83041 bytes)
- A computational proof of Huang's degree theorem (19.07.27)
- PDF (74334 bytes)
- Culinary arts and Computer Science (19.09.28)
- PDF (54107 bytes)
- Plausible but bad probabilistic reasoning (19.12.30)
- PDF (47971 bytes)
- Asymptotic size of search trees for Fibonacci matchings (20.02.04)
- PDF (126828 bytes)
- Signed skeletons (20.04.24)
- PDF (133792 bytes)
- Whirlpool permutations (20.05.17)
- PDF (124838 bytes)
- Coups de grâceful graphs (20.11.16)
- PDF (109721 bytes)
- Amazing grace (21.01.01)
- PDF (149072 bytes)
- Von Neumann's 1945 manuscript on sorting (21.04.10)
- PDF (158454392 bytes)
- Baxter matrices (21.09.05)
- PDF (107937 bytes)
- Xqueens and Xqueenons (21.10.06)
- PDF (124067 bytes)
- Ambidextrous numbers (22.09.07)
- PDF (241670 bytes)
- The CVM algorithm for estimating distinct elements in streams (23.05.25)
- PDF (232859 bytes)
- Parades and poly-Bernoulli numbers (24.03.14)
- PDF (329242 bytes)
Miscellaneous
- Q167 O Calculus: A letter about calculus reform
- TeX file
ocalc.tex (7853 bytes)
- R47 Stanford's CS204 Problem Seminar 1985, edited by Ramsey Haddad
- PDF file (4.9MB)
Complete list of all Knuth's papers
Don Knuth's home page