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 Knuth-Morris-Pratt algorithm


An international symposium on algorithms in the Soviet Union
Donald Knuth Scientist
Comments (0) Please sign in or register to add comments

I said that Analysis of Algorithms was... was what I wanted to call my life's work, this is... this is so, the field that I considered that... that most of what I'd done - including in writing The Art of Computer Programming - is to... is to find a quantitative way to... to say how good a computer method is... algorithms. So... so since I knew that algorithms was... was my great, you know... of all the things that I... that I enjoy and do, that this was somehow, had to be number one, I was delighted to learn that the word algorithm comes from Arabic, Al-Khwarizmi where Khwarizm is a... is a region of Uzbekistan, now, but at the time it was... it's the... it's the... there's a lake... I mean the Aral Sea used to be called Lake Khwarizm. And... and it's a part of the world that's pretty much forgotten.  It's usually to the east, north, south or west of whatever map you're looking at. If you look at a map of Iran it's north of there, if you look at a... at a map of... of Romania or something it's east of there, if you look at India or Afghanistan it's west, you know, south of Russia, it just doesn't appear, it's sort of a forgotten part of the world. But I... I found out that that's where the word algorithm comes from, Khwarizm. It means the... the person from the Khwarizm... the Khwarizm area or... actually there was a district of Baghdad where... which was the Khwarizm district where just... maybe, you know, like the Armenians lived in one place and... and they would call it the Armenian place, but this was the Khwarizm quarter of Baghdad. So... so I thought, okay, it would be interesting to go to Khwarizm sometime in my life and I looked in... I looked up... up in the atlas and, oh no, it's in the middle of the Soviet Union, how am I ever going to get there?  There's no roads going into it either showing from any, you know. So I mentioned this to my friend Andrei Ershov who was visiting from Russia, from the Soviet Academy of Sciences. Well, he wasn't my friend at the time, I didn't know him very well, but he was a friend of John McCarthy and I... and we were at a party at John McCarthy's house. And I said to him, 'You know, algorithms comes from... the word comes from this part of the world and it's in the Soviet Union.  We should celebrate this some time.  Wouldn't it be nice to have a... to have some kind of... of a pilgrimage where... where computer scientists of the world can go to Khwarizm and celebrate the, you know, the... the birth of this... of this subject?' And he said, 'Hey, that sounds like a great idea'. So he goes... he goes back home and he does all the work arranging it and getting the Russian Academy of Science to sponsor an international symposium on algorithms to... to last two weeks and to take place in... in the Khwarizm oblast, the... the district of Uzbekistan that... that everybody has forgotten. So not only did I get to go to Khwarizm but when I get off the plane I'm greeted by 200 children carrying flowers, and... and, you know, and interviewed on local television. And it was the first time anybody in the world had shown interest in their... in their part of the world, so... so we had, you know, the... the tremendous hospitality of the... of the people in... in the Mid East is... is amazing. In fact, you know, the hosts were so generous I said... I said jokingly well, how about, you know, providing me with a... not concubine... but anyway, you know. And, you know, I'm sure he would have believed me and done it, you know, unless I had really assured him that I wasn't joking. That I was joking. And we... and we could visit, right near where we were is a... is a kind of a museum city of Khiva where... which is really a... maybe where the author, Al-Khwarizmi, was... was from... well, I'm not sure but anyway it's a... it's a kind of a preserved city which shows all the great things of that culture. And... and we... and at this conference half of the people were Soviet Union and half of them were from the rest of the world and we could just meditate on the... the significance of algorithms, so it was another highlight of my... of my life I guess, to be... to be able to accomplish that little visit and see a part... that corner of the world. Amazingly we met children in this... in this village, many different nationalities, you know, blonde, blue-eyed kids, some of them with Korean ancestry.  We visited the cotton farms and picked cotton. We saw lots of, you know, I... I got myself a... a cap like the people wear in... in Khwarizm so that when I'm working on algorithms I can... I can be properly dressed.

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: The Art of Computer Programming, Arabic, Al-Khwarizmi, Khwarizm, Uzbekistan, Aral Sea, Lake Khwarizm, Soviet Union, Soviet Academy of Sciences, Russia, Russian Academy of Science, Khiva, Korean, Andrei Ershov, John McCarthy

Duration: 5 minutes, 42 seconds

Date story recorded: April 2006

Date story went live: 24 January 2008