it up.^b This became the genesis of my main research work, which developed not to be working on compilers, but to be working on the analysis of algorithms. It dawned on me that this was just one of many algorithms that would be important, and each one would lead to a fascinating mathematical problem. This was easily a good lifetime source of rich problems to work on.

If you ask me what makes me most happy, number one would be somebody saying “I learned something from you.” Number two would be somebody saying “I used your software.”

at caltech he finds a mentor,
but can’t talk to him.

I went to Caltech because they had [strength] in combinatorics, although their computing system was incredibly arcane and terrible. Marshall Hall was my thesis advisor. He was a world-class mathematician, and for a long time had done pioneering work in combinatorics. He was my mentor. But it was a funny thing, because I was in such awe of him that when I was in the same room with him I could not think straight. I wouldn’t remember my name. I would write down what he was saying, and then I would go back to my office so that I could figure it out. We couldn’t do joint research together in the same room. We could do it back and forth.

He also was an extremely good advisor, in better ways than I later was with my students. He would keep track of me to make sure I was not slipping. When I was working with my own graduate students, I was pretty much in a mode where they would bug me instead of me bugging them. But he would actually write me notes and say, “Don, why don’t you do such and such?”

 

the research for his Ph.D. thesis takes an hour. I got a listing from a guy at Princeton who had just computed 32 solutions to a problem that I had been looking at for a homework problem in my combinatorics class. I was riding up on the

b “Notes on Open Addressing.” Unpublished memorandum, July 22, 1963; but see http://algo.inria.fr/AofA/ Research/ 11-97.ht ml

if you ask me what
makes me most
happy, number one
would be somebody
saying “i learned
something from you.”
number two would
be somebody saying
“i used your software.”

elevator with Olga Todd, one of our professors, and I said, “Mrs. Todd, I think I’m going to have a theorem in an hour. I am going to psyche out the rule that explains why there happen to be 32 of each kind.” Sure enough, an hour later I had seen how to get from each solution on the first page to the solution on the second page. I showed this to Marshall Hall. He said, “Don, that’s your thesis. Don’t worry about this block design with = 2 business. Write this up instead and get out of here.” So that became my thesis. And it is a good thing, because since then only one more design with = 2 has been discovered in the history of the world. I might still be working on my thesis if I had stuck to that problem. But I felt a little guilty that I had solved my Ph.D. problem in one hour, so I dressed it up with a few other chapters of stuff.

 

he’s never had trouble finding problems to work on. The way I work it’s a blessing and a curse that I don’t have difficulty thinking of questions. I have to actively suppress stimulation so that I’m not working on too many things at once. The hard thing for me is not to find a problem, but to find a good problem. One that will not just be isolated to something that happens to be true, but also will be something that will have spin-offs, so that once you’ve solved the problem, the techniques are going to apply to many other things.

he starts The Art of

Computer Programming.

A man from Addison-Wesley came to visit me and said “Don, we would like you to write a book about how to write compilers.” I thought about it and decided “Yes, I’ve got this book inside of me.” That day I sketched out—I still have that sheet of tablet paper— 12 chapters that I thought should be in such a book. I told my new wife, Jill, “I think I’m going to write a book.” Well, we had just four months of bliss, because the rest of our marriage has all been devoted to this book. We still have had happiness, but really, I wake up every morning and I still haven’t finished the book. So I try to organize the rest of my life around this, as one main unifying theme.

George Forsythe [founder of the Computer Science Department at Stanford] came down to southern California for a talk, and he said, “Come up to Stanford. How about joining our faculty?” I said “Oh no, I can’t do that. I just got married, and I’ve got to finish this book first. I think I’ll finish the book next year, and then I can come up [and] start thinking about the rest of my life. But I want to get my book done before my son is born.” Well, John is now 40-some years old and I’m not done with the book.

This is really the story of my life, because I hope to live long enough to finish it. But I may not because it’s turned out to be such a huge project.

1967 was a big year.

It was certainly a pivotal year in my life. You can see in retrospect why I think things were building up to a crisis, because I was just working at high pitch all the time. I was on the editorial board of Communications of the ACM and Journal of the ACM—working on their programming languages sections— and I took the editorial duties very seriously. I was a consultant to Burroughs on innovative machines. I was consumed with getting The Art of Computer Programming done. And I was a father and husband. I would start out every day saying “Well, what am I going to accomplish today?” Then I would stay up until I finished it.

It was time for me to make a career decision. The question was where should I spend the rest of my life?