— Alan J. Perlis [foreword to SICP]

I find long functions names charming — I think they impart a certain personality to the API and add to the *fun* of programming. And while I try to avoid excessively long names in my own code at work (unless they add to clarity), I never fail to get a good kick seeing such names used by other programmers!

I’ve often wondered what the longest names would look like. So I decided to explore a large system — the system DLLs in `C:\Windows` directory — and dig up some of the biggies. My plan was to write a script that walked through the installed DLLs and looked at their exported functions list for interesting candidates.

Here are the longer ones I could find:

`RtlWriteDecodedUcsDataIntoSmartLBlobUcsWritingContext`[wcp.dll], with 53-characters, was the longest one (but this function is not documented)- (52)
`ConvertSecurityDescriptorToStringSecurityDescriptor{A,W}`[advapi32.dll], the function that Raymond Chen admitted was the reason for his post on security descriptors. - (52)
`ConvertStringSecurityDescriptorToSecurityDescriptor{A,W}`[advapi32.dll], the complement of the above. - (50)
`CreatePrivateObjectSecurityWithMultipleInheritance`[advapi32.dll], another security function. - (50)
`CertCreateCTLEntryFromCertificateContextProperties`[crypt32.dll]. - (50)
`EapHostPeerQueryUIBlobFromInteractiveUIInputFields`[eappcfg.dll]. - (49)
`AccessCheckByTypeResultListAndAuditAlarmByHandle{A,W}`[advapi32.dll], yet another security API — I guess the security API programmers get a good kick from long names, just like me! - (47)
`GetNumberOfPhysicalMonitorsFromIDirect3DDevice9`[Dxva2.lib]. - (43)
`SetupRemoveInstallSectionFromDiskSpaceList{A,W}`[Setupapi.dll].

And just so that no one thinks I’m making these up, I’ve linked to their documentation!

Curious on seeing these names, I dug through the other “operating system” I had access to — GNU EMACS. The longest interactive command there is `slime-compiler-notes-default-action-or-show-details/mouse`: Counting punctuations, this beats the longest Windows export by 4 characters.

I used the pefile Python library to parse all DLLs in my `windows` directory. I only considered “system” DLLs (ignoring any third-party drivers etc.) by checking for “Microsoft” in the DLL copyright-string. In addition, I discarded any C++-ish exports, because the C++ name-mangling skewed the results too much and I was too lazy to hook in a “undecoratify” procedure.

Finally, on my 64-bit windows installation, there are both 32-bit and 64-bit versions of many core DLLs (in `System32` and `SysWOW64` directories respectively), and I encountered duplicates. A similar thing happened with SxS DLLs.

Using this Python script I coded, I generated a delimitered text-file with around 1500 entries that I manually scanned (I had some time to waste!) for “interesting” names. Below is a histogram of the function-name lengths. The rough bell shape gives me confidence that script wasn’t totally off the mark.

A second axis to dig “interesting” functions would be to count the *number of function params*.

This one is a bit of fuzzy due to questions like “Do you count *deep*“? In that when a function accepts a pointer to a struct, do you count the struct members as inputs too? For instance, `CreateFontIndirectEx` [gdi32.dll] takes a pointer to `ENUMLOGFONTEXDV` structure that holds about two dozen items (all things considered).

Counting params is also more work, at least for DLL exports (where you need to cross-reference with documentation/headers if the export is, at all, public). Otherwise, the problem can be approached differently by forgetting DLL exports entirely and instead using a crawler that walks the the locally installed MSDN and parses the “Syntax” section to count the number of params — just assuming `num_params = num_commas + 1` might be good enough.

Anyway, manually browsing through some of MSDN, I chanced upon a few gems:

`AccessCheckByTypeResultListAndAuditAlarmByHandle`, our friend from above, true to its character, takes 17 parameters!`OleCreateFromFileEx`takes in a filename, interface ID, flags, sink, connection, site… 13 in all.

Well named functions (just like well named variables) are good instant documentation. *Descriptive* function are important when:

- Such functions all belong to a flat namespace (DLL exports or C code)
- Several of them have very similar purpose (like the six or so
`AccessCheck*`APIs)

Such names become even more relevant when they define the public API of your library/system.

Some people (“constipated by bittersweet philosophy”?) dislike long function names, and I wonder why. The argument that longer functions take longer to type seems mostly dud: Visual Studio with the awesome Visual Assist X addon does Intellisense beautifully; Emacs with `hippie-expand` does some good magic (the brave also have CEDET); Eclipse, BBEdit, and Vim surely have their own thing. So typing isn’t a problem. And with machines so fast and powerful, the (JIT)compilation/linking-time for longer function names should be irrelevant in most cases.

While researching for this entry, I came across the post “Best” method names ever by Brad Abrams that has some interesting content/comments.

*[Note: Lest someone should give a wicked twist to the whole point of this post, I should add that I have most sincere respect for Microsoft engineers, enjoy using their programs every day and working with their APIs.]*

A bunch of `A`, `B`… The *wire identification problem* asks for an efficient procedure to mark the other end of the bunch with the corresponding labels. The wires run underground so you can’t track them individually and any wire is visibly indistinguishable from any other (except for the labeling).

As you might have guessed, the only way to gain information in this setup is to connect some set of wires at one end, walk up to the other end, and test for conductivity — this would give some partial labeling information. The process may have to be repeated many times before a complete labeling can be constructed. And since each such step involves walking across the distance of the wires, we wish to solve the problem *with the least number of trips*.

It should be easy to convince oneself that this problem cannot be solved when `n = 2` — there’s really nothing we can use to break the symmetry of the situation.

For `n = 3`, we can use the following simple procedure (see the illustration on the right):

*Step 1*: Connect the and wires at the labeled end, walk up to the unlabeled end, and test for conductivity. The pair that conducts electricity would be and , although we cannot determine exactly which is or at this point, and the remaining wire is uniquely identified as . For notation, we use lowercase letters for the labelings that we discover, versus uppercase letters for the given labeling.*Step 2*: Connect the newly identified wire with any one of the wires (recall, we don’t know which is or individually, only that one is and the other ). Now walk back to the labeled side and test for conductivity of with the remaining wires. If we find that — is conducting, then the wire we hooked up on the other side was really , otherwise it was .

The case `n = 4` can be solved similarly with just two trip: Hook up — on one side and then run conductivity tests on the other side to partition the wires into two groups — and —; then hook up one from each of the two groups together etc.

So the question is: Can the problem be solved for all `n` with just two trips?

The wire identification problem is one of those puzzles that is deceptively simple in its description, whose small cases are easy enough to solve in the head, and yet a fair amount of math goes into proving the general result.

I first read about this fascinating problem in the Don Knuth’s Selected Papers on Discrete Mathematics book — in a short 5-page paper titled The Knowlton–Graham partition problem (arXiv link).

Knuth states the following idea, attributed to Kenneth Knowlton, to solve the general problem:

Partition into disjoint sets in two ways and , subject to the condition that at most one element appears in -set of cardinality and a -set of cardinality , for each and . We can then use the coordinates to identify each element.

By a theorem of Ronald Graham, a solution involving just two trip always exists for wires unless is 2, 5, or 9 (On partitions of a finite set [PDF]).

Knuth in his paper translates the problem of Knowlton-Graham partitions in terms of 0/1-matrices. Lemma 1 in that paper states: *Knowlton-Graham partitions exist for iff there’s a 0/1-matrix having row sums and column sums such that and are multiples of and *.

Let’s use this lemma to label a set of 6 wires (). Since we can write 6 = 1 + 2 + 3, a rather obvious matrix satisfying the conditions of the lemma is:

Guided by this matrix, here’s our two-trip identification procedure:

