Ashutosh Mehra’s Blog

Home
About

Fun with ZDDs: Notes from Knuth’s 14th Annual Christmas Tree Lecture

December 14th, 2008 | Categories: TAOCP

Pages: 1 2 3

In this entry, I’ll attempt to record the important ideas Knuth presented in his 14^th Annual Christmas Tree Lecture, part of his regular Computer Musings.

While I wasn’t fortunate enough to attend the lecture in person, I did go through the recording that, thankfully, was quite well done. Like all other “musings”, this one included some fascinating anecdotal bits (no pun intended) and Knuth’s good sense of humor was sprinkled throughout; but most noticeable was his infectious enthusiasm for the topics he spoke about. The preface to Volume 4 (printed in Fascicle 0) begins with:

The title of Volume 4 is Combinatorial Algorithms, and when I proposed it, I was strongly inclined to add a subtitle: The Kind of Programming I Like Best.

His excitement for these topics clearly showed in the lecture. It is a must-watch for anyone interested in The Art of Computer Programming (especially Volume 4 on Combinatorial Algorithms), or interested in learning a very useful data structure for combinatorial applications — ZDDs.

ZDDs (Zero-suppressed Binary Decision Diagrams) were introduced by Shin-Ichi Minato in 1993, about 7 years after Randal Bryant introduced his key ideas of the BDD data structure; one of which was that keeping the BDD both reduced and ordered is important in practice. In his “Fun with BDDs” musing (this June), Knuth mentioned that this 1986 paper of Bryant’s took computer science almost by storm; remaining the most-cited paper in the field for many years (see here).

Minato’s idea (of zero-suppression in BDDs) was motivated by his observation that when working with combinatorial objects, very often tests in BDDs have to be made just to ensure a potentially large number of variables are FALSE. So, in ZDDs, we just “skip over” any node whose HI pointer leads to $\bot$ (the FALSE sink) — if having $x_j$ TRUE results in the subfunction rooted at $x_j$ to become FALSE, then we skip testing $x_j$ altogether. That’s the basic difference between BDDs and ZDDs. And while ZDD theory is much like the BDD theory, it differs sufficiently in the sense of requiring a different “mind-set”.

The pre-fascicle 1B that discusses BDDs and ZDDs is available from Knuth’s News page (direct link). Interested readers can download it (but Knuth cautions against printing it out just yet, since he’ll be putting up an updated version in a couple of weeks). That pre-fascicle is a 140-odd page booklet with more than 260 exciting exercises! It will be published as part of fascicle 1 (Knuth said it’ll go to printing around the end of January 2009); fascicle 1 would in turn form part of Volume 4A (along with the already published fascicles 0, 2, 3 and 4).

Update (May 2009): Volume 4, Fascicle 1, is here!

The Fascicle 1 of Volume 4 of The Art of Computer Programming is now in print. In addition to the material on BDD and ZDD techniques (described in this post), it includes a subsection on bitwise tricks and techniques, including broadword computing (formerly known as “Platologic computing”). In Knuth’s own words, it is “cram-packed with lots of new stuff among nearly 500 exercises and answers to exercises.”

There’s also a bundle of Volume 4, Fascicles 0-4 available at a discounted price.

Get your copies today!

Families of subsets and their ZDD representation

BDD is a data structure for (representing, manipulating, working with) boolean functions. ZDD, on the other hand, is a data-structure for what Knuth calls Families of Sets — a large number of combinatorial problems are based on studying families of sets (which are just Hypergraphs). Families of sets are another way of looking at boolean functions since there’s a natural one-to-one correspondence between the two — the solutions of a boolean function (the set of n-tuples of boolean values $x=(x_1,\ldots,x_n)$ such that $f(x)$ is TRUE) correspond to family of subsets, with each solution corresponding to a subset where $j$ belong to the subset iff $x_j=1$ [see TAOCP Exercise 7.1.4 -- 203(b)]. But even though the families of sets can be encoded as boolean functions, it is sometimes better to think of them directly as families of sets, rather than in boolean sense. This is the thinking cap we’ll put on when working with ZDDs.

Families of subsets are taken from a well-ordered universe $U$ . We use the following rules to represent those using ZDDs [again, see TAOCP Exercise 7.1.4 -- 203]:

The Empty Family, $\phi$ , is represented by $\bot$ (the FALSE sink node).
The Unit Family (the set comprising just the empty set), $\{\phi\} = \epsilon$ , is represented by $\top$ (the TRUE sink node).
If $f$ is any other family (besides empty and unit), we know that it is nonempty, and that at least one of its members is in turn nonempty. In that case, let $v$ be the least element of universe $U$ that $f$ supports — that $v$ appears in at least one set in $f$ . [see answer to TAOCP Exercise 7.1.4 -- 197 for the definition of supports]. Then define sub-families $f_0$ and $f_1$ of $f$ with $f_0=\{\alpha | \alpha\in f\ \mbox{and}\ v\notin\alpha\}$ and $f_1=\{\alpha | \alpha\cup\{v\}\in f\ \mbox{and}\ v\notin\alpha\}$ . These sub-families correspond to those sets that don’t and do contain $v$ . Then, inside the computer, the family $f$ corresponds to a zead (ZDD-node) labeled $v$ with LO and HI branches going to the ZDD representations of $f_0$ and $f_1$ respectively. Notice the recursive definition (see Knuth’s diagram below).

Defining a ZDD recursively (@19m)

Ex. 1: ZDD of a function (@24m)

Throughout the talk, Knuth took up various problems, and worked them out in real-time for everyone to follow, rather than putting up a bunch of slides with everything already worked out. This is one of the beauties of his musing lectures — it’s interactive. While Knuth works his way through the problems, the audience can work with him or with their own pencil and paper. And it’s even more convenient when watching the recorded session over net, where one can pause, work the problem out, and then play to see if they got it right, and go back etc.). Knuth also joked about how he sometimes had to sit through presentations where the speaker doing PowerPoint would whiz through the slides a bit too fast. So, anyway, the most instructive (and most enjoyable) way to understand these examples, I think, would be to just watch the video and work them out yourself (possibly after going through the relevant material in the pre-fascicle).

Pages: 1 2 3

Solving Project Euler Problems 161 (Trominoes Tiling) and 185 (Number Mind) with ZDDs Analytically evaluating a limiting probability (June 2007 Ponder This)