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 ScienceTime and Place
TBA
Deadlines
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) (If you have trouble downloading these files, your browser is probably screwing up; please see my FAQ page for a workaround.)
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.4--19 (Heine's famous identity)
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.