What is the Future of the Data Structures Course?

For a viewpoint similar to what I write about here, see A New CS1 Objective: Building Intuition for Computational Science by Charles Van Loan from Cornell. His work was published in the 9/95 and 10/95 issues of Siam News. In his paper he argues that students in the first year should develop intuition about the five computational senses, ask your students:

Do you have eyes fo the geometric?
Do you have ears that can hear the "combinatoric explosion".
Do you have a taste for the random?
Do you have a nose for dimension?
Do you have a touch for what is finite, inexact, and approximate?

He also espouses the following system of equations

        Formalism First = Rigor Mortis
        Intuition First = Rigor's Mortise

My position for the second course(s) is similar, and calls for practical componenent that Charlie also mentions in his paper.

The courses that are CS2

We seem to be stuck with the appelation CS2. That's too bad, because many places spread the material that I'll talk about as essential to CS2 over two (and sometimes three courses). However, having a single name on which we can hang all these topics is convenient. In the rambling explanation that follows, there's no order to the topics I list as important. I'm sure I've left some important topics out and look forward to re-visiting this statement.

Object Oriented. The OO paradigm, both programming and design, is a much better tool than what we've traditionally called structured programming. Fred Brooks says so, and my intuition after living in OO-land for four years matches his statement.
However, OO programming and design is hard, and we can't expect students to master these, no matter what language we use, after two courses. We must build a foundation on which subsequent courses can build. The foundation should be grounded in the following ways:
- Apprentice Learning. Students should be shown elegant, well-crafted programs. These should use the right principles, be extensively commented, and show students how larger programs are built. We should not expect all programs to be written from scratch by students, but should supply frameworks and classes that facilitate writing more interesting and larger programs (see the next bullet).
- Application Driven. We can't use toy problems to illustrate all the principles we hope to cover. Programs should be computational in that the use of a computer makes them solvable in a reasonable time-frame. For example, we should stay away from palindrome checking (but palindrom generation is ok).
- Design Patterns. We should be using design patterns as discussed in the "Gang of Four" or GOF book (Gamma, Helm, Johnson, and Vlissides: Design Patterns: Elements of Reusable Object-Oriented Software. Not all the patterns there are appropriate in a second course, but other patterns not discussed there are. Briefly, a pattern is a solution to a problem in a context. However, that definition doesn't begin to do justice to how design patterns facilitate designing and building object oriented software.
Off-the shelf software. Given robust class libraries like STL (in C++) and JGL (in Java), it doesn't make sense to have students implement simple ADTs like stacks and queues. I'm not saying that we should use STL components; in fact I prefer to use implementations developed for use in student courses that are compatible at some level with STL, but safer and more intuitive.
The kinds of trade-offs inherent in using a linked list or a vector/array to implement a stack, or a ring-buffer/linked list to implement a queue are just not interesting compared to trade-offs like using balanced trees, hash-tables, or unsorted linked lists to implement a map/dictionary. We should discuss trade-offs that make a real difference in complexity.
Even with off-the-shelf software, our students do need to know how to implement linked lists/trees/... (or do they?). We must develop programming assigments that make home-grown lists better than an off-the-shelf list class. There is tension here in what we ask students to implement. For example, in C++ I think it's a mistake to talk about the built-in array type anywhere in the first two courses. However, I'm in favor of having students implement linked lists and trees. If Java is used, students are "stuck" using the built in array and vector classes.
Theory. We must help students develop an intuition about big-Oh (and, perhaps, theta/omega). I'm not concerned with the formal definition of big-Oh, I want to develop an understanding of what an upper-bound is and how big-Oh is used to compare complexities of algorithms and data structures. I expect students to understand how to solve recurrence relations by "expand, guess, check", but I'm happy if they recognize what I call the big four, know what canonical problems these apply to, and recogize when they're applicable:
- T(n) = T(n/2) + O(1), binary search
- T(n) = T(n-1) + O(n), selection sort
- T(n) = 2 T(n/2) + O(1), tree traversal
- T(n) = 2 T(n/2) + O(n), mergesort
I want students to have intuition about worst-case and average-case. I'd like students to know about different searching/sorting algorithms, but I'm not concerned that they can code these without a book, I want them to know the characteristics of a significant subset of what's found in most textbooks (as an aside, I want my students to hate Bubblesort).

What's Hot, What's Not

There's a lot to do in a second course. I don't think we can expect our students to be competent programmers, understand idioms and patterns, have a feel for complexity, know about algorithmic and data structure trade-offs (and whatever else we want to put into this course) in a single semester. We must decide what the important topics and principles are, and how these can be discussed in as language-neutral a way as possible. We should think about an advanced course I call software design in which we do larger projects, but also address some of the low-level constructs that may have been missed in a software-component course. Fitting the new CS2 courses into existing curricula isn't simple, but it's an adventure and it can be challenging and rewarding.

Owen L. Astrachan

Last modified: Fri Mar 21 17:10:47 EST