Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Don Knuth: The analysis of algorithms
Don Knuth.YouTube,01:02:33,published onJan 30, 2017,stanfordonline,https://www.youtube.com/watch?v=jmcSzzN1gkc.Type:Video
Date Reviewed: May 8 2018

Don Knuth needs no introduction. Computer science labs around the world are decorated with posters of Professor Knuth, and many academics have on their bookshelves at least the first volume of The art of computer programming [1]. As a pioneer, he was instrumental in the definition of the whole concept of computer science as an independent discipline. This video attempts to capture something of those early days of the discipline and particularly the subdiscipline of analysis of algorithms, which he was working on first at Caltech and then, since 1969, at Stanford.

Don Knuth uses a fun and interesting conceit to set up the talk recorded here: we have Knuth in 2017 standing on the right of the stage, providing a commentary on Knuth in 1969 giving his inaugural seminar as he joined the Stanford faculty. A wig and sideburns provide an additional light touch for the start of the talk.

For me, one of the main lessons from watching this was Knuth’s perseverance with going through an example algorithm and its analysis on the chalkboard, in extreme detail. These days, we are used to PowerPoint talks, where a lot of details can pass by in the blink of an eye, or talks that are illustrated with minimalist overheads with one word or one phrase (in typical cool sans-serif fonts) or even TED-style talks where many concepts are thrown out at break-neck speed. In Knuth’s talk, we see him methodically showing how careful analysis of specific algorithms can give rise to general insights, maybe even that such detail is necessary to understand broad principles. This is old-school methodology, and it is quite inspiring to see him put calculation after calculation on the chalkboard to tease out patterns that can then provide insights.

Knuth uses the same example, of an algorithm for finding the maximum number in a list of numbers, to motivate the need for a new kind of mathematics, a mix of continuous and discrete mathematics, a theme that has been expanded in a very popular textbook by Knuth and his colleagues [2].

Some speakers would present concrete mathematics right at the start of the talk as gospel and then illustrate it; Knuth, on the other hand, invites talk attendees and video viewers to discover the theme themselves by carefully following his progress on the example. I am not sure this works very well in the video format, especially considering the limitations of showing a set of wide chalkboards through a limited-angle camera, but it is difficult not to be touched by Knuth’s enthusiasm and eagerness in re-creating the talk that marked the start of his brilliant career at Stanford.

There are other recorded talks by Knuth available online that might provide more general interest to his many fans in the computing community; this one is interesting particularly for his attempt at providing a portrait of the early days of the development of the very important subject area of the analysis of algorithms.

Reviewer:  Sara Kalvala Review #: CR146022 (1807-0386)
1) Knuth, D. E. The art of computer programming. Addison-Wesley, Redwood City, CA, 1997.
2) Graham, R. L.; Knuth, D. E.; Patashnik, O. Concrete mathematics: a foundation for computer science. Addison-Wesley, Boston, MA, 1994.
Bookmark and Share
  Reviewer Selected
Editor Recommended
Featured Reviewer
 
 
Analysis Of Algorithms And Problem Complexity (F.2 )
 
 
Analysis Of Algorithms (I.1.2 ... )
 
 
Introductory And Survey (A.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Analysis Of Algorithms And Problem Complexity": Date
Online deadline scheduling: multiple machines and randomization
Lee J.  Parallel algorithms and architectures (Proceedings of the fifteenth annual ACM symposium, San Diego, California, USA, Jun 7-9, 2003)19-23, 2003. Type: Proceedings
May 14 2004
Self-improving algorithms
Ailon N., Chazelle B., Comandur S., Liu D.  Discrete algorithms (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, Florida, Jan 22-26, 2006)261-270, 2006. Type: Proceedings
Aug 21 2006
A programmer’s companion to algorithm analysis
Leiss E., Chapman & Hall/CRC, 2006.  255, Type: Book (9781584886730)
May 9 2007
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy