Due to the COVID-19 pandemic, the last couple years Donald Knuth professor emeritus at Stanford University was not able to generate/present The Annual Christmas Lectures. For this past year (today is January 01, 2023 – Happy New Year!) he generated Stanford Lecture: Don Knuth – Twintrees, Baxter Permutations, and Floor Plans (2022). When you read the title it is hard to imagine how the three topics could be connected. My suggestion is to watch the video in which the topics are presented. Towards the end of the video the relationships are discovered. Not only that, but a set of four C programs are provided so one may experiment with the concepts.
Some years ago I was employed by a fortune 100 company in the Twin Cities of Minneapolis and St. Paul. For lunch several of the team members used to go out to fast food places. There was a strip a few blocks from the office.
On our way back I would stop by the technical library in building 235. I used to read volumes from The Art of Computer Programming by Donald Knuth and magazines from the Association of Computer Machinery (ACM) and the Institute of Electrical and Electronics Engineers (IEEE). With time I purchased two copies of The Art of Computer Programming. During one move (change of jobs) I lost the first collection so I had to replace it.
The presentation by Donald Knuth is a bit longer than an hour. In general, I like to watch and experiment on the subject. I took notes and experimented for about four hours. That seems like a good estimate for me for courses, papers, and presentations.
Twin trees are defined as binary trees in which node k has a right child in exactly one of the trees for 1 <= k < n. and node k has a left child in exactly one of the trees for 1 < k <= n. I had never before heard of twin trees. If interested, watch the Youtube video.
The presentation then moved to cover the Baxter Permutation. Given a set of numbers there seems to be a relatively large number of permutations that are covered by the definition. So far not that interesting, but I knew that after the three topics were presented, there has to be a relationship.
The presentation moved to describe and give an example of a floorplan. If interested in additional information on Floorplan (microelectronics). The algorithm presented is used to rearrange a floorplan into equivalents and verify that they are equivalent.
At the end of this part of the presentation is when the relationship between the three subjects was described. Equivalent floorplans in ICs can be represented by twin binary trees. The order of the nodes can be checked to be equivalent if they represent Baxter permutations.
There is a lot of information and very good explanations of the three topics.
The algorithms presented were associated with the following:
o Eyal Ackerman, Gill Barequet and Ron Y Pinter 2006
o Yoo, Chen, Cheng, Graham 2003
o S Dulucq and O Guibert 1996
A set of computer programs were described and shown during the presentation:
Programs to Read
https://www-cs-faculty.stanford.edu/~knuth/programs.html
* FLOORPLAN-TO-TWINTREE
https://www-cs-faculty.stanford.edu/~knuth/programs/floorplan-to-twintree.w
* FLOORPLAN-TO-TWINTREE-TTFORM
https://www-cs-faculty.stanford.edu/~knuth/programs/floorplan-to-twintree-ttform.ch
* TWINTREE-TO-BAXTER
https://www-cs-faculty.stanford.edu/~knuth/programs/twintree-to-baxter.w
* BAXTER-TO-FLOORPLAN
https://www-cs-faculty.stanford.edu/~knuth/programs/baxter-to-floorplan.w
A trilogy of interesting bijections between floorplans, twintrees, and Baxter permutations (September 2021).
I wish I would have additional time to spend on the materials referenced in the presentation.
If interested in the topics presented by Don Knuth, I suggest watching the Youtube video.
Keep on reading and experimenting. It is the best way to learn.
John