I guess they know algorithms well, but...

The authors of Introduction to Algorithms (Cormen et al.) do not seem to  be much up on their software engineering. I suggest the foremost principle of software engineering is DRY: don't repeat yourself. Every time you repeat a bit of code, you double your maintenance worries.

These authors, while they are no doubt experts on algorithms, knowing far more than me on that topic, seem to pay little attention to the DRY principle. For instance, when they want to introduce students to a random quicksort, after having explained a basic quicksort, they write a whole new function that is identical to basic quicksort, except that it calls random_partition() instead of partition(). Shouldn't students be taught to just pass in a partition function to quicksort()?

Similarly, in dealing with heapsort, the authors suggest having max_heapify() and min_heapify() functions. Well, what about just writing heapify(), and passing it a comparison operator?

Yes, certainly these points are peripheral to studying the algorithms themselves. But in the process of teaching students basic algorithms, why in the world would we also want to each them crappy software engineering along the way?

4 comments:

  1. I wonder how many have ever found these to be useful. More commonly what is sought is a sorted index on a set of records, maintaining data associated with the sort key.

    ReplyDelete
    Replies
    1. How do you think the index gets sorted?!

      Delete
  2. I agree with you generally but I can see the argument for doing it their way in this case -- you don't necessarily want the overhead of introducing an API for heapifying and comparison functions when it doesn't clarify the core aspects of the algorithms they want to highlight.

    Though it would still be a good idea to make a note, in passing, about "hey, those functions are basically doing the same thing so in practice you'd want to generalize and DRY it up a bit".

    ReplyDelete
    Replies
    1. Yes, that may have been the right way to handle it.

      Delete