A treat for all computer scientists or anyone with a lively mind is the annual Christmas Lecture given by Donald Knuth. After a Covid pause in 2020 and 2021 they are back and it's an Xmas Tree lecture this year!

Knuth's xmas lecture was originally a lecture on the tree data structure but there is only so much that you can do with a tree - or is there? This year the topic returns to trees with a theme that connects three apparently very separate ideas.

Some find  Knuth's presentation difficult to deal with but if you can stick with it you will discover one of the few places on the web where someone talks to you about clever things in an informal way that displays how they think. Much of this is spontaneous and the low-tech presentation - Knuth writes long-hand on paper - adds something that a flashy PowerPoint would never achieve. You can of course disagree.

The three topics are Twintrees, Baxter Permutations and Floorplans, of which I had encountered only Twintrees before. These are hardly core topics, but they are interesting nevertheless and they are included in Volume 4B of the Art of Computer Programming which was published this Fall.

Click on the image to find out more.

Twintrees is a simple idea that is difficult to describe. A binary tree can have a twin in which each node only has a left or right child in one of the trees. That is, if a node has a right node in the first tree it doesn't have a right node in the twin. If it doesn't have a right node then it does have one in the twin. You can work out that terminal nodes, i.e. with no right or left nodes, have both nodes in the twin tree. This sounds very strange so much so that you might think that there are few such pairs. In fact, as Knuth shows very simply, there are lots of them. One thing that might help understand the video is that what Knuth calls "symmetric order" is what is mostly referred to as "inorder".

Baxter permutations are "nice" in that they avoid the permutation embodied in Knuth's Pi permutation that he says seems to be the one that breaks any false conjecture you might have about permutations. The definition of a Baxter permutation is very difficult to follow because it is defined by a pattern that it doesn't contain. It comes down to looking at four elements of the permuation i, j, j+1 and k with i<j<k such that the permutations at these positions move the elements so as to invert j and j+1. That is, j is moved to the right and j+1 to the left. and the elements at i and k between them, but in the same order:

Or it leaves the order of j and j+1 alone and inverts i and k between them:

You can see that these patterns are not "nice". They swap the order of one pair and place what was "inside" the sequence "outside" . A Baxter permutation doesn't do this. For example, the Pi permutation which contains   3...14...2 gives the diagram:

You can see that the elements at i and k are swapped over and they are now between the elements j and j+1. Thus the Pi permutation is not a Baxter permutation.

Put simply - Baxter permutations do not do this sort of "shuffling".

It is worth noting that Knuth started this idea of permutation patterns in an analysis of what sequences can be sorted using nothing but a stack.

After Baxter permutations Knuth moves on to Floorplans - the division of rectangles into rectangles - i.e. rooms. This has applications in areas such as making silicon chips. An extra condition is that no four rectangles have a common corner.  This means that the room walls always meet in a T junction. Floorplans are equivalent if the rooms have the same relationships with each other,  i.e. share the same walls. Knuth shows how different arrangements can be considered the same and how to construct two standard arrangements.

The big surprise (is it?) is that if you take the standard arrangment of any floorplan and read off a binary tree from the diagonal, treating horizontal walls as a left node and vertical walls a right node, and then do the same to the second standard arrangement you get Twintrees. Also the order of the rooms on the diagonal is a Baxter permutation.

Now watch the video:

It is amazing that a floorplan is connected to a tree structure and a permutation. Knuth also gives programs that converts between the represenations.

So much depth in something so simple.

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way and The Trick Of The Mind: Programming and Computational Thought, aimed at programmers and non-programmers alike, which examines the nature of programming and reveals why it is a very special skill.

More Information

Computer Musings

Related Articles

Donald Knuth & The Art of Computer Programming 

The Art Of Computer Programming - Ace Gift For Any Programmer 

Welcome To A New Part of Donald Knuth's Magnum Opus

No Donald Knuth Christmas Lecture This Year ...

Knuth's 25th Christmas Lecture - Pi And The Art Of Computer Programming

Knuth's 22nd 360 Degree Not Christmas Tree Lecture

Knuth's 21st Not Christmas Tree Lecture 

Donald Knuth's Christmas Tree Lecture 2017

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:0137935102>

<ASIN:0201038064>

<ASIN:1871962439> 

<ASIN:1871962722>