a story lives forever
Sign in
Form submission failed!

Stay signed in

Recover your password?
Form submission failed!



I have read and accepted the Terms & Conditions.


Video URL



Family history


Why I chose analysis of algorithms as a subject
Donald Knuth Scientist
Comments (0) Please sign in or register to add comments

Speaking of analysis of algorithms quickly I should say that, you know, I named the subject and I like it but I didn't mention what...the thing that... that was sort of key in the beginning, why I thought that... that it would be rich enough to... to serve as a life's work. And the reason... and the reason is that... okay, when I was working on a compiler in 1962 I took a day and I... and I looked at an algorithm called hashing, more specifically hashing with... it's called linear probing... a certain kind of hashing. And I'd heard that some students in Princeton had... had looked at this algorithm and they couldn't figure out how fast it was going to run. And I had a few hours to kill so I took a look at it and I... and I got lucky and I saw... I saw how to analyze it and prove exactly how fast it was going to run and this changed my life. I thought... I... I said, wow, this was... this was lots of fun working on this problem, figuring... figuring it out and so... so it turned out to be a beautiful mathematical problem although it had come out of a... a totally practical computer science domain. And I knew that there... there were many other problems in the theory - what's called queueing theory - that are just special cases of certain kinds of algorithms that had... and already this was a buzz word - queueing theory - the... the study of... of the way queues behave. And that's just a special case of... of a certain kind of algorithm.  So if I... if I consider the entire class of all interesting algorithms then it had better... it's bound to be full of problems just as interesting as queuing and hashing were... which I knew that... that they were there. So that's why right at that point I said hmm, that wouldn't be bad for a life's... to spend a lifetime on it because the... because you have a huge number of... of problems, not only do they have beautiful mathematical structure that ties together, you know, hangs together in... in nice patterns, but also there are customers out there so that when you solve the problem the people say hey, thanks for solving the problem, Don. So... so it's a great field to... to embark in and it... and it has turned out to be the case.


Listeners: Dikran Karagueuzian


Tags: Princeton University

Duration: 2 minutes, 47 seconds

Date story recorded: April 2006

Date story went live: 24 January 2008