Donald Knuth has been described as the Euclid of computer science. The first draft of his epic "The Art of Computer Programming" was completed as a 12-chapter manuscript in 1965. Fifty years later TAOCP is still an on-going project and Knuth has achieved many other things along the way. 

In the 1960 computers were very new - yes we know Babbage had the basic idea in Victorian times, but the realisation of the idea was a 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 than 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.

In stepped Donald Knuth who planned to take on the task of documenting the discipline of computing. Referred to the "father of the analysis of algorithms", he also has a wicked sense of humour.

Donald Ervin Knuth, born 10th January 1938

Donald Knuth was born in Milwaukee, Wisconsin, to the owner of a small printing business - something that would be reflected in his later interest in typesetting tools.

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 basketball 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 asked for!

Perhaps this could 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 Caltech immediately.

After receiving his PhD, Knuth joined Caltech's faculty as an associate professor. He moved to Stanford University  in 1968, the same year in which Volume 1 of TAOCP was published. As a Stanford professor, he introduced a variety of new courses into the curriculum, notably Concrete Mathematics but retired from teaching in 1993 to work full time on his book. He has remained affiliated with Stanford, however, and is currently Professor Emeritus there.

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. 

The Art of Computer Programming

Knuth was able to convince Addison Wesley that the book was a good idea and so he started, and by 1965 he had completed a draft of twelve chapters - 3000 hand written pages.

The first chapter was sent to Addison Wesley who estimated that the finished book would be 2000 printed pages, which by the standards of the time was unthinkable. Having often criticized books of approaching 1000 pages as being unreadable because of their weight and tendency to fall apart it is easy to sympathize with Addison Wesley's decision to convert it into a multi-part work.

So it was that the first volume of The Art of Computer Programming, subtitled Fundamental Algorithms and published in 1968, consisted of just the first two chapters of the manuscript on Basic concepts and Information Structures. It is this volume that is by far the best known. It was the only one available in paperback and usually the only one that students ever really look at.

The next volume, of what was then expected to be a seven-volume set, was Seminumerical Algorithms was published following year consisting of  a further two chapters on Random numbers and on Arithmetic. Two more chapters were combined to create the third volume, Sorting and Searching, which appeared in 1973 and tended to attract more attention perhaps because of the practical importance of the topic.

These first three volumes virtually created the subject of computer science overnight and led to Knuth being described as the Euclid of computer science, which gives you some idea of just how important the work is. Volumes 1-3 were first combined into a slip case in 1988.

<ASIN: 0321751043>

<ASIN: 0201558025>
<ASIN:0201038048> 

<ASIN:0201038129>