- On the labeled side, hook up wires in the following groups: , , and .
- Walk over to the unlabeled side, run the conductivity tests, and make the corresponding groups , , and .
- Still on the unlabeled side, hook up the wires in the groups , , and . Note that we still don’t know exactly which wire is, say, ; but we do know the two wires of which one if and the other .
- Walk over to the labeled side, unhook the connection we had made in the first step, and check for conductivity. The sole wire here, say, would correspond to the the sole wire from the group on the other side. Similarly, the connected-pair of — corresponds to the pair on the other side. etc.

Navin Goyal, Sachin Lodha, and S. Muthukrishnan consider some variants & generalizations of the wire identification problem in their paper The Graham-Knowlton Problem Revisited. In particular, they consider the restrictions to just hooking up pairs in the identification process (in our examples above, we were free to hook, say, 3 wires).

]]>Last week I finished reading Kernighan & Plauger‘s beautiful book The Elements of Programming Style, the classic that pioneered the term *programming style*. I’ve excerpted below some rules of style from that book. I hope these get you excited to reading the book too!

Here’s how the book works: The authors pick up a simple “real-world” program (mostly from other programming texts) and comment critically on its style. For analyzing the style, they look at the expressions and statements (at the lowest level), program and control structures, I/O-handling, program efficiency and documentation. In addition to suggesting what’s wrong with the code, the authors fix it, sometimes rewriting the whole thing, to produce a simpler, cleaner, sometimes more efficient, and always a more obviously correct program.

The experience is that of watching two master programmers doing a code-review!

You may read the text in one run. Or, you may challenge yourself and use it as a “problem-book” by studying the programs and analyzing them for style and fixing them before reading what the masters have to comment.

In all, it is a very pragmatic book — full of useful, practical advice.

A word of caution is due: The program fragments are in Fortran and PL/I. And while they use only the basic features of the language, it is still somewhat of a quest to figure out the meaning of the longer Fortran programs infested with GOTOs and arithmetic-IFs. PL/I is much easier to read.

There’s probably *not much new stuff* you’ll find in this book. Most things the authors say are perhaps ones you already knew, believed, and agreed with (if only subconsciously). And yet it is a delight to read the whole thing if only because it reaffirms those beliefs. This is close to how I felt when reading *The Pragmatic Programmer* — that book hardly had anything *new*, and yet it was a sheer pleasure to read.

Programming is far from being a exact science — perhaps it is an art (or engineering?). As we, programmers, work day after day doing what we do, we build many notions (or guiding principles) about our craft. From reading books to blogging, from studying other people’s code to writing our own to fixing bugs, from discussions with colleagues — the entire software development experience helps us build various concepts of what constitutes good practices of programming. And once in a while, it is reassuring to have all these notions validated by the masters — expert programmers, like Kernighan and Plauger, who we can safely trust to know about the art.

Reading this book will give such a reaffirmation to your own principles of programming. And if (alas!) you had been harboring some truly deviant ideas about programming, reading it would hopefully help set them right.

It’s been more than three decades since the second edition of the book came out in 1978. So it is natural to wonder what, if anything, has changed about how we program and what we consider good programs. To what extent have our programming languages and programming principles advanced through the years? Is this book still relevant?

To be honest, I wasn’t even born until many years after the book came out, so I’m naturally not qualified to comment. But studying how the programs in the text, perhaps typical of their age, were written, I couldn’t help but notice the following.

There has been definite improvement in the following respects:

*Structured programming*and*structured control statements*(like`if/then/else`,`for`,`while`,`break`,`continue`,`yield`) have made some of the points (mainly about`goto`, but also some others) in this book less relevant.- Support for
*recursion*appears to be univerally available in all “modern” languages I can think of. (To contrast, the original Fortran didn’t allow recursion.) - Python/Haskell-style
*layout*has solved many problems related to block-indentation. *Functional languages*like Haskell have made certain class of problems, like forgetting initialization, close to impossible. (And while functional languages definitely existed many decades ago, I think they are much more widely known — I may be wrong in this.)*Profilers and other instrumentation tools*for measuring timing performance and “hotspots” are available in plenty, though perhaps not used enough.*Module/Package/Namespace systems*are available in many mainstream languages.

But we still have to routinely solve the same old problems and we still make the same old mistakes when solving them: What is the best way to design/structure correct and reliable programs? How to best validate input? How to correctly program with floating point numbers? … The book would perhaps provide some guidance with respect to these questions.

I’ve tried to collect some of the timeless wisdom of Kernighan and Plauger’s words as quotations in the remainder of the post.

Each chapter in their book is sprinkled with several terse lines summarizing the essence of the discussion. I’ve also collected some of those towards the end. If you enjoy and appreciate these, *you would definitely want to read the whole book*. As far as programming books go, this is quite thin (the size of K&R), so you have a good chance of actually finishing it!

The introductory chapter gives an example of how a Fortran program used the expression `(I/J)*(J/I)` to initialize `V(I,J)` to an identity matrix! Notice that with integer arithmetic, assume `i` and `j` are nonzero, `(I/J)*(J/I)` is same as `I == J ? 1 : 0`.

The author’s point out why such code is wrong:

The problem with obscure code is that debugging and modification become much more difficult, and these are already the hardest aspects of computer programming. Besides, there is the added danger that a too-clever program may not say what you thought it said.

(Page 2)

The first chapter ends with an advice on healthy skepticism:

Nevertheless, mistakes can occur. We encourage you to view with suspicion anything we say that looks peculiar. Test it, try it out. Don’t treat computer output as gospel. If you learn to be wary of everyone else’s programs, you will be better able to check your own.

(Page 7)

This is reminiscent of Feynman’s words *“You should, in science, believe logic and arguments, carefully drawn, and not authorities. … I am not sure how I did it, but I goofed. And you goofed, too, for believing me.”* (Page x, *Feynman Lectures in Physics; Vol I*).

The chapter on expressions has the famous words on *clever programming* that are often quoted:

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it?

(Page 10)

Simplicity and clarity trump stray microseconds:

Simplicity and clarity are often of more value than the microseconds possibly saved by clever coding… Trivia rarely affect efficiency. Are all the machinations worth it, when their primary effect is to make the code less readable?

(Page 127)

Here’s some advice on the demerits of arbitrary temporary variables:

The fewer temporary variables in a program, the less chance there is that one will not be properly initialized, or that one will be altered unexpectedly before it is used. “Temporary” is a dirty word in programming — it suggests that a variable can be used with less thought than a “normal” (permanent?) one, and it encourages the use of one variable for several unrelated calculations. Both are dangerous practices.

(Page 11)

The authors present a peculiar test, to which *Elevator Test* bears some resemblance, to assess code readability:

A useful way to decide if some piece of code is clear or not is the “telephone test.” If someone could understand your code when read aloud over the telephone, it’s clear enough. If not, then it needs rewriting. Use the “telephone test” for readability.

(Page 21)

The text of the program should be close to the process it evokes:

It is a good rule of thumb that a program should read from top to bottom in the order that it will be executed; if this is not true, watch out for the bugs that often accompany poor structure.

(Page 37)

Write short functions/classes with well defined purpose:

When a program is not broken up into small enough pieces, the larger modules often fail to deliver on these promises. They try to do too much, or too many different things, and hence are difficult to maintain and are too specialized for general use.

(Page 59)… Combining too many functions in one module is a sure way to limit its usefulness, while at the same time making it more complex and harder to maintain.(Page 64)

“Optimizing” too early in the life of a program can kill its chances for growth.

(Page 61)

It must be possible to describe the function performed by a module in the briefest of terms and it is necessary to minimize whatever relationships exist with other modules, and display those that remain as explicitly as possible. This is how we obtain the minimum “coupling”, and hence maximum independence, between modules.

(Page 62)

