This year, 2022 marks the 60th anniversary of that fateful day in 1962 when a 24-year-old Donald Knuth started writing “The Art of Computer Programming.” Now approaching his 85th birthday, Knuth has become almost a legend in the world of computer programming — and he’s still writing additional volumes for his massive analysis of algorithms.

But every year, right around Christmas time, there’s another tradition. Knuth gives a special lecture “pitched at non-specialists” for a small audience at Stanford University (where Knuth is a professor emeritus) and a larger audience online. Because of the pandemic, it’s been three years since Knuth has been able to honor this tradition.

So this year’s audience greeted Knuth with an extra sense of anticipation.

The Magic of Trees

Hunched over a notepad (which was projected onto a screen behind him), Knuth began the 26th annual Christmas lecture by pointing out that the evening’s topic had been hiding in plain sight for two decades. For the first 20 years, they’d called them the “Christmas tree” lectures, since “trees are one of the most important things to a computer scientist. And every year I learned at least two new cool things about trees…”

About five years ago they’d changed the name to just “Christmas lectures” — but the problem wasn’t that trees stopped being interesting. “I still learn cool things about trees every year. But they’re getting harder and harder to explain to a general audience!”

So this year’s triumphant “homecoming” lecture would indeed include trees — specifically a phenomenon Knuth describes as “twintrees,” along with Baxter permutations, and Floorplans. Knuth noted they’re all topics touched on in the latest volume of The Art of Computer Programming, before jokingly reminding the audience that his book makes an excellent Christmas present.

He added with a laugh that “From a lecturer’s point of view, it’s always best when you have something that you love to talk about.”

Knuth began by introducing the audience to binary trees — a familiar branching data structure where, as you work your way down, each node can have up to two lower nodes (a left and a right “child” node). But then he showed the audience “one of my favorite algorithms of all time, for more than 50 years… binary tree insertion.” This is where data is inserted in the left fork if it’s lower than the key value, and in the right fork if it’s higher.

To generate a truly random sequence, he’d let members of the audience shout out where the numbers should appear in a sequence of eight numbers — then converted that jumble into a tidy binary tree on his notepad.

But then going through those same numbers in reverse order, Knuth magically produced a complementary second binary tree — one where there’s no overlap when you write out each parent node’s subnodes, for both trees, onto a single chart.

Knuth demonstrated this using red ink to write the subnodes of one tree, and then green ink for the subnodes of the other:

Rare? Hardly. Knuth shared the surprising calculation that there are over 10,000 eight-node twintrees. “This tree insertion algorithm has been something that I’ve been playing with from the middle 1960s,” Knuth told the amazed audience “and I’ve used it in a zillion computer programs.

“But I never — it took 50 years before I understood that it also gave me twintrees at the same time!”

Smalls and Bigs

The next mathematical curio was Baxter permutation, a kind of number series for which Knuth offered a beautifully simple definition. If the numbers above any fixed numbers k and K + 1 are “bigs” and the numbers below them are “smalls,” then in Baxter permutations, “I can’t have a big followed by a small.” (And the converse is also true. If in the sequence k is preceded by the larger k + 1, then “I can’t have a small followed by a big.”)

Knuth provided an example — but then played with the ramifications.

Reversing the order of the numbers always produces another Baxter permutation. And you can also produce another Baxter permutation just by adding a constant to each number in the sequence. If that constant is equal to or larger than your sequence’s highest number, you can then produce an even longer Baxter permutation by appending that sequence onto your original sequence. (Or even by pre-pending that sequence.)

All these scenarios retain the original unique property of the Baxter sequence, Knuth reiterated to the audience. No matter which pair of numbers separated by one you choose for your test, “All the small guys are all going to come first, and the big guys later.”

Knuth presented the smallest possible non-Baxter permutations — 3, 1, 4,2. He called it “the pi mutation,” since it’s a rounded approximation of pi to four digits.

Over the years Knuth has found that when testing conjectures about permutations, “if the conjecture is false, it almost always fails at the pi mutation.” The reverse of the sequence is also not a Baxter permutation — the only two such failing sequences (out of 24 possible sequences).

Three Beautiful Algorithms

The final topic for the evening was floorplans — a familiar-looking breakdown (or “decomposition”) of a rectangle into smaller subrectangles. (Or, this being a floorplan, into “rooms.”) As an aside, Knuth pointed out that this kind of modeling becomes important when creating silicon chips — where the “rooms” become modules or logic gates.

And then he asked a provocative question: What does it mean for two floorplans to be the same?

Knuth rearranged the order of his coordinate names on both his X and Y axis, and then drew another floorplan where the rectangles retained their same position relative to each other. (“I might as well write the whole thing down, because this is going on the internet,” Knuth joked at one point.)

This particular floorplan followed the Tatami condition — there’s no “four corners” point where four different rectangles meet at a single point. Knuth showed alternate ways of diagraming the floorplan — which brought him to his grand finale. “What does this have to do with twin trees and Baxter permutations?”

Amazingly, when using that final method of diagramming, every sequence of numbers that’s a Baxter permutation gives you a valid floorplan. And going through that same sequence, first forwards and then backward, always gives you a pair of twin binary trees that — you guessed it — is again perfectly complementary. (There’s no overlap when you write out each parent node’s subnodes for both trees onto a single chart.)

“You give me a Baxter permutation, I can tell you what the floorplan is. You give me a floorplan, I can tell you what the twintrees are, and you give me a twintree, I can tell you what’s the unique Baxter permutation that generates it!”

As Knuth explained on his webpage, “Three fascinating concepts, which seem at first to be entirely unrelated to each other, are in fact in one-to-one correspondence, via three beautiful algorithms.”

Knuth has written programs that perform all the operations — like a program that converts Baxter permutations into floorplans. (“If you give it a permutation that’s not a Baxter permutation,” Knuth tells the audience, “it sneers at you, and says ‘Too bad. You lose. It’s not a Baxter permutation!” ) He’s even used Unix pipes to send the output of one program as the input for the next — and “I get back, of course, the one I started with.”

> baxter-to-floorplan | floorplan-to-twintree-ttform | twintree-to-baxter

After 60 years of writing, and a lifetime of exploring mathematical algorithms, Knuth looked up to see that he’d talked 10 minutes past the scheduled hour. And then he joked that he was glad. “I was expecting to be 20 minutes over.”

“Thanks for listening, and I’m ready for questions.”

WebReduce

• Short French documentary commemorates the creation of the Prolog programming language in 1972.
• Archive.org unveils a browser-based Palm Pilot emulator for 569 apps and games from the mid-1990s.
• There’s a brand new (optional) standard for over-the-air TV broadcasters.
• EFF annual report touts battles against surveillance technologies — and results from its 4,000-member survey.