Putting the Science in Computer Science
Strange name you have, Computer Science. It evokes a sense that the scientific method is at work, that discoveries might be made by means of inductive reasoning based on collecting data from experiments designed to test a hypothesis. Yet academic CS often concerns itself with the kind of deductive proofs (and mathematical induction) more commonly associated with applied mathematics. Then in practice, most computer scientists (or whatever we call ourselves when we have CS degrees) engage something much closer to engineering.
The study of living things isn’t called “Biology Science,” but just Biology. And the study of matter is “Physics” not “Physical Science”. But I guess “Computation” sounded like it might be just the crappy version of “Mathematics” and a degree in “Computers” was a bit weak, so tacking on “Science” makes it more academic even if it doesn’t clarify anything. Regardless, I’ve always liked that, given a computer with an operating system and a programming language, you really can do something like laboratory science. It’s possible, with only a few preconceptions about what the computer is doing, to begin investigating the features of the language (and thus, the means of controlling the machine) via experimentation.
The ability for each student to independently explore an internally consistent world of computational expressions (and their resulting output) is what I think makes our field special and especially attractive to a certain kind of mind. A lot of particular power is available here. You don’t need any exotic equipment, it’s not dangerous to try random ideas, and you can answer a lot of your own questions through simple experiments. It’s also possible to get down to serious work pretty quickly. Last week, I had my students build a “stopwatch” in Java that times the execution of statements. The only thing I showed them was System.currentTimeMillis, which returns the current time in milliseconds. They built their classes around that call and some instance variables. Using these newly-minted tools, they then measured the execution time of various operations. (Did you know you can increment an integer variable over a billion times a second with a recent JVM on a contemporary processor?)
This sort of real-world performance isn’t tested by the College Board on the AP exam, but the searching and sorting algorithms are. These algorithms are a classic part of the computer science curriculum, and I think they’ve held that position through the dramatic increase in programming language abstraction for two reasons: 1. because the problems are easy to explain but 2. the best solutions are non-intuitive and implementation details can make a big difference. These are important realities for new programmers to experience. In my view, we’re not really bringing the point home unless our students actually implement the algorithms themselves based on a specification and then test the efficiency of their implementations. The simple Stopwatch object is not only a good programming exercise (since it requires meeting an API with minimal direction on how to get there) but is also the sort of tool that even an experienced professional programmer will turn to for diagnosing performance problems. In short, this is the real deal.
Once the stopwatch was built, I had them implement and time a linear search and binary search. The linear search turned out to be a great formative assessment that showed me which students were still struggling with for loops. (I think it’s down to two of them at this point.) I haven’t taught recursion formally yet, so I gave some hints about how to implement binary search iteratively. But all I really told them was that keeping track of the starting and ending indexes of the data under consideration would be necessary.
One of my students implemented binary search recursively and then decided to also do an iterative version so she could compare performance. Another student wrote a recursive version that copied a subset of the search data to pass to itself. He found its performance worse than even worst-case linear search and wrote a new recursive version that didn’t need to do any copying. These are the kinds of learning experiences that I think many undergrads don’t have because searching and sorting are often treated as solved problems to be viewed like curiosities in a case, or as canonical information that just needs an overview accompanied by animations that make the point so we can get on to the proofs.
But here’s a key point about the science in computer science: Science isn’t a spectator sport. At some point, you have to do the experiment to get the result. Of course, every teacher has to make decisions about how to allocate the given time to cover the topics we need to cover. I didn’t teach search and sorting this way last year. But based on what I see happening in my classroom this year, I can’t think of much else that gives this much bang for the buck. What other topics let you pack real-world performance testing tools and skills in with algorithmic reasoning, sensitivity to implementation details, and a fantastic set of formative assessment opportunities, all in the process of solving a problem you can explain to a layperson in under 2 minutes? I knew there must be a reason we kept search algorithms in the curriculum. Next week: sorting!