As we have said several times, the hard part of programming is controlling complexity — keeping the pieces decoupled so they can be dealt with separately instead of all at once. And the need to separate into pieces is not some academically interesting point, but a practical necessity, to keep things from interacting with each other in unexpected ways.

(Page 95)

One good test of the worth of a module, in fact, is how good a job it does of hiding some aspect of the problem from the rest of the code.

(Page 65)

… break the job into five small functions, each one of which can be assimilated separately, then treated as a black box that does some part of the job. Once it works, we need no longer concern ourselves with how it does something, only with the fact that it does. We thus have some assurance that we can deal with the program a small section at a time without much concern for the rest of the code. There is no other way to retain control of a large program.

(Page 77)

One of the better ways of [planning program structure] is what is often called “top-down design.” In a top-down design, we start with a very general pseudo-code statement of the program … and then elaborate this statement in stages, filling in details until we ultimately reach executable code. Not only does this help to keep the structure fairly well organized, and avoid getting bogged down in coding too early, but it also means that we can back up and alter bad decisions without losing too much investment.

(Page 71)

Learning to think recursively takes some effort, but it is repaid with smaller and simpler programs. Not every problem benefits from a recursive approach, but those that deal with data that is recursively defined often lead to very complicated programs unless the code is also recursive.

(Page 77)

Input/output is the interface between a program and its environment. Two rules govern all I/O programming:

NEVER TRUST ANY DATA, andREMEMBER THE USER. This requires that a program be as foolproof as is reasonably possible, so that it behaves intelligently even when used incorrectly, and that it be easy to use correctly. Ask yourself: Will it defend itself against the stupidity and ignorance of its users (including myself)? Would I want to have to use it myself?(Page 97)

Some compilers allow a check during execution that subscripts do not exceed array dimensions. This is a help … many programmers do not use such compilers because “They’re not efficient.” (Presumably this means that it is vital to get the wrong answers quickly.)

(Page 85)

Where there are two bugs, there is likely to be a third.

(Page 102)

Floating point arithmetic adds a new spectrum of errors, all based on the fact that the machine can represent numbers only to a finite precision.

(Page 115)

As a wise programmer once said, “Floating point numbers are like sandpiles: every time you move one, you lose a little sand and you pick up a little dirt.” And after a few computations, things can get pretty dirty.

(Page 117)

Concerns of efficiency must strike a balance with those of overall cost.

Machines have become increasingly cheap compared to people; any discussion of computer efficiency that fails to take this into account is shortsighted. “Efficiency” involves the reduction of overall cost — not just machine time over the life of the program, but also time spent by the programmer and by the users of the program.

A clean design is more easily modified as requirements change or as more is learned about what parts of the code consume significant amounts of execution time. A “clever” design that fails to work or to run fast enough can often be salvaged only at great cost. Efficiency does not have to be sacrificed in the interest of writing readable code — rather, writing readable code is often the only way to ensure efficient programs that are also easy to maintain and modify.

To begin, let us state the obvious. If a program doesn’t work, it doesn’t matter how fast it runs.

(Page 123)

How can we really speed it up? Fundamental improvements in performance are most often made by algorithm changes, not by tuning … There are two lessons. First, time spent selecting a good algorithm is certain to pay larger dividends than time spent polishing an implementation of a poor method. Second, for any given algorithm, polishing is not likely to significantly improve a fundamentally sound, clean implementation. It may even make things worse.

(Page 133–134)

Profile and measure your code before making performance improvements.

Beware of preconceptions about where a program spends its time. This avoids the error of looking in the wrong place for improvements. Of course, you have to have some working idea of which part of a program has the most effect on overall speed, but changes designed to improve efficiency should be based on solid measurement, not intuition.

A useful and cheap way to measure how a program spends its time is to count how many times each statement is executed. The resulting set of counts is called the program’s “profile” (a term first used by D. E. Knuth in an article in Software Practice and Experience, April, 1971). Some enlightened computer centers make available a “profiler” …

(Page 136)

The sole truth about a program is its text.

The only reliable documentation of a computer program is the code itself. The reason is simple — whenever there are multiple representations of a program, the chance for discrepancy exists. If the code is in error, artistic flowcharts and detailed comments are to no avail. Only by reading the code can the programmer know for sure what the program does.

(Page 141)

In a project of any size it is vital to maintain readable descriptions of what each program is supposed to do, how it is used, how it interacts with other parts of the system, and on what principles it is based. These form useful guides to the code. What is not useful is a narrative description of what a given routine actually does on a line-by-line basis. Anything that contributes no new information, but merely echoes the code, is superfluous.

(Page 141)

The book ends with the following paragraph on following the rules of programming style:

To paraphrase an observation in

The Elements of Style, rules of programming style, like those of English, are sometimes broken, even by the best writers. When a rule is broken, however, you will usually find in the program some compensating merit, attained at the cost of the violation. Unless you are certain of doing as well, you will probably do best to follow the rules.(Page 159)

You would surely have heard of programming maxims like “make it right before you make it faster” or “don’t comment bad code — rewrite it”. Well, this book is generously sprinkled with such short witty one-lines capturing the essence of the section. Below are some of those words of wisdom.

- From the Introduction: Write clearly – don’t be too clever.
- On Expressions: Say what you mean, simply and directly. Use library functions. Avoid temporary variables. Trying to outsmart a compiler defeats much of the purpose of using one. Write clearly – don’t sacrifice clarity for “efficiency”. Let the machine do the dirty work. Replace repetitive expressions by calls to a common function. Parenthesize to avoid ambiguity. Choose variable names that won’t be confused. Use the good features of a language; avoid the bad ones.
- On Control Structures: Use
`DO-END`and indenting to delimit groups of statements. Use`IF-ELSE`to emphasize that only one of two actions is to be performed. Use`DO`and`DO-WHILE`to emphasize the presence of loops. Make your programs read from top to bottom. Use`IF ... ELSE IF ... ELSE IF ... ELSE ...`to implement multi-way branches. Use the fundamental control flow constructs. Write first in an easy-to-understand pseudo-language; then translate into whatever language you have to use. Avoid`THEN-IF`and null-`ELSE`. Avoid`ELSE GOTO`and`ELSE RETURN`. Follow each decision as closely as possible with its associated action. Use data arrays to avoid repetitive control sequences. Choose a data representation that makes the program simple. Don’t stop with your first draft. - On Program Structures: Modularize. Use subroutines. Make the coupling between modules visible. Each module should do one thing well. Make sure every module hides something. Let the data structure the program. Don’t patch bad code – rewrite it. Write and test a big program in small pieces. Use recursive procedures for recursively-defined data structures.
- On Input/Output: Test input for validity and plausibility. Make sure input cannot violate the limits of the program. Terminate input by end-of-file or marker, not by count. Identify bad input; recover if possible. Treat end-of-file conditions in a uniform manner. Make input easy to prepare and output self-explanatory. Use uniform input formats. Make input easy to proofread. Use free-form input when possible. Use self-identifying input. Allow defaults. Echo both on output. Localize input and output in subroutines.
- On Common Blunders: Make sure all variables are initialized before use. Don’t stop at one bug. Use debugging compilers. Watch out for off-by-one errors. Take care to branch the right way on equality. Avoid multiple exits from loops. Make sure your code “does nothing” gracefully. Test programs at their boundary values. Program defensively. 10.0 times 0.1 is hardly ever 1.0. Don’t compare floating point numbers just for equality.
- On Efficiency and Instrumentation: Make it right before you make it faster. Keep it right when you make it faster. Make it clear before you make it faster. Don’t sacrifice clarity for small gains in “efficiency.”Let your compiler do the simple optimizations. Don’t strain to re-use code; reorganize instead. Make sure special cases are truly special. Keep it simple to make it faster. Don’t diddle code to make it faster — find a better algorithm. Instrument your programs. Measure before making “efficiency” changes.
- On Documentation: Make sure comments and code agree. Don’t just echo the code with comments — make every comment count. Don’t comment bad code — rewrite it. Use variable names that mean something. Format a program to help the reader understand it. Indent to show the logical structure of a program. Document your data layouts. Don’t over-comment.

For the past several days, I’ve been working my way through Prof. N.G. de Bruijn’s book Asymptotic Methods in Analysis; and I want to share some of the fun I’ve had reading it.

This post is not a review or anything (here’s an image of the back cover with some reviews). Below are just fragments of what I’ve read so far and found fascinating. You could also consider this my attempt at trying to persuade you to get a copy of this beautiful little book! Sadly, new copies appear *not* to be available at most online bookstores, so it might be hard to get one.

This book is by the same Prof. de Bruijn well-known, among other things, for his cycles, which are defined as following: An -ary *de Bruijn cycle* is a sequence of radix- digits such that every combinations of digits occurs consecutively in the cycle. For example, one possible binary de Bruijn cycle of length is:

Treating this sequence as a cycle, notice that each of the 16 possible 4-bit patterns (`0000` … `1111`) appear exactly once in it. Knuth describes at least *three* interesting algorithms for generating such cycles in TAOCP Section 7.2.1.1 (printed in Volume 4, Fascicle 2 and downloadable as pre-fascicle 2a).

There’s surely lots to say about Prof. de Bruijn’s work (including his cycles), but I’ll reserve them for future posts. Take a look, for example, at the index of TAOCP Vol I (perhaps also in other volumes) and you’ll see references to many of his results, sometimes framed as exercises. And if you enjoy asymptotic calculations and analyses of algorithms, you would find it interesting to read his co-authored paper (with Knuth and Rice) where it is shown that *the average height of planted plane trees* is:

This is also TAOCP Ex. 2.3.1–11, where the question is posed in terms of the average value of the maximum stack size consumed while running the usual in-order binary tree traversal, assuming all binary trees with n nodes are equally probable.

As an interesting note, Knuth in his musings on *The Joy of Asymptotics* (30 May 2000) said:

I’ve dedicated this book [Selected Papers on Analysis of Algorithms] to Prof. de Bruijn … in the Netherlands because he has been my

guru… Ever since I got my PhD, I considered him my post-graduate doctoral advisor. Every time I had a problem that I got stuck on, I would write to him, and he would write me back a letter that would help me get unstuck. And that’s been going on for over fourty years now. So I dedicated this book to him. And what I want to talk to you about today is one of the thingshehas spent most ofhislife on — asymptotic methods.

By the way, that paper deriving the cool formula for the height of trees is included in these *Selected Papers* (Ch. 15).

I had got myself a copy of this book several years ago after first reading about it in the section on asymptotic calculations in TAOCP (Sec 1.2.11.3). But unfortunately, the book suffered the same fate as countless others — it just kept resting on my bookshelf. But a few days ago, I decided to give it a try.

*A brief history*. As described in its preface, this book grew out of lectures given in 1954–55 and was first published in 1958. The Dover edition I have is a reprint of the third edition from 1970.

Most computer programmers are familiar with the Big-O notation, or the Bachmann-Landau notation, for analyzing space/time-complexity of an algorithm. Among other things, this book talks of the tricks involved in getting precise asymptotic bounds once we have reduced the problem at hand to, say, a sum or an integral.

This is a *pragmatic* book — its focus is on demonstrating general techniques by working out several examples in detail (sometimes in more than one way) rather than expounding highly generalized theories of analysis. In this context, I found these lines from the preface reassuring:

Usually in mathematics one has to choose between saying more and more about less and less on the one hand, and saying less and less about more and more on the other. In a practical subject like this, however, the proper attitude should be to say as much as possible in a given situation.

From my reading, at certain places it, of necessity, assumes a basic knowledge of analysis and complex variable theory. Other than that, it is a fairly elementary treatment. (Note: as Feynman made a quip in one of his lectures, *“Elementary” means that very little is required to know ahead of time in order to understand it, except to have an infinite amount of intelligence.”*)

It’s a small book (200 pages) with very few exercises and so can be read in about two weeks, if you read an hour a day. And since there are lots of cliff-hanging moments (well, to the extent a book on analysis can have!) and the reader is left wondering how a tricky sum/integral would be tamed, your might be compelled to finish it even sooner!

de Bruijn has a good sense of humor too. At the start of the first chapter, when trying to answer the question *“What is Asymptotics?”*, he says:

The safest and not the vaguest definition is the following one: Asymptotics is that part of analysis which considers problems of the type dealt with in this book.

Didn’t see that one coming!

And while the book is tiny, it covers lots of tricks & techniques. So, to give my interested readers a taste, I’ve picked a couple of my favorite from the first chapter. All examples are de Bruijn’s.

*Uniformity of estimates* is this little thing that keeps popping up every so often when analyzing the asymptotics of some characteristic of an algorithm. But it is rarely explained what it means or why uniformity is crucial to the application at hand. Grown up boys and girls are supposed to know what uniformity is, I suppose.

Before looking at uniformity, let’s recap the definition of the -notation. We say:

to mean the existence of numbers and such that:

The thing to note in this definition is that

Returning to the question of uniformity, suppose is a positive integer and and are arbitrary functions. Then:

Rewriting the last line as: , we see that

On the other hand, in the asymptotic relation (with again being a positive integer):

the implicit constant in the -notation is independent of k, since we have

Hence if we write , with , we can choose to be 1. In such a case — when the hidden constants in the -notation do not depend on the parameter — the estimate is called *uniform*. This requirement is much like that of uniform convergence or uniform continuity in analysis.

So why trouble oneself with uniformity? Here’s one case where uniform estimates prove helpful: In “balancing” the asymptotic terms of a sum evenly to achieve a tight bound.

For instance, if we have somehow shown that with and where is a parameter. If the formula holds uniformly, we can get a tight bound by reasoning as follows: When is small, the first part, , is small, but the second part, , is large; the reverse holds if is large. Hence we wish to find a “balance” that minimizes the sum of the terms. And this happens when both the terms are asymptotically equivalent. So to achieve such a balance, we simply equate the two expressions , giving , and we finally get .

Notice that because of uniformity, the four hidden constants (, , , ) of the two do not vary when we vary the parameter . If the two original estimates had not been uniform; that is, had their hidden constants (implied by the -notation) varied with , we wouldn’t have been able to apply this simplistic “balancing” idea. For instance, while for small , the term might have been small, the hidden constant in might have grown, leading to unpredictable overall behavior.

The good thing about uniform estimates is that they are sometimes more useful; but proving uniformity might require a more careful analysis.

An *asymptotic series* or *asymptotic expansion* for a function is a formula like:

where, as ,

That is, the asymptotic expansion for is a series of functions such that if we truncate the series at the

A large class of examples of asymptotic expansions are convergent power series, like:

But there could be asymptotic expansions that are not convergent power series. And with such asymptotic expansions, some curious things can happen:

- The series of the asymptotic expansion need not be convergent.
- If the series does converge, its sum need not be equal to
- It is even possible to have and ‘s such that the sum of the series does not have the series as its own asymptotic expansion!

The essential reason for these seemingly strange facts, as de Bruijn explains, is:

… that convergence means something for some fixed whereas the -formulas are not concerned with , but with . Convergence of the series, for all , say, means that for every individual there is a statement about the case . On the other hand, the statement that the series is the asymptotic expansion of means that for every individual there is a statement about the case .

For example, when , the asymptotic expansion of is:

but the series converges for no value of .

The book covers lots of useful stuff. In particular, It talks about Lagrange’s inversion formula (using which we can solve for the “tree function”), it has a especially thorough treatment of the saddle-point method. And much much more.

]]>Some days ago I migrated to the emacs 23 pretest (

First, the good news: My zillions of customizations, installed packages and hooks all worked without a glitch and my most frequently used modes have been working great — `c++`, `emacs-lisp`, `haskell` (with `ghci` interaction), `dired`, `eshell` and the dear old `text`. Also there have been no crashes or freezes or (I shudder!) data corruptions. The pretest looks rock-solid. The only major thing that didn’t work for me was `w3m` (it asked me to try the development version; that might likely have worked).

So, what’s new?

Now `next-line`/`previous-line` go to the next/previous *visual* line as opposed to the *logical* line. In the words of StackOverflow poster Chris R, emacs navigation now acts like notepad.

While it’s just a change of defaults and one could revert to the earlier behavior by setting `line-move-visual` to `nil`, I still think, this is, by far, the biggest change in behavior of emacs 23. And I can safely bet that it would break many keyboard macros. In less than a week of use, this behavior bit me twice while calling some keyboard macros. Note that our friends `C-a` and `C-e` (`move-beginning-of-line` and `move-end-of-line`) still act on logical lines.

With this new default, the usual technique of jumping to the next/previous visual line (of a long logical line) via a quick isearch is no longer needed. But more keystrokes have to be pressed to go next/previous logical line.

There seems to have been a fair bit of discussion around the behavior of `C-n` and `C-p`.

With the `--daemon` command-line argument, emacs starts running in background (with no visible terminal session or frame). New terminal sessions or frames can be created using `emacsclient`: specify `-c` to **c**reate frames or `-t` for **t**erminal sessions; and optionally `-n` if you don’t wish `emacsclient` to wait for the editing to finish. And if you’re feeling all hackerish, there’s even a `-e` option to supply an expression to be eval’ed!

`emacsclient` also worked way back with emacs 21, but only after a `server-start` had been done from a running emacs session. Then `emacsclient` would just create a new buffer in that existing session/frame.

With the new daemon support, distinct sessions/frames can be created, all connected with the same server. One thing I find cool with this setup is that different sessions opened simultaneously share buffers and other state. So if you make some changes (add text, delete paragraphs whatever) in a buffer in one session, you can see those changes get reflected in the view of that buffer in another session *in real time*. Finally, even if all sessions are closed, the buffers remain open.

In emacs 21, `emacsclient` was already instantaneous because it didn’t have to load up a new copy of emacs and do all the startup initialization. Hence it could be safely set as the `$EDITOR` on Mac or Linux (See Jared’s post What is your $EDITOR?). The same is true with emacs 23 running in `--daemon` mode, and now we have the added flexibility to create new sessions/frames.

`--daemon` worked great for me on the Mac but on Windows, emacs refused to launch in the daemon mode, giving the error “This platform does not support the -daemon flag.” I wonder if daemon support for Windows would be included in the final emacs 23.

Emacs sessions created via `emacsclient` have a special indicator `@` in the mode-line and the minor-mode indicator `Server`. `C-x C-c` is now mapped to `save-buffers-kill- terminal` rather than

See `djcb`‘s entries at emacs-fu (a good regular source of emacs tricks) on emacs –daemon and windows and daemons.

Directory-local variables are a great way to associate certain mode-specific variables to every file contained in a particular directory (or in its subdirectories).

As an example, say, you’re working on a `C++` project that has peculiar code indentation requirements (indents are to be real tab character worth 8-space) while your usual indentation style is quite different (always 2-space indents, never tabs). Using directory-local variables, you can emacs pick the project’s indent style for files in the project’s directory and otherwise use your regular style. Something like the following setup would do the trick.

First, as usual, in your `.emacs` define your own personal style, via, say:

Next, define variables like `c-basic-offset`, `tab-width`, `indent-tabs-mode` to match your project’s style and associate them to the root of your source repository. So if your projects root is at “d:/work/BeautifulCode/”, you do this in your `.emacs`:

Now, whenever you open any `C++` file under your project’s root, the project-specific formatting would get applied. You can work this way with many different projects, each having different formatting requirements, without having to write specific customizations via a magic first line at the top of each file like:

/* -*- c-basic-offset: 8; tab-width: 8; indent-tabs-mode: t; -*- */

Using directory-local variables, one could also define scm parameters (server/port, repository root, …) on a per root-directory basis. I think it’s a very powerful feature.

Similar to the above configuration via `dir-locals-set-directory-class` and `dir-locals-set-class-variables`, it is possible to define directory-local variables via a `.dir-locals.el` file (actually, the file defined by the `dir-locals-file` variable).

The idea is to place all project-related customizations in a `.dir-locals.el` file placed at the root of the project source tree. Then, when emacs opens any file under it, it applies these customizations. This way, uniform configurations can be shared across multiple developers using emacs.

Also see atomized’s post on directory local variables where he brings up some problems he’s faced with the directory-local variables feature.

The transparency of the emacs frame can be now controlled via the `alpha` frame parameter. Try something like: `(set-frame-parameter (selected-frame) 'alpha 70)`

This is undoubtedly cool (I bet XCode and Visual Studio can’t do that!) and maybe useful in one-off cases. But I don’t think anyone would have long emacs sessions with a transparent frame — it hinders visibility and is distracting.

D-Bus is a Unix IPC system for applications to talk to each other. I’ve not had a chance to play with it, but for an example of using `dbus` in emacs, see `djcb`‘s using D-Bus example.

This will be a welcome enhancement for linux programmers. Being a Mac/Win user, I’ve enjoyed anti-aliased fonts for some time now. For details and screenshots on Linux, see XftGnuEmacs on EmacsWiki. Alexandre Vassalotti has a Pretty Emacs Reloaded package for Ubuntu. Another page describing how to set this up on Linux.

By the way, with anti-aliasing, I love the Bitstream Vera Sans Mono and Monaco fonts for programming (in particular because they have nice distinct shapes for `l`/`1`).

If `delete-by-moving-to-trash` is non-nil, then deleted files are moved to the Recycle Bin/Trash. It’s surprising that this feature wasn’t already available.

Some neat search and highlight related enhancements I found:

`M-s a C-s`and`M-s a M-C-s`in dired runs multi-file isearch on the marked files. Should come in handy.- For incremental
*word*search, there’s a new command`isearch-forward-word`globally bound to`M-s w`. While doing an isearch, the same key`M-s w`(now bound to another new command`isearch-toggle-word`) toggles word searching on/off. `M-s h r`(bound globally to the command`highlight-regexp`) can be used to highlight all occurances of a regexp in a buffer. The same key can be used when doing isearch to highlight all occurrances of the current search string (it calls`isearch-highlight-regexp`internally).`occur`can now be invoked using`M-s o`. The same key runs an`isearch-occur`when doing an isearch.- If an isearch is started in the minibuffer, it searches
*in the minibuffer*! - You can now specify group numbers explicitly in the regexp via an extended form of “shy” groups:
`\(?`. Again a handy thing.*number*:*regexp*\)

`C-x C-+`or`C-x C-=`increase the text face size (font size), while`C-x C--`decreases it (that is, zooming in/out).`C-x C-0`restores to the default size. These are mapped to`text-scale-adjust`. You can also do stuff like`C-x C-+ C-+ C-+`, that is, omit the`C-x`on repeated commands.`C-l`now does something more useful. On the first invocation, it moves the current line to center of the window (as it did earlier). But on the second successive invocation, it moves the current line to the top of the window; and then to the bottom on a third invocation. Subsequent invocations cycle through these three placements.`C-l`is now bound to the`recenter-top-bottom`(in previous versions, it was bound to`recenter`).

