I had a memorable time last weekend. My new Apple iMac came on a FedEx truck at about 9:30am. The publishing agreement for my textbook (second semester computer science) came about fifteen minutes later on a different FedEx truck. And then I turned 60 on Sunday. The first two were clearly exciting. (I am a new convert to the cult of Apple. My father was deeply observant, but I stuck with Unix/Linux, and what convinced me to convert was that I could get all the Mac features but still run X11 underneath and write, as I am now writing, in a standard Linux window with standard Linux tools. No need to dual boot)
I am scheduled to teach the second semester course in the undergraduate major next semester, using my pdf as the text. I started work on this book when I taught this course two years ago and wasn’t entirely happy with any of the books available. First of all, there is way too much material in the standard ACM/IEEE/ABET curriculum. It’s just not possible to teach all the material in the curriculum in one semester.
The approach I have tried to take in my book is that students in the first semester have become moderately capable of doing computing in a naive way. They should have mastered arrays and ArrayLists (we use Java in our first two courses as the programming language vehicle for teaching computer science and program design), linear search and lookup, and the organization of programs into perhaps three levels
of classes.
The computer can either be an object of study (if one is a hardware designer or a compiler writer) or a tool to be used for doing something useful. I assume that that there are far more students in the latter group than the former, especially when one is teaching courses that have students from other majors. For this majority of students who might use a computer to do something, the next steps after learning how to do things naively is to learn how to do things in a more sophisticated way, which would allow them to do bigger projects and run on more data.
Instead of linear search, then, binary search becomes the method of choice. More complexity and coding, yes, but more payoff if one has more searching to do. Instead of storing everything in an ArrayList, we use linked lists, stacks, queues, and such to provide more structure and allow for more efficient processing against the data.
And yes, there is some sophistication in the programming language that can be introduced. I view the entire notion of iterators as a way of eliminating the step that involves knowing what the underlying structure is. Instead of doing a “next” to get a node in a linked list, and then fetching the data in that node, we use the iterator to fetch the data directly. But again, this isn’t just a cool construct in the language that the compiler writers just had to do in order to show how clever they were; this is a feature that specifically eliminates one complication in naive programming and thus might reduce the number of bugs. As with everything, there is no free lunch; complexity in constructs requires complexity in program design and structure. But the complexity is sometimes necessary and must be mastered.
Or at least that’s what I am going to try to convince my students of next term.
Duncan Buell
CSTA Board of Directors
As I scanned this article I thought: The problem here is clearly the writer’s focus on the language and not the fundamentals. That Java provides a half dozen data-structures and patterns of access is neither good nor bad (assuming, of course, that the user needs all of this mechanism). Rather, the question regarding linear versus binary search more often centers around the category of object, meaning if we have an ordinal category (you call that an ordered “collection” in Java) then binary search is no harder than linear search and is log-time. If you have an unordered collection, then the price of ordering such a collection is O(n log n) (at best), and then you realize O(log n) time—but you’ve paid a price. Depending upon what you NEED to do with these data, the price might be worthwhile. You could also use this situation as a starting point on a discussion about kinds of orderings and assumptions commonly attributed to each.
Again, the focus on the language is pure distraction, and is the reason that a vast majority of citizens and policy-makers think that Computer Science is about a machine or a particular language when really it’s more useful than either.
Regards,
Tom R