Is computer science baseless?

Mar 31 2010 Published by under computer science, education

From the April Communications of the ACM, the Kode Vicious column is on The Data-Structure Canon.

The reader question is:

In most areas of science there are a few basic underlying laws that inform the rest of the study of a given subject. Physics, chemistry, and electrical engineering all have these basic equations. What are the basic equations in computer science? Or is computer science baseless?

In other words, what's the fundamental intellectual basis of computer science? Well, according to KV, it's data structures!

If there were any set of basics that I wanted to hammer into software engineers and programmers, it would be the basic data structures, their features and pitfalls. ...

The basic data structures are the array, list, tree, and hash table. That seems like a short list, and I'm sure some of the more experienced readers of this column are warming up their mail applications to write me nasty notes about how there are more basic data structures than just these four. To these people I say, "Go for it!"

What I find most interesting about this list is how many programmers take it for granted and how few of them understand the implications of using one data structure versus another. Try as I might, I cannot lay all the blame at the feet of the programmers using these data structures; a good deal of the blame has to go to their teachers and the legions of poorly written "how to program" books that emphasize how to use a data structure rather than the underlying implications of what happens when they are used. Abstraction is a fine thing-it makes understanding large systems easier--but it also can obscure important facts: in particular, the performance implications of certain choices.


Given the different complexities I've just mentioned, I think you'll see that these four data structures, which form the basis of most computer programs, are worth studying time and again. A good place to start is Knuth's The Art of Computer Programming, Volume 1, Chapter 2, which covers all of these subjects more seriously and in depth. When you're done reading all that he has to say, please write me, though I should be retired by then.

Interesting. Although he probably conflates computer science with programming a little too much for my taste, I'm probably mostly in agreement with KV's point of view. But I was wondering what all of you out there in Computer Science Land think?

23 responses so far