`linum-mode`is a minor-mode for line numbers in the left margin. This is like vi’s`:set nu`command. I have already had the linum package installed for some years now, and had used it occasionally. It is nice to see it finally become a part of emacs.- There’s a new game called
`bubbles`(somewhat like “bejeweled”) `proced`is a “process editor” and creates a buffer with a list of processes running on the system (much like`ibuffer`does for buffers, or`dired`for files). You can use commands like`k`to kill a process etc.`proced`was not available on the Mac, while on Windows, it didn’t allow me to kill processes.

- The
`shift-select-mode`variable (`t`by default) enables Win/Mac style selection by pressing the shift key first, and then pressing the right/left arrow keys to grow/shrink selection. - Pressing
`TAB`when transient mark mode is now on (the default now) causes certain commands like`M-q`(`fill-paragraph`),`M-$`(`ispell-word`) and`TAB`to operate on the region instead. - Completion now takes text after the point in minibuffer into account for filtering the remaining alternatives (that were generated by the text before the point). For instance, if I’m trying to open the emacs PROBLEMS file, and the minibuffer input is
`d:/progs/emacs/etc/`, and I type`oo`and bring the point back to before the`oo`, so that the input now looks like:If I then press

`TAB`, emacs not only restricts the choices to the two files that have`oo`in them (`COOKIES`and`spook.lines`) but also updates the minibuffer input`oo`to`ook`(since both of these have a`k`following`oo`): - Minibuffer input for shell commands (
`M-!`) also allows completion. `M-x butterfly`flips the desired bit on the disk platter. It is almost a clichĆ© now — but somehow it’s still funny!

That’s about it! More pleasant surprises will turn up as I play more with it.

*A word on the emacs etc/NEWS file*. I would never have discovered some of the features mentioned above without digging through the

I was going through the first chapter of the book *Graphical Enumeration* by Frank Harary and Edgar M. Palmer when I chanced upon this perplexing footnote:

Read wrote Wright that both Read [R2]

^{1}and Wright [W3]^{2}were wrong. So Read and Wright wrote a joint erratum [RW1]^{3}to set things right. This may be wrong since Wright asserts that Wright wrote Read first.

It appears on Pg. 17 in reference to k-colored graphs. Read and Wright are, of course, the mathematicians Ronald C. Read and Edward M. Wright!

A quick glance at the bibliography confirms that the above footnote describes, even if humorously, a true incident. However, I can’t say what the last sentence means: This may be wrong since Wright asserts that Wright wrote Read first

. Does it mean:

- There is a genuine priority dispute as to who figured the error out [I don’t think this is the case]. Or,
- Since [RW1] paper has Read as the first author (so, in that sense, “Read wrote first”), Wright couldn’t have written first. Or,
- Since “write” must happen before “read”, Wright wrote first. Or,
- It doesn’t mean anything — the authors are just playing around with words!

I could not find anything relevant by searching the phrase “Read wrote Wright” on Google.com. I’ll be eager to learn any other clues the reader might have as as to the meaning of the last sentence of the footnote.

*Aside*: It is sad that the *Graphical Enumeration* book, which was published by Academic Press, New York (1973), has apparently gone out of print. I’ve added it to the out of print math blog.

- [R2] R.C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math.
**12**, 409–413 (1960). - [W3] E.M. Wright, Counting coloured graphs, Canad. J. Math.
**13**, 683–693 (1961). - [RW1] R.C. Read and E.M. Wright, Coloured graphs: A correction and extension, Canad. J. Math.
**22**, 594–596 (1970).

As I attempted to solve more and more problems, I found a disproportionately large number of them centered around the theory of numbers. These involved important ideas of number sieves, congruences, continued fractions, the Farey series, solving Pell’s equation, implementing Shanks Tonelli algorithm etc., and had me sifting through Hardy and Wright’s book every so often. But after a while they weren’t so much fun. I did, however, find enough problems of my interest to get me hooked — enumeration and dynamic programming (208, 161, 209, 172, 169, 215, 219), probability (227, 213) and those occasionally unique ones like 197 (concerning the “steady-state” behavior of a certain sequence). Working through these problems made me realize what a treasure PE was. Kudos to Colin “Euler” Hughes and the PE-team for their effort in running this great site!

In addition to having the fun of solving the problems myself, I could study the solutions worked out by other members in the forum. Seeing the elegance, efficiency and analyses of some of their solutions was a rewarding (even if a bit humbling) experience. A case in point is the solution to Robot Walks (208) by `sajninredoc` and `stijn263` (among others), where they reduce the enumeration problem to a single summation. And then there were those APL/J programmers with their cute one-liners!

In this entry, I shall outline my solutions (and their performance characteristics) to the Trominoes Tiling (161) and Number Mind (185) problems. To solve these problems, I used the ZDD techniques I had just studied in Knuth’s pre-fascicle 1B (now in print as Vol 4 Fascicle 1). I had blogged earlier on Knuth’s Fun with ZDDs musing.

Trominoes Tiling (161) is almost the tiling problem of TAOCP 7.1.4 — (130) with the difference that only trominoes are allowed (no monominoes or dominoes) and the grid-size is slightly larger (`9x12` instead of `8x8`). I reuseed, with the obvious changes, the ZDD routines that I had coded while working out that section. Since Knuth has already explained the ideas involved so beautifully (see the text around 7.1.4 — (129)), I shall only briefly sketch the ZDD construction before giving some performance statistics.

To begin, we first model the tiling problem as an Exact Cover. This involves creating a boolean matrix of `9x12` = `108` columns (corresponding to cells of the board) and `526` rows (corresponding to the ways of placing the `L` and `I` trominoes in all possible orientations on a `9x12` grid). We have iff tromino placement occupies cell . The strategy for placement numbering I used is shown below for the simpler `4x4` case (the cells are numbered in the usual row-major order). Since the placement strategy decides the variable-ordering of the ZDD and hence its size (unless, of course, we choose to sift/reorder variables later on), it is important to pick a placement strategy that is not too inefficient.

Having constructed the boolean matrix, to enumerate the tilings, we find the number of ways to select some rows of the matrix such that if we inspect any column, precisely one of the selected rows contains a `1` in that column. Hence the name “exact” cover — we neither want to leave any cell uncovered, nor do we want parts of two or more trominoes to overlap.

Exact covers can be enumerated using Knuth’s Algorithm X — an efficient backtracking technique implemented using an idea Knuth calls Dancing Links (DANCE program, paper at arXiv, Computer Musing video, ASL Implementations for dancing_links and toroid_node_t). Algorithm X not only *enumerates* the solution, it in fact *generates* them all!

To enumerate exact covers using ZDDs, using the matrix produced in the step above, we construct the boolean function (Eq. 7.1.4 — (129)):

where boolean variable indicates selection of row of the matrix (that is, placement a tromino in the orientation ), = is the set of rows that have a

For various ways to efficiently construct the above ZDD, see Exercise 7.1.4 — 212. The function can itself be implemented using Exercise 207’s “Symmetrizing” operation.

Once we have the ZDD for the boolean function above, the *number of solutions*, i.e., the number of vectors that make true (which are precisely the vectors representing exact covers) can be readily found using the ZDD-analog of Algorithm 7.1.4C.

*Runtime performance of the solution*: The resulting ZDD involved 526 variables and had a size of `7893743` zeads. Without invoking any garbage collection, the peak memory usage was `~600MB` (where each zead in my implementation was a `20`-byte node); time taken was `34s` (user) and `85s` (elapsed). Given that my memos weren’t very optimized (I had used GCC’s `std::map`) and neither had I tried doing any variable reordering, the performance seemed reasonable.

A dynamic programming approach (like one I later used for Crack-free Walls (215)), should have been able to give the results in about a second (this was confirmed by posts on the forum). Nevertheless, the ZDD solution was fast enough to keep my conscience clear of any violations of Project Euler’s one-minute-rule.

