Donald Knuth's Christmas Tree Lecture
Written by Mike James   
Thursday, 25 December 2014

In a tradition that is in its 20th year, Donald Knuth presented his 2014 Christmas Tree lecture at Stanford University earlier this month. His topic, as always, is related to something new about trees he learned during the year - in this instance (3/2)-ary Trees.

Trees are important at this time of the year, at least in the parts of the world that celebrate Xmas. However for programmers trees are always important. They are the fundamental advanced data structure that while seeming simple have lots of surprising and remarkable properties.

 

knuth

 

Donald Knuth should be known to you but just in case - he invented the TeX computer typesetting system, is the author of the monumental work The Art of Computer Programming and many algorithms. He also has a strange sense of humour so look out for it when you watch the video.  

The notes to the lecture tell you pretty much what it is all about:

In previous lectures Professor Knuth has discussed binary trees, ternary trees, quaternary trees, etc., which are enumerated by the coefficients of important functions called generalized binomial series of order 2, 3, 4, etc. What happens when we consider generalized binomial series of order 3/2, or of other fractional orders? The answer is pretty amazing.

The lecture proper starts about 4 minutes in - and be warned it is over an hour long and it is difficult to follow if you don't know finite math as explained in Knuth's book Concrete Math. If you get a bit discouraged by the math at the start then try to keep going because it gets increasingly interesting and more oriented to computer science as it goes on: 

 

 

 

 

stanfordlogoforknuth

 

More Information

Computer Musings 

Related Articles

Donald Knuth and the Art of Programming       

Data structures - Trees

 

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

 

Banner


Microsoft Releases Dev Proxy 0.21
08/10/2024

Microsoft has released an update to Dev Proxy, its command-line API simulator. The updated version, v0.21, adds the ability to simulate authentication and authorization using API keys and OAuth2 among [ ... ]



Oracle Code Assist Now In Beta
19/09/2024

Oracle Code Assist is now available in beta. The coding assistant was first announced in May, when Oracle said it would be optimized for Java, SQL, and Oracle Cloud Infrastructure-based applicati [ ... ]


More News

 

kotlin book

 

Comments




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

 

<ASIN:0201558025>

<ASIN:0321751043>

 

Last Updated ( Thursday, 25 December 2014 )