a story lives forever
Sign in
Form submission failed!

Stay signed in

Recover your password?
Form submission failed!

Web of Stories Ltd would like to keep you informed about our products and services.

Please tick here if you would like us to keep you informed about our products and services.

I have read and accepted the Terms & Conditions.

Please note: Your email and any private information provided at registration will not be passed on to other individuals or organisations without your specific approval.

Video URL

You must be registered to use this feature. Sign in or register.


The Art of Computer Programming: underestimating the size of the book


A new field: analysis of algorithms
Donald Knuth Scientist
Comments (0) Please sign in or register to add comments

In the Fall of… of '67 there was a conference in Santa Barbara of… of mathematicians, and… and I, that's… so… I remember meeting, I think also that… wasn't that the year when there was a conference… conference in Chapel Hill in the Spring too of mathematicians? So, I… I was meeting a lot of people that… that stimulated me and we… and we had problems… interesting problems to talk about between each other, but when I got to the… to the conference at Santa Barbara, I realized that this was going to be my only chance to do research, so I sat out the conference. I didn't go to any of the lectures. I just sat on the beach and wrote my paper about attribute grammars at that conference. But I went to the meals, and I… I particularly remember somebody at that conference asking me what do I do, and I was just deciding, you know, I'm going… I’m going to become a computer scientist instead… instead of being in the math department. And so I said, ‘Well, I'm going to… I think I'm going to be a computer scientist’. And so he said, ‘Well what, are you a numerical analyst?’ And I said, ‘No, not really’.  So he… he says, ‘Ah, artificial intelligence’.  And I said, ‘No… not artificial intelligence either’. Then he said, ‘Well, then you must be in programming languages’, and in other words, compiler is what I had been asked to write a book about.  And… and in fact, at that time computer science was considered to consist of three things, numerical analysis plus artificial intelligence plus programming languages.

And… and Stanford's department also was sort of organized along those three lines. There were three qualifying exams and… and things like that. But I said, ‘Well, you know, I've done a lot of research in programming languages, and I've been editor of the programming language departments of journals, but… I… but my main interest is different’. And so I realized I didn't have a name for… for what my main interest was. And what is… what was my main interest? Well, see, as I'm… by this time, I'd… I’d written 3000 pages of The Art of Computer Programming and typed part of it, and… and published, and… and almost ready to publish, you know, reading the galley proofs or part of it. And… and it turned out that what I… what I found was that we wanted the mathematical basis for… for understanding the quality of… of computer methods. You wanted to know how good a method was, whether it's twice as good as another one or whether, you… you know, some quantity of things, you know, not just qualitative of, yes, better, but how much better, some… some way to… to add quantity to this. And so I… so I used that as the… as the underlying unifying theme of my books, is to find these quantitative, descript… ways of… of judging the merits of a computer method.  And… but I didn't have a name for it, and… and at this conference at Santa Barbara I realized that if… if I'm going to… if I have to explain to somebody else what is… what is my field, I'm going to have to have a name for the field.  So I… so I made up a name for the field. I decided to call it analysis of algorithms.  And I figured, okay, you know, I'm writing a book. I could… I could use that to explain what an analysis of an algorithm is. I… I talked to my publisher and I said, let's change the title of my book. Instead of calling it Art of Computer Programming, let's call it The Analysis of Algorithms.

Well, that didn't sell with their… with their focus group, but… but I decided anyway that would be… that would really be my career, to be… to focus mostly on the analysis of algorithms, meaning the… the quantitative study of how good an… an algorithm or computer method is. And I used that as… then when I was asked to give an international… a lecture at the International Congress of Computer… of… of what's it called, Information Processing Societies in… in 1971. My title was the Analysis of Algorithms, and I also was asked to speak at a mathematical… International Mathematical Conference in… in 1970 in… in France, and my title there was Mathematical Analysis of Algorithms. So, I was trying to promote this term as a… as a buzzword so that somebody… so that somebody would understand what it is that I do, or that I like… that I hope to do. And… and I'm glad to say that after… after 10 years or so… I mean in the late '70s, it started to show up as a… as a category in the… in the reviewing journals and there were books coming out called Analysis of Algorithms. In fact, even though I, you know, my publishers didn't like that title, there's… there are quite a few books now that… that have that title in them. And… and so, but I got to name the… the area that… that I work in.  And… but if anybody asked me what does it really mean, I would just say, well, it means whatever I'm interested in, you know, so I could change it for… for the first few years to… to suit myself.

Born in 1938, American computing pioneer Donald Knuth is known for his greatly influential multi-volume work, 'The Art of Computer Programming', his novel 'Surreal Numbers', his invention of TeX and METAFONT electronic publishing tools and his quirky sense of humor.

Listeners: Dikran Karagueuzian

Trained as a journalist, Dikran Karagueuzian is the director of CSLI Publications, publisher of seven books by Donald Knuth. He has known Knuth since the late seventies when Knuth was developing TeX and Metafont, the typesetting and type designing computer programs, respectively.

Tags: Santa Barbara, Chapel Hill, Stanford University, The Art of Computer Programming, France

Duration: 5 minutes, 44 seconds

Date story recorded: April 2006

Date story went live: 24 January 2008