Donald Ervin Knuth

The editors have asked me to note down a few of my personal memories of Andrei Ershov. Although Andrei and I lived on opposite sides of the globe, with about 180o degrees of longitude separating us, his life influenced my own in many positive ways.

These influences began when 1 was an undergraduate student at Case Institute of Technology. Andrei's book on his Programming Program for the BESM bad just appeared, and a bunch of us students were able to convince our Russian teacher to include it as one the two texts for our course on un derstanding scientific Russian. This was an excellent experience for us because many of the technical words for computer terms were not in any of our dictionaries, nor had our teacher ever seen them before! (The English translation by Nadler had not yet appeared.) We got a feeling that we were seeing the «real» Russian language as actually used in science; this was much more exciting to us than the other text, which was about Sputnik and space exploration but at a very simple level.

Besides learning a bit of Russian from that book, I also learned interesting algorithms for compiler optimization. Indeed, Andrei's early work, which initiated this important subfield of computer science, is still of in terest today. His method of exposition also turned out to be significant: The appealing flowchart illustrations in his book were a major influence on the way I later decided to illustrate program flow in my paper «Computer-drawn flow charts» [Communications of the ACM 6 (September. 1963), 555 ― 563], and in my subsequent series of books on The Art of Computer Programming.

My first personal encounter with Andrei was at an IFIP Working Group meeting when a successor to Algol 60 was being planned. By this time I had learned that Andrei had been an independent co-discoverer (with Gene Amdahl) of «hashing with linear probing» — an important algorithm that was a key turning point in my life because it led me to the field of algorithmic analysis. (See the footnote on page 529 of my book Sorting and Searching; this footnote appears on page 628 of the Russian translation.) And I had heard exciting rumors about new techniques incorporated in Andrei's Alpha language project. So I was excited to meet him in person and to learn that he spoke English fluently. We spent about two hours talking about compilers and languages, while he was using the Xerox machine to copy numerous documents at that meeting.

Eventually I was able to see him more frequently, because he regularly came to see John McCarthy at Stanford University. During one of those visits a seed was planted for one of the most memorable events of my life, the conference on Algorithms in Modern Mathematics and Computer Science held in Urgench, 1979. That conference — a scientific pilgrimage to Khowarizm, the birthplace of «algorithm» — was a dream come true for me. Although Andrei and I were officially listed as co-chairmen of that meet­ing, the truth is that Andrei took care of 99 % of the details, while I was able to relax and enjoy the proceedings and to learn important things from, the many people I met there. Such an experience is a once-in-a-lifetime thing, and I hope it will be possible for many other computer scientists to participate in a similar event if someone else is inspired to follow Andrei's example. During that week I got to know him much better than ever before, and T was especially struck by the brilliant way he filled numerous roles as conference leader, organizer, philosopher, speaker, translator, and editor.

I have many other memories — including especially the night in 1983 when my wife and I took Andrei to an American square-dance party and he was doing the Virginia Reel and «do si do» — but the above should suffice to explain way Andrei has had such a special significance to me personal­ly.

On his last visit to Stanford I learned of the great work he undertook during the final years of his life, a revolutionary improvement in computer science education for millions of students; this has justly been acclaimed throughout the world. We are all sad that Andrei's life was destined to end so prematurely, yet we are pleased to celebrate the many things he accomplished, and we know that the fruits of his life will continue to nourish the next generations of computer scientists everywhere.

Knuth D.E., Prof.

© 2008-2022 IIS SB RAS