*Aside*: The Crack-free Walls (215) problem is kind of like TAOCP Exercise 7.1.4 — 214 (Knuth calls it “faultfree”) and should be amenable to the ZDD attack. There, however, appears to be a danger of hitting space-out since the grid-size `10x32` is somewhat large. I’ve not tried this approach.

Number Mind (185) was the other PE problem that I solved with ZDDs. In this problem we’re to uncover a 16-digit number given a set of “guesses” of the form:

5616185650518293 ;2 correct

3847439647293047 ;1 correct

5855462940810587 ;3 correct

. . .

The guesses along with the “hit-rates” provide partial information about the secret number. Our aim is to find the “secret” number corresponding to the set of guesses.

To solve this problem, we create variables representing the condition that ^{th} digit () is (). We then have the following constraints:

- Since each position can hold just one digit, for each exactly one of can be true. Constraints of this kind correspond to terms like , where is again our friend, the symmetric boolean function.
- Each of the given guess “hit-rates” must be satisfied. As an example, the third constraint “
`5855462940810587 (3 correct)`” is represented as:

Using the symmetrizing operator from Exercise 7.1.4 — 207, both the above kinds of constraints are easily represented. Finally, we compute the `AND` (or, `INTERSECT`, if one prefers family-of-subsets point-of-view) of the individual constraints — and we’re left with the final ZDD representing the family of feasible solutions (in our case, the solution in fact turns out to be unique).

*Runtime performance of the solution*: The ZDD had `160` variables , program execution had a peak memory usage of `~1GB` without any garbage collection or reordering (zead-size `20`-bytes), size of the largest partial function was `4665450` zeads. The running time was `~16s` (both user and elapsed).

Comparing the ZDD solutions to the two PE problems, I think it was the kind of “unstructured” problem like Number Mind where the ZDD technique really shined.

]]>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 (the FALSE sink) — if having TRUE results in the subfunction rooted at to become FALSE, then we skip testing 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).

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!*

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 such that is TRUE) correspond to family of subsets, with each solution corresponding to a subset where belong to the subset iff [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 . We use the following rules to represent those using ZDDs [again, see TAOCP Exercise 7.1.4 — 203]:

*The Empty Family*, , is represented by (the FALSE sink node).*The Unit Family*(the set comprising just the empty set), , is represented by (the TRUE sink node).- If 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 be the
*least*element of universe that*supports*— that appears in at least one set in . [see answer to TAOCP Exercise 7.1.4 — 197 for the definition of supports]. Then define sub-families and of with and . These sub-families correspond to those sets that don’t and do contain . Then, inside the computer, the family corresponds to a*zead*(ZDD-node) labeled with`LO`and`HI`branches going to the ZDD representations of and respectively. Notice the recursive definition (see Knuth’s diagram below).

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).

Here, Knuth took the example of family = the family of 2-element subsets of , that is, and explained how to construct its ZDD (see diagram above). The family is , so its least support is . The and families turn out to be and respectively. So we have `LO` and `HI` branches (dotted and solid lines in the diagram above) going from to the ZDD of and that we recursively construct. Notice that no node with the same (`V`, `LO`, `HI`) triple appears twice in our data structure (that is, the diagram is *reduced*). So although Knuth is giving a Christmas “Tree” lecture, a *ZDD is not a true tree* because overlapping subtrees are combined into one — rather, a ZDD is a DAG (directed acyclec graph).

When working on real problems, there’re usually many functions we’re working with simultaneously. So instead of a ZDD representing a single function, we really have a *ZDD-base* where common zeads are shared across functions. Knuth constructed the ZDD-base of the two functions and . Inside a computer, a ZDD is represented as a linked structure, where each node of the ZDD, zead, is represented as a record with 3 fields: `V` (Variable ID#), `LO` (Low Pointer), `HI` (High Pointer). Sink nodes have their `V` field set to , with `LO` and `HI` fields pointing back to them (see diagrams above).

ZDD-bases satisfy certain laws:

- No two nodes have the same triple (
`V`,`LO`,`HI`) — that is, the structure is*reduced*. - No node has
`HI`= 0, except sink — this is the reason Minato called it*zero-suppressed*— the idea is to “skip over” such nodes - For non-sinks f,
`V`(`LO`(f)) >`V`(f) and`V`(`HI`(f)) >`V`(f) when f > 1 — that is, the nodes are*ordered*with`V`-fields are always increasing as we walk down the structure

ZDD-bases, which though conceptually easy to understand, are non-trivial to implement efficiently because behind the scenes, lots of things have to be taken care of:

- New nodes are born and old ones die — nodes have to be efficiently
*allocated*,*ref-counted*and*garbage-collected.* - The UNIQUE-table (hash-table for (
`V`,`LO`,`HI`) triple) has to be efficiently maintained and kept fresh with any changes made to the ZDD. A*memo-cache*has to be similarly maintained for caching recently computed results (like`AND`/`OR`of function).

Knuth’s BDD15 (literate) program, available from his Downloadable Programs page should provide an instructive study of the issues and techniques involved. I gained a lot of clarity on tricky BDD topics like ref-counting nodes, reordering of variables, efficient function composition etc, by studying Knuth’s BDD14 program. I used it as a reference whenever I got stuck anywhere with my own BDD implementation. BDD15 should be equally useful, and I plan to find time to study it soon.

Nested parentheses are a natural way to describe tree structures (LISP being a good example). In this example, Knuth showed how to represent the 5 ways to correctly nest 3 sets of parentheses using a ZDD:

Parenthesis Nesting | ZDD subset |
---|---|

( ( ( ) ) ) | |

( ( ) ( ) ) | |

( ( ) ) ( ) | |

( ) ( ( ) ) | |

( ) ( ) ( ) |

In this representation, subscripts correspond to positions in the string with / denoting the kind of parenthesis. The ZDD for this represents a family of 5 sets (each containing 6 elements). In the ZDD, the variable ordering used is (see the diagram above).

For parentheses pairs, the ZDD contains 14 nodes and don’t appear to save a whole lot. However, if we consider parentheses pairs, the ZDD of 602 nodes represents 1.3 trillion solutions! This compact ZDD structure encodes all those solutions without having to store them explicitly; and yet we can ask questions about the solutions. Like, say, analyze solutions that contain . The figure 1.3 trillion comes because the number of ways to nest pairs of parentheses in a balanced way is the Catalan number, . See TAOCP Exercises 2.2.1 — 2, where a proof of this fact is given using a “reflection principle”; and also Eq. 2.3.4.4 — (14), which deals with enumeration of binary tree.

So, using only a small space, ZDDs can represent large families of combinatorial sets of interest, allowing efficient operations on these families and helping solve problems related to them. For example, if a family of sets is represented as a ZDD, one can quickly (in terms of the size of the ZDD) find a random set of the family.

*[This is actually Ex. 7.1.4 — 203, 204.]* People from different branches of combinatorics have different operations they want to perform on families of sets. The usual ones are:

- Union:
- Intersect:
- Difference:
- Symmetric Difference:

All four operations can be efficiently implemented given the ZDDs of and using an easy recursive process based on the smallest support for the two functions. The implementation can be sped up using a *memo-cache*.

In addition to the ones above, more operations are possible: (meet), (join), (delta), (quotient), (remainder). Knuth said he had recently discovered another binary operation that he thinks might prove useful. He likes to call it *disjoin* since it is similar to the join operation, but works on disjoint sets:

The is not what Knuth uses as the symbol for disjoin (for the correct symbol, see his hand-written version in the snapshot above), but I haven’t yet figured out the name for that symbol.

Even more operations on families are possible (see Exercise 7.1.4 — 236): (closure), (maximal elements), (minimal elements), (nonsubsets), (nonsupersets), (cross elements). Seeing all these funny symbols, somebody chimed in an obligatory APL joke; somebody else mentioned “family values” in connection with family algebra. People were certainly having fun!

Towards the end, Knuth mentioned various applications of the ideas he had spoken of earlier.

Exact Cover Problems essentially involves selecting rows from a given boolean matrix in such a way that each column among the selected rows has exactly one 1. A popular example of this kind of problem is Sudoku. Knuth, in an earlier musing, mentioned an efficient dancing links algorithm for solving such problems.

In the present musing, Knuth showed the examples of covering an 8×8-chessboard with 32 dominoes [7.1.4 — displays (127) to (129)]; covering with monominoes/dominoes/trominoes [display 7.1.4 — 130]; or covering with dominoes of three colors (red, white, blue) with no adjacent dominoes of the same color [Exercise 7.1.4 — 216].

Knuth showed how, with 5*26 = 130 variables, it is possible to store all five-letter words of the SGB (Stanford GraphBase) in a ZDD, and perform operations such as:

- Querying for words that match the pattern
`t?u?h`. This involves using family algebra on ZDDs to compute where is the “pattern” . - Finding all words such that when the letter
`b`in it is changed to the letter`o`, we still get a valid five-letter word. This involves computing , which gives words like`busts`(),`herbs`() etc.

Knuth illustrated application of ZDDs to graph problems by showing how it can be used to find various constrained arrangement of queens on a chessboard (queens-graph): kernels, maximal cliques, dominating sets etc. [See Exercise 7.1.4 — 241]. All these operations can be implemented using ZDDs and family algebra operations (see Knuth’s sheet). Letting to be the family of edges of a graph/hypergraph (such that members of are subsets of the sets of vertices ):

*Independent Sets*are (Knuth uses Weierstrass P to denote the power set )*Maximal Independent Sets*(or*Kernels*) are the maximal elements of the independent sets*Dominating Sets*are where*Minimal Dominating Set*is*Maximal Induced Bipartite Subgraphs*is

Knuth had so much interesting stuff to talk about. But he had spoken for 90 minutes already — so he decided to stop.

I’ve been studying `fasc1b` for about three months now and have been enjoying myself thoroughly — learning new data-structures & proof techniques, developing my own BDD-base, working out the programming exercises, playing with Conway’s game of Life, coloring graphs and more. I’m still only two-thirds through with the exercises (that total to a respectable 263) — just about to start working on the ZDD exercises. I hope to be able to work my way through the exercises by the end of this year.

Here’s part (2), the tougher part, of the problem: Values for a random variable are generated independently and uniformly over . By accumulating these values, your job is to reach a sum between and , where is a positive integer, and . You can ask for successive values of this variate as many times as you wish, but you must add each such value to the running total you maintain. If the accumulating sum exceeds , you loose; if you manage to get a sum between and , you win. What is the probability of winning as ?

Earlier that year, I had finished studying Knuth’s Selected Papers on Discrete Mathematics. That is a precious collection for anyone interested in discrete structures, combinatorics, asymptotics, random structures etc. I had especially enjoyed one of the papers, “The first cycles in an evolving graph” (with Flajolet & Pittel as co-authors), not only for the neat results but also for the techniques used to get asymptotic values/bounds of certain integrals. That paper helped introduce me to, and drive home the importance of, the fascinating field I later came to know as Analytic combinatorics (also this). That paper analyzes the evolution of a random graph, where edges are successively added to a set of vertices(under different random graph models). Among other results, it shows that expected length of the first cycle to appear is proportional to and the size of the component having this cycle is — quite fascinating stuff. At any rate, with these analytic techniques still fresh in my mind, I attacked the problem by trying to find a bound on the probability integral. Details follow (with a I-to-we switch).

To begin with, we use the classical Central Limit Theorem to replace the sum of independently and uniformly distributed variates (each of which had mean and variance ) with a Normal variate with mean and variance .

Now, the probability of “hitting” (i.e., achieving a sum lying within the interval) in *exactly* “moves” is , where is the probability of hitting in exactly moves and is the probability of jumping from to the desired interval in the m^{th}-move.

When , ; and when , . is the probability density function of the aforementioned normal variate; so

Thus the probability of success in precisely moves is

which simplifies to

Since we’re interested in a success in any number of moves, we must evaulate , and finish by taking the desired limit .

To evalutate the sum over , we replace the summation by integration (see caveat below) and substitute the variable of integration from to (resulting in an extra factor of ). So our final integral turs out to:

Expanding the integrand (of the first integral) in powers of , the integrand becomes:

When we integrate over and take limit , all terms other than the first go away. As for the first term, it yields since

(where is the Error function).

Whew! That was heavy going. Let us catch our breath. Okay. So the answer to the original problem turns out to be . As a sanity check, it’s value turns out to be 0 at and 1 at . Good.

*Caveat*: The above derivation is *not rigorous* (in fact, it is somewhat sloppy) for at least the following reasons:

- Convergence of many integrals/summations is implictly assumed
- The error term has not been calculated when changing a summation to an integration. Euler Summation Formula (also TAOCP 1.2.11.2) should have been used to bound the error terms.
- The Central Limit approximation has been used without being demonstrated that it is being applied only close to the peak of the distribution, and not far into the tails (unless justified)

*A question:* If you read the publisher solution on Ponder This, it says, “Values between 0 and 1 are equally likely but larger values are more likely to cause the sum to exceed . So as the differential probability that is .” *Can the reader explain the reasoning behind this differential probability?*

Some time back, I had read a hilarious piece by Shashank, a friend of mine from the days at BITS, Pilani. The *auto-podal-tow* phenomena that he describes has to be seen to be believed: an autorickshaw towing another with one of the drivers using his leg as a connection! A good soul captured the moment and licensed it under Creative Commons Attribution-Noncommercial 2.0 Generic.

It would have been unfortunate to have left a phenomenon as recurrent as the auto-podal-tow without a name. Shashank did his part, and I’ll do mine by documenting two other phenomena that deserve to be “named and conquered”. People who haven’t been on Indian roads will have to get their imaginations working (since I couldn’t find images for them).

First there is, what we’ll call, the *autorickshaw-big-v-formation*: In a 2-lane road, a bunch of auto-rickshaws (usually three to five in number) do a V-formation that’s impossible for anything but a motor-bike/scooter to breach. While the V-formation is the most commonly sighted one, other tactical formations are also deployed to advantage.

Second, there’s a phenomenon known as *differential-velocity-autorickshaw-overtake-maneuver*. To a casual observer it would appear that two or three autorickshaws are engaging in a line-abreast formation; but in all probability, something more subtle is under way. What’s really happening is that one of the autorickshaws is running just a little bit faster than the one alongside it (any non-zero , no matter how small, would be sufficient for our purpose); and the -faster autorickshaw is doing the only reasonable thing to under such circumstances — overtake the slower one. The phenomenon usually lasts for a good one-two minutes before the “formation” is broken.

Over the years I’ve occasionally chanced upon “things” about these topics that I wished I could have shared with more people. While many of them have been spoken of elsewhere, others haven’t generally been publicized on the web/blogsphere. Of course, others no doubt would have thought of or come across ideas similar to what I would be blogging about; so I definitely do not assert any claims of being the first to discover them. But I do feel that there would be some people interested in reading about them.

Even if I turn out to be the only one reading this blog, there’s a very good reason why I should still do it — it would help improve my clarity on the things I feel important enough to share with others. Steve Yegge wrote a neat post explaining just this. Dear reader, if you don’t blog (for whatever reasons), you should at least consider reading that.

A bit on the timing: I’d been thinking of starting a blog for quite some time now (all the while “gathering” interesting material to speak about), and my sabbatical (this whole of December) have given the nudge I needed to finally start one.

Till you come ’round again, here’s a little problem from IMO to ponder on: If is defined from such that for each , then prove that for each . For another interesting problem involving the solution to a functional equation, check out TAOCP Exercise 1.2.4 — 49.

]]>