Donald Knuth has been described as the Euclid of computer science. He began work on his epic "The Art of Computer Programming" in 1965 and it is still an on-going project. Volume 4A was published on 12 January, 2011 and there are plans for Volumes 4B, 4C, 4D, 5 and perhaps more.
Computers are still very new - yes I know Babbage had the basic idea in Victorian times, but the realisation of the idea is a comparatively recent event. Along with all the practical hardware and software that has had to be developed there was a theory to write.
Computer science is younger then the computer - logically it has to be! Yet it seems difficult to believe that such a large body of knowledge can spring from almost nowhere so fully formed. Back in the early days programmers, even academically oriented programmers, would rather get on with programming than bother to write up some new technique. They needn't have worried because Donald Knuth did it all for them! One of the most remarkable men in computing, and he has a wicked sense of humour.
Donald Ervin Knuth, born 10th January 1938
Donald Knuth's first encounter with computers, of a sort, was with his father's Remington Rand calculator. He played with numbers like most children would play with toys. Words didn't escape his attention, though. Playing with words came naturally as well but not poems - a simple graphical grammar.
You can tell what sort of kid Knuth was by the story of the Zeigler's giant bar. The makers ran a competition to see how many words could be made from the letters in "Zeigler's Giant Bar". Knuth stayed off school for two weeks and generated 4,500 words - 2500 more than the judges of the competition had found! Knuth won a sledge, a chocolate bar for his class and a TV for the school - but I'm sure the prizes didn't matter to him.
He already seems to have displayed the obsession for completeness that is a characteristic of many an academic.
In high school he was keen on physics and on music - he played the piano. In the end physics won and he enrolled in the Case Institute in 1956. His first article was published in Mad magazine - a strange American institution that if you have not seen is impossible to describe. The article was "The Potrzebie System of Weights and Measures" and it proposed a ludicrous system of units.
More important he met his first real computer, an IBM 650, when he took on a summer job. The 650 was at first a mystery but then someone explained how it worked and he was hooked. Stories of long nights cooped up with computers seems to be a recurrent event in the lives of all the computer creators!
The Zeigler's chocolate bar incident repeated itself in 1957 when the professor of a class in maths set an optional problem with the promised reward of an automatic A grade to anyone who completed it - guess who did.
When Knuth missed the bus for the marching band that he was a member of he found he had a Saturday with nothing much to do. He solved the problem in time to hand it in on the Monday. With the automatic grade A he uncharacteristically skipped the class. Knuth eventually abandoned physics. Like many a glasses wearing theoretician he discovered that the manual requirements of the experimental component of most physics courses were too much. He switched to maths.
At this point the story takes an almost Bill Gatesian twist. While at the Case Institute of Technology (1956-60) Knuth developed a program to manage the college baseball team - rating the players so that the coach could accurately choose the best players. When the college won the league championships Knuth had an early moment of fame on the Walter Cronkite Sunday news program.
IBM also made a short film, "The Electronic Coach" featuring Don Knuth and the IBM 650 which you can see below.
The next public venture was to write an Algol compiler for Burroughs. He charged only $5000 and later realised how much more he could have charged!
Perhaps this might have been the start of a commercial career that would have lead him to fame and fortune in a different area of computing but he was awarded his BSc in 1960 with such distinction that he was also awarded a Masters at the same time. He moved on to study for his doctorate at Cal Tech immediately.
An ambitious book project
In 1962 Addison Wesley suggested that Knuth write a book on compilers. He planned the book as a twelve chapter work and in typical academic fashion the first three chapters would be based on notes for a course.
After he received his doctorate he started to work harder on the book. He started the chapter on sorting and conceived of a book with a wider scope than simply compilers. No one had written down the then almost virgin subject and those few who had tried had made only patchy and incomplete attempts. Knuth's aim was to codify the theories, methods and algorithms in a complete fashion. In doing so he was bound to find the gaps that others had simply not seen. Only when you start to write down and more importantly classify the different methods of sorting something in to order do you begin to see that there are other possibilities.