# Communications of the ACM

BLOG@CACM

View as: Print Mobile App Share:

I have again been conducting interviews of candidates to a master program in computer science, software engineering, and leadership. A faculty member personally interviews all students applying to the program. Sometimes, that is me.

Some answers are not going to take the candidate very far. For example (I have witnessed all):

## #1 "It's quite complex."

Yes, sure. The question was: "What is the complexity of the Quicksort algorithm?"

## #2 "For me, a binary search tree is..."

I do not know where this is going, but an answer starting with "For me" is not promising. The question was "What is a binary search tree?". I am really sorry: the purpose of that question was to find out whether you know what a binary search tree (or anything other CS concept to be substituted here) is. If you do, it should be the same "for you" as it is for me -- and many other people.

## #3 Divide and conquer.

I think it goes back to Donald Knuth's epic Volume 3, Sorting and Searching, of The Art of Computer Programming -- or at least its easier elements, parrotted by less-formidable textbook creators. Like any good author, Knuth was looking for good metaphors, and he decided to explain recursive algorithms such as Mergesort or Quicksort by resorting to a phrase attributed first to Philip II of Macedon, and also used by Julius Caesar and Napoleon (thanks, Google and Wikipedia!). Probably Machiavelli too, at least in its spirit. The more usual form is actually "divide and rule." OK, as a metaphor to introduce recursive application of a strategy it is not bad, and no doubt it was impressive the first time (out of 3 billion or so by now) it was used. Now it has become such an overworn cliché that it makes me cringe every single time I hear it -- which is every single time I ask about, for example, Quicksort.

I am not even mentioning that if you have listened to Lamport (and my own immodest rendition of his ideas in Eiffel), you will know that recursion is in fact entirely extraneous to Quicksort. In practice, everyone teaches that Quicksort is an organically recursive algorithm, and we are testing what people learned, not what they should have learned. So, OK for recursion. But "divide and rule" means nothing at all! Every algorithm divides its data and tries to make something out of the result. (Think map-reduce.)

Don't try to impress me with big words. Tell me the principle of the algorithm, data structure, design pattern, or other concept and explain the practice that implements this principle. Then we can start talking.

Bertrand Meyer is a professor and Provost at the Constructor Institute (Schaffhausen, Switzerland) and chief technology officer of Eiffel Software (Goleta, CA).

No entries found