Seminar in the summer term 2005

Helping Donald Knuth

Contact:

 Daniel Mölle (moelle@informatik.rwth-aachen.de) Stefan Richter (richter@informatik.rwth-aachen.de) Peter Rossmanith (rossmani@informatik.rwth-aachen.de)

Classification

Theoretical Computer Science

Time and Place

TBA

Please remember that in order to attend the seminar you have to get a proposal accepted until May 15th. To ensure timely submission you are furthermore required to have at least a first proposal submitted until the 15th of April! Do not panic, this proposal should be rather brief and in essence is to contain a short description of the question and its background as well as your solution approach.

Contents

In this seminar we are going to check several exercises by Professor Knuth.

Donald E. Knuth (), one of computer science's most prolific voices, is the author of the renowned book series "The Art of Computer Programming", three volumes of which have been completed, with four more planned. In fact, "these books were named among the best twelve scientific monographs of the century by American Scientist, along with: Dirac on quantum mechanics, Einstein on relativity, Mandelbrot on fractals, Pauling on the chemical bond, Russell and Whitehead on foundations of mathematics, von Neumann and Morgenstern on game theory, Wiener on cybernetics, Woodward and Hoffmann on orbital symmetry, Feynman on quantum electrodynamics, Smith on the search for structure, and Einstein's collected papers." (see their homepage at Stanford)

Some extracts from the forthcoming fourth volume have been put on the web for evaluation, along with the following request by Professor Knuth himself:
Previews of Volume 4

I've been making some headway on actually writing Volume 4 of The Art of Computer Programming instead of merely preparing to write it, and some first drafts are now ready for beta-testing. I've put them online primarily so that experts in the field can help me check the results, but brave souls who aren't afraid to look at relatively raw copy are welcome to look too. (Yes, the usual rewards apply if you find any mistakes.)

• Pre-Fascicle 2a: Generating all $n$-tuples (version of 10 December 2004)
• Pre-Fascicle 2b: Generating all permutations (version of 10 December 2004)
• Pre-Fascicle 3a: Generating all combinations (version of 19 January 2005)
• Pre-Fascicle 3b: Generating all partitions (version of 10 December 2004)
• Pre-Fascicle 4a: Generating all trees (version of 11 December 2004)
• Pre-Fascicle 4b: History of combinatorial generation (version of 28 December 2004)

Note to Internet friends: I'm extremely grateful that hundreds of you have taken time to read these drafts, and to detect and report errors that you've found. Your comments have improved the material enormously. But I must confess that I'm also disappointed to have had absolutely no feedback so far on several of the exercises on which I worked hardest when I was preparing this material. Could it be that (1) you've said nothing about them because I somehow managed to get the details perfect? Or is it that (2) you shy away from the more difficult stuff, being unable to spend more than a few minutes on any particular topic? Although I do not like to think that readers are lazy, I fear that hypothesis (1) is far less likely than hypothesis (2). I may have to remove material that nobody cares about. But I still cling to a belief that this stuff is extremely instructive. Thus I would like to enter here a plea for some readers to tell me explicitly, Dear Don, I have read exercise N and its answer very carefully, and I believe that it is 100% correct,'' where N is one of the following:
• 7.2.1.1--96 (analysis of a coroutine-based algorithm)
• 7.2.1.1--98 (decoding a recursively generated de Bruijn cycle)
• 7.2.1.2--43 (a Sims table with only short cycles)
• 7.2.1.2--75 (enumeration of northeasterly knight's tours)
• 7.2.1.3--25 (proof of van Zanten's theorem)
• 7.2.1.3--33 (enumeration of genlex listings for index lists)
• 7.2.1.3--42 (analysis of an algorithm for near-perfect combination generation)
• 7.2.1.3--63 (minimal-change algorithm for contingency tables)
• 7.2.1.3--92 (synchronized standard sets in toruses)
• 7.2.1.3--93 (counterexample when hypotheses are violated)
• 7.2.1.3--100 (the heaviest multicomplexes)
• 7.2.1.4--18 (two versions of Yee's one-to-one correspondence)
• 7.2.1.4--19 (Heine's famous identity)
• 7.2.1.4--28 (Lehmer's fabulous formulas, to be checked empirically)
• 7.2.1.4--47 (Nijenhuis and Wilf's algorithm for random partitions)
• 7.2.1.4--49 and 50 (analysis of the smallest parts of a partition)
• 7.2.1.4--55 (basic properties of the majorization lattice)
• 7.2.1.4--56 (my algorithm for partitions in an interval of the majorization lattice)
• 7.2.1.5--27 and 28 (theory of generalized rook polynomials)
• 7.2.1.5--62 (elementary way to locate the largest Stirling numbers via Darroch's theorem)
• 7.2.1.6--19 (proof that Skarbek's algorithm is dual to lexicographic generation)
• 7.2.1.6--25 (my new prune-and-graft method of generating all linked binary trees)
• 7.2.1.6--26, 27, 28 (basic facts about three important lattices of trees)
• 7.2.1.6--33 (representing binary tree links with a single permutation)
• 7.2.1.6--37 (analysis of the Zaks--Richards algorithm for trees by degrees)
• 7.2.1.6--60 (an algorithm to invert the Chung--Feller mapping)
• 7.2.1.6--99 (quick Gray code to list spanning trees of a series-parallel graph)
• 7.2.1.6--105 (counting spanning trees when graphs are built up from smaller ones)
• 7.2.1.6--108 (counting spanning arborescences when digraphs are built up from smaller ones)
• 7.2.1.7--2(b) (the genetic code and the I Ching)
• 7.2.1.7--10 (a coupon-collecting problem relating to dice)
• 7.2.1.7--28 (partitions that are almost noncrossing)
• Note that you don't have to work the exercise first; you're allowed and even encouraged to peek at the answer. Please send success reports to the usual address for bug reports (taocp@cs.stanford.edu), if you have time to provide this extra help. Thanks in advance!

Rules

In order to help Don Knuth, each participant is required to select at least one of the above exercises. She then proceeds to write a short proposal outlining the background, question and answer to be presented. These proposals are reviewed by the staff and may be rejected, accepted or accepted subject to conditions. The process will be visualized on this website by signs attached to the topics meaning available / in review / accepted respectively. During the next semester, we expect the participant to clarify his presentation toward the organisers. This involves getting help where appropriate. Moreover, a detailed solution to the exercise is to be submitted.

Finally, the seminar itself we be held in compact form. During the event, each student presents his topic, the posed question and its answer and proposes a verdict concerning Professor Knuth's version. The other participants then vote whether or not to follow this advice. Opposers will demand clarification from supporters until the audience comes to an unanimous verdict. In this case, randomly selected students will be asked to substantiate their opinion. Thus, by preparation and discussion, everyone should in the end be convinced that the group may give a reasonable statement about the quality of the exercises in question.

Prerequisites

Vordiplom. Active interest in mathematics/theoretical computer science. Willingness to contribute. Command of the English language - the seminar will be held in English because this is the only common denominator language of all participants.