Helping Donald Knuth (WS 2021/2022)

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)

Volume 4, Fascicle 6 has recently been published as preliminary paperback. The book is about Satisfiability and contains many exercises along with their solutions. On his website (under Progess on Volume 4B) Professor Knuth issues the following request:

I worked particularly hard while preparing some of those exercises, attempting to improve on expositions that I found in the literature; and in several noteworthy cases, nobody has yet pointed out any errors. It would be nice to believe that I actually got the details right in my first attempt. But that seems unlikely, because I had hundreds of chances to make mistakes. So I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out carefully as yet.
I still cling to a belief that these details are extremely instructive, and I'm uncomfortable with the prospect of printing a hardcopy edition with so many exercises unvetted. 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 exercises in Volume 4 Fascicle 5:

• MPR-28-29: Prove basic inequalities for sums of independent binary random variables
• MPR-50: Prove that Ross's conditional expectation inequality is sharper than the second moment inequality
• MPR-59: Derive the four functions theorem
• MPR-61: Show that independent binary random variables satisfy the FKG inequality
• MPR-99: Generalize the Karp–Upfal–Wigderson bound on expected loop iterations
• MPR-103-104: Study ternary “coupling from the past”
• MPR-114: Prove Alon's “combinatorial nullstellensatz”
• MPR-121-122: Study the Kullback–Leibler divergence of one random variable from another
• MPR-127: Analyze the XOR of independent sparse binary vectors
• MPR-130-131: Derive paradoxical facts about the Cauchy distribution (which has “heavy tails”)
• 7.2.2-79: Analyze the sounds that are playable on the pipe organ in my home
• 7.2.2.1-29-30: Characterize all search trees that can arise with Algorithm X
• 7.2.2.1-53 (Nikola): Find every 4-clue instance of shidoku (4×4 sudoku)
• 7.2.2.1-55 (Viktor): Determine the fewest clues needed to force highly symmetric sudoku solutions
• 7.2.2.1-103 (Tomáš): List all of the 12-tone rows with the all-interval property, and study their symmetries
• 7.2.2.1-104: Construct infinitely many “perfect” n-tone rows
• 7.2.2.1-115: Find all hypersudoku solutions that are symmetric under transposition or under 90° rotation
• 7.2.2.1-121: Determine which of the 92 Wang tiles in exercise 2.3.4.3–5 can actually be used when tiling the whole plane
• 7.2.2.1-129: Enumerate all the symmetrical solutions to MacMahon's triangle-tiling problem
• 7.2.2.1-147: Construct all of the “bricks” that can be made with MacMahon's 30 six-colored cubes
• 7.2.2.1-151-152: Arrange all of the path dominoes into a single loop
• 7.2.2.1-172: Find the longest snake-in-the-box paths and cycles that can be made by kings, queens, rooks, bishops, or knights on a chessboard
• 7.2.2.1-189: Determine the asymptotic behavior of the Gould numbers
• 7.2.2.1-196: Analyze the running time of Algorithm X on bounded permutation problems
• 7.2.2.1-215: Show that exclusion of noncanonical bipairs can yield a dramatic speedup
• 7.2.2.1-262: Study the ZDDs for domino and diamond tilings that tend to have large “frozen” regions
• 7.2.2.1-305-306: Find optimum arrangements of the windmill dominoes
• 7.2.2.1-309 (Philipp): Find all ways to make a convex shape from the twelve hexiamonds
• 7.2.2.1-320: Find all ways to make a convex shape from the fourteen tetraboloes
• 7.2.2.1-323: Find all ways to make a skewed rectangle from the ten tetraskews
• 7.2.2.1-327: Analyze the Somap graphs
• 7.2.2.1-334: Build fake solutions for Soma-cube shapes
• 7.2.2.1-337: Design a puzzle that makes several kinds of “dice” from the same bent tricubes
• 7.2.2.1-346: Pack space optimally with small tripods
• 7.2.2.1-375: Determine the smallest incomparable dissections of rectangles into rectangles
• 7.2.2.1-387: Classify the types of symmetry that a polycube might have
• 7.2.2.1-394 (Erhard): Prove that every futoshiki puzzle needs at least six clues
• 7.2.2.1-415: Make an exhaustive study of homogenous 5×5 slitherlink
• 7.2.2.1-424 (Andreas): Make an exhaustive study of 6×6 masyu
• 7.2.2.1-432: Find the most interesting 3×3 kakuro puzzles
• 7.2.2.1-442: Enumerate all hitori covers of small grids

I still cling to a belief that these details are extremely instructive, and I'm uncomfortable with the prospect of printing a hardcopy edition with so many exercises unvetted. 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 exercises in Volume 4 Fascicle 6:

• 6: Establish a (previously unpublished) lower bound on van der Waerden numbers W(3,k)
• 57: Find a 6-gate way to match a certain 20-variable Boolean function at 32 given points
• 165: Devise an algorithm to compute the largest positive autarky of given clauses
• 177 (Felix): Enumerate independent sets of flower snark edges
• 212: Prove that partial latin square construction is NP-complete
• 282: Find a linear certificate of unsatisfiability for the flower snark clauses
• 306-308: Study the reluctant doubling strategy of Luby, Sinclair, and Zuckerman
• 318: Find the best possible Local Lemma for d-regular dependency graphs with equal weights
• 322: Show that random-walk methods cannot always find solutions of locally feasible problems using independent random variables
• 335: Express the Möbius series of a cocomparability graph as a determinant
• 339: Relate generating functions for traces to generating functions for pyramids
• 347: Find the best possible Local Lemma for a given chordal graph with arbitrary weights
• 356: Prove the Clique Local Lemma
• 363: Study the stable partial assignments of a satisfiability problem
• 386: Prove that certain CDCL solvers will efficiently refute any clauses that have a short certificate of unsatisfiability
• 428 (Daniel): Show that Boolean functions don't always have forcing representations of polynomial size
• 442-444: Study the UC and PC hierarchy of progressively harder sets of clauses
• 518: Reduce 3SAT to testing the permanent of a {-1,0,1,2} matrix for zero

Please don't be alarmed by the highly technical nature of these examples; more than 100 of the other exercises are completely non-scary, indeed quite elementary. But of course I do want to go into high-level details also, for the benefit of advanced readers; and those darker corners of my books are naturally the most difficult to get right. Hence this plea for help.
Remember that you don't have to work the exercise first. You're allowed to peek at the answer; in fact, you're even encouraged to do so. 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!

Material

• Kickoff-Folien

TAOCP Volume 4, Fascicle 6 can be found in the computer science library. An earlier draft can be found in the archive of Knuth's website.

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

Good grade in the Data Structures and Algorithms lecture. Active interest in mathematics/theoretical computer science. Willingness to contribute. Command of the English language.