The Art of Programming

By Martin Heller

May 29, 2006

(The Art of Programming :  Page 1 of 1 )

Like many programmers of my generation, I never took a formal course in Computer Science. By the time Computer Science departments were forming, I was a grad student in Physics, writing programs to analyze my data. To get to that point as a programmer, I taught myself from manuals and books and other people's programs, and wrote hundreds of programs; to help our research succeed, other physicists took the time to mentor me one-on-one and bring my programming up to the next level. Much later, I taught programming in a Computer Science curriculum, but that's another story.

Knuth

One of the most useful sets of books I bought as a 20-something physicist/programmer in the 1970s was Donald Knuth's The Art of Computer Programming (Addison-Wesley). I worked through all three volumes on my own. Along with the work of Niklaus Wirth and Edgar Dijkstra, Knuth's writing helped me learn about algorithms and data structures and structured programming.

In my first job, I often found myself going back to Knuth. For example, when an embedded program in a calibration instrument my group was developing was taking too long to report its results, I sat down with the junior programmer who had done the initial development and we reviewed the code. When we got to his sorting algorithm and I realized that he'd coded a bubble sort to order a very long list of numbers, I just about went through the roof. Knuth's comment that "the bubble sort seems to have nothing to recommend it" was fresh in my mind, as was its unsuitability for use with large lists.

We dragged out Volume 3 of The Art of Computer Programming, coded up several of the sorting algorithms, and ran benchmarks against sample data from the instrument. A variation of Knuth's Algorithm Q (quicksort) with a random break point for picking sub-files to avoid the famous worst case (the standard quicksort behaves badly when the list is already in order) turned out to be as good as we could do, and when we put it into the instrument the problems we'd been having disappeared.

 Page 1 of 1