# 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 Science### Time and Place

09.02. and 10.02.2009, seminar room I1### Important 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--105 (characterization of graphical degree sequences)
- 7--131 (the maximum number of maximal cliques)
- 7--137 and 138 (generalized toruses)
- 7.1.1--83 (an online algorithm for optimum -- --server locations)
- 7.1.1--116 (functions with conjectured maximum number of prime implicants)
- 7.1.1--122 (simple examples of regular functions that aren't threshold functions)
- 7.1.1--132 (properties of ``bent functions'')
- 7.1.2--16 (minimum-memory computation of 7-variable functions
- 7.1.2--36 and 37 (efficient prefix computation with small depth)
- 7.1.2--43 (efficient finite state transduction with small depth)
- 7.1.2--63 (upper bound for functions with lots of don't-cares)
- 7.1.2--67 (design of a tic-tac-toe chip)
- 7.1.2--68 (analysis of a functional decomposition algorithm
- 7.1.2--76 (Uhlig's cloning algorithm, computes twice as fast as expected
- 7.1.2--85 and 86 (introduction to Razborov's monotone lower bounds
- 7.1.3--10 and 12 (multiplication and division in Conway's field
- 7.1.3--14 and 16 (branching functions and animating functions
- 7.1.3--19 (Paley's amazing rearrangement -- --inequalities
- 7.1.3--58 (characterization of Omega-routable permutations
- 7.1.3--75 (improvement of Ofman's mapping netword
- 7.1.3--83 (shifting a scattered accumulator to the right
- 7.1.3--91 (alpha channels without multiplication
- 7.1.3--110 (powers of two in O(lg lg n) bitwise steps
- 7.1.3--124 (lower bounds on a basic RAM
- 7.1.3--158 and 159 (Fibonacci and negaFibonacci codeword manipulation
- 7.1.3--173 (cleaning up thresholded raster images
- 7.1.3--179 (online algorithm for components of a bitmap
- 7.1.3--186 (fast three-register algorithm for quadratic B\'ezier splines
- 7.1.4--44 (the symmetric functions with largest BDD
- 7.1.4--107 (testing whether a BDD defines a 2SAT instance
- 7.1.4--110 (explicit functions of $n$ variables whose BDD is largest
- 7.1.4--124 (computing the BDD size for the hidden weighted bit function, given any permutation of the variables
- 7.1.4--191 (counting all ZDDs that have no 0-sink
- 7.1.4--216 (covering a chessboard with red, white, and blue dominoes
- 7.1.4--226 (a new way to generate all simple cycles of a graph
- 7.1.4--259 (generating all set partitions with ZDDs
- 7.2.1.1--97 (analysis of a coroutine-based algorithm
- 7.2.1.1--99 (decoding a recursively generated de Bruijn cycle
- 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--100 (the heaviest multicomplexes
- 7.2.1.4--18 (two versions of Zeilberger's one-to-one correspondence for joint partitions
- 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.5--28 and 29 (theory of generalized rook polynomials
- 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 (basic facts about three important lattices of trees
- 7.2.1.6--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
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.

### Prerequisites

Vordiplom. Active interest in mathematics/theoretical computer science. Willingness to contribute. Command of the English language.### Vorlagen

Einige mit*LaTeX-Beamer*erzeugte Beispielfolien finden sich hier. Zum Kompilieren benötigt man diese Quellen. Lesenswert ist zudem die Anleitung für das Beamerpaket. Im wesentlichen für Linux: Einige Hinweise und Quelldateien zum Schreiben einer

*LaTeX*-Arbeit gibt es hier. Neben den wichtigsten Textelementen werden auch der Formelsatz sowie das Erzeugen und Einbinden von

*Metapost*-Abbildungen behandelt. Außerdem liegt ein einfaches, aber praktisches

*Makefile*bei.