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.

The Winners

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.

The Method

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.

Functions Taking Lots of Parameters

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.

On a Serious Note

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.

Links

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 n wires have been labeled at one end with alphabetic codes 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.

Small Cases

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 General Case

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:

, corresponding to the assignment

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.

Extensions

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!

How the Book Works

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.

Reaffirm Your Own Beliefs of Good Style

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.

What has Changed in These Three Decades?

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.

The Rest of the Post…

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!

On Obscure Code

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)

On Healthy Skepticism

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

On Clever Programming

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)

On Temporary Variables

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 Telephone Test

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)

On the Shape of Programs

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)

On Program Structuring

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)

On Premature Optimization

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

On Loosely Coupled Modules

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)

On Encapsulation

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)

On Functions as Black-boxes

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

On Top-down design

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)

On Recursion

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)

I/O Programming — Never Trust Any Data & Remember the User

Input/output is the interface between a program and its environment. Two rules govern all I/O programming: NEVER TRUST ANY DATA, and REMEMBER 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)

On Bounds-checking

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)

On Bug Infestation

Where there are two bugs, there is likely to be a third. (Page 102)

Floating Point Numbers Are Like Sandpiles

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)

On Efficiency

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)

Algorithmic Improvements versus Tuning

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)

On Profiling

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)

On Documentation

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)

On What Documentation Should Comprise

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)

On Following the Rules

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)

A Treasure Trove of Pithy Rules

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.

1. From the Introduction: Write clearly – don’t be too clever.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.

Prof. de Bruijn, his cycles, and average height of trees

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:

.

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 things he has spent most of his life 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).

The Book: A Pragmatic Exposition

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.

Uniform Estimates

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:

.

the -notation implies two implicit constants

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

, because,

the implicit “constants” and depend on the parameter

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

.

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.

Asymptotic Series and Convergence: Some Curious Facts

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

, and,

.

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:

,

So…

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.

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?

The C-n and C-p line-motion commands now move by screen lines

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.

Emacs can start as a daemon (the multi-tty feature)

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 create frames or -t for terminal 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.

Two sessions (terminal and frame) working on the same buffer.

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 save-buffers-kill-emacs.

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

Directory-local Variables

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.

Emacs can have transparent frames

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)

A Transparent emacs frame

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 and ZeroConf

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.

Anti-aliased font on X11

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

Recycle Bin/Trash can be used for file deletion

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.

Search Enhancements

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: \(?number:regexp\). Again a handy thing.

Some New Default Keybindings

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

New Modes

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

New Behaviors

• 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 NEWS file. It lists several other improvements and additions that I’ve not even had time to try! I couldn’t find a copy online, so here’s a link to a local copy of the emacs 23 NEWS file (build 23.0.92.1).

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]¹ and Wright [W3]² were wrong. So Read and Wright wrote a joint erratum [RW1]³ 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.

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

My experience with Project Euler Problems

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): Enumerating Exact Covers using ZDDs

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.

Tromino Placement Numbering for a 4x4 grid (also used for the rows of the exact cover matrix and ZDD variable ordering)

Exact Cover Matrix (for the simplified 4x4 case)

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

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): Using ZDDs to satisfy an ad-hoc set of constraints

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

Conclusion

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!

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

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

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.