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
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
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
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?