Seminar in the winter term 2008
Helping Donald Knuth
Contact:
| Joachim Kneis (kneis@informatik.rwth-aachen.de) |
| Alexander Langer (langer@informatik.rwth-aachen.de) |
| Stefan Richter (richter@informatik.rwth-aachen.de) |
| Peter Rossmanith (rossmani@informatik.rwth-aachen.de) |
Classification
Theoretical Computer ScienceTime and Place
09.02. and 10.02.2009, seminar room I1Important Dates
- 31.10.2008: Exercise accepted (requires abstract)
- 12.01.2009: Final version and slides
- 09./10.02.2009: Talks, 30 min/talk
- 09.03.2009: Final version (including comments from audience) to be sent to Knuth
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 spend most of my time these days grinding out new pages for the fascicles of the future. Early drafts are posted here, ready for beta-testing.
I've put these drafts 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 0a: Introduction to Combinatorial Searching (version of 30 Jan 2008)
- Pre-Fascicle 0b: Boolean Basics (version of 30 Jan 2008)
- Pre-Fascicle 0c: Boolean Evaluation (version of 30 Jan 2008)
- Pre-Fascicle 1a: Bitwise Tricks and Techniques (version of 16 Feb 2008)
- Pre-Fascicle 1b: Binary Decision Diagrams (version of 15 Sep 2008)
- 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--97 (properties of graph sums and graph products)
7--131 (the maximum number of maximal cliques)
7.1.3--58 (characterization of Omega-routable permutations
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 will 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.