Ronald W. Heiby College Career
Key Lessons from College
I attended Hope College in Holland, Michigan, where I majored in Computer Science. Although much of my time at Hope was not sufficiently appreciated for a number of years, there are two related "lessons" that have really stuck with me throughout my professional career. It is surprising how often they come up. Both came from the same assignment in the same course, taught by the department chair, Professor Herb Dershem.
"It doesn't matter how fast the sort is, if it doesn't put the elements into the right order."
We had been put into small groups, and each group was assigned to implement a handful of different sort algorithms. 20% of the grade for the assignment was to be determined by the relative speed of each type of sort among those produced by the groups. Professor Dershem had let it be known that the absolutely fastest known external files sort was the Polyphase Merge Sort. He also let it be known that said algorithm was fully described in Knuth's Art of Computer Programming, Volume 3: Sorting and Searching, available for perusal in his office.
Well, no one in our group particularly wanted to work on the external files sort, so I volunteered. I remember going to the office and reading through the pages that described the famously fast sorting algorithm. I remember thinking, "Huh?", and then "Maybe the one before this makes sense." This pair of thoughts continued through a seemingly endless set of external files sorting algorithms, until I got to the first, most basic external files sort algorithm. When I got there, I thought, "Aha! I understand how this one works. I'll implement this one, then come back later and figure out the complicated one."
I implemented the basic sort, tested it thoroughly, and got distracted by the need to spend time on other classes. I never went back and re-did the assignment using the Polyphase Merge sort. So, I had to turn in the basic algorithm implementation that I had.
When the grades were handed back, I was somewhat surprised to learn that I had received full points for the fastest external files sort. It seems that mine was the only one turned in that actually put the elements into the right order! Afterwards, each person from the other teams who had done the external files sort wanted to know how I had figured out the Polyphase Merge. The looks on their faces when they'd learned what I'd done was priceless. This leads us to the second "lesson".
"Get it working first, then make it as fast as it needs to be."
Concentrate on getting the thing right first. Then work out how to make it do the right thing faster. As it turned out, the simple, direct, understandable algorithm produced a simple, direct, understandable implementation. It produced an implementation that worked and, as it turned out, was fast enough to meet the performance goal. Those who concentrated on speed first forgot the first lesson.