First Things First

What will best serve our students?

With the availability of the standard template library (STL) for C++, we believe that our students are best served by a CS-2 course that is significantly different from the traditional Pascal-era course.

A Continuum of Approaches

Since the adoption of STL in C++, there is a continuum of possible ways to teach CS-2. One endpoint of this continuum would seem to be a black box approach that emphasizes the use of the "off-the-shelf" data structures provided by STL without examining their implementation. The other endpoint of this continuum appears to be a no box approach that emphasizes the traditional implementation of data structures from scratch, without coverage of STL. (Such a course would be quite similar to the traditional Pascal-era course.)

We advocate a glass box approach, in which traditional data structures are the primary focus of CS-2, but we use and "peek under the hood" of their STL counterparts to study their implementation, and implement some data structures ourselves. Our position is thus one of the many "middle ground" positions between the two extreme endpoints.

Analysis

Our reasons for rejecting the "black box" and "no box" approaches in favor of our "glass box" approach are as follows:

• Computer science is at its heart a practical discipline that has little tolerance for inefficiency and wasted effort. We believe that this argues against a "no box" version of CS-2 in which students are required to "reinvent the wheel" extensively.
• The STL components are a part of C++, and must be taught somewhere in the computer science curriculum. We believe that the natural place to do so is in CS-2, which argues against the "no box" approach.
  • If the "no box" approach is taken, then teaching STL must be deferred to some later point in the curriculum. We are unaware of any subsequent course in the traditional curriculum that is more appropriate than CS-2 for providing coverage of STL.
  • If the "no box" approach is taken, students will be required to spend a significant amount of time "reinventing the wheel" in CS-2. We believe that when such CS-2 students hear from upperclassmen that they are wasting their time (as is inevitable), a "no box" CS-2 course will become extremely unpopular, with low student morale.
• A "black box" approach to CS-2 could use STL to teach students about the data structures without coverage of pointers. However, we believe that a working knowledge of pointers is still needed (to read and maintain legacy code), so that students would not be well-served by the "black box" approach. However, we also believe that the treatment of pointers that characterizes the traditional "no box" CS-2 course is outmoded.
  • Thanks to STL, virtually all linked data structures can either be created by instantiating STL templates, or built by composing STL components. But to really understand the STL component behaviors requires that students have a working knowledge of pointers. Similarly, to understand how a C++ array differs from an STL vector, and how a vector differs from a list, students must understand the underlying pointer-based implementations. These argue against the "black box" approach.

    To best serve our students, we believe they should implement at least one linked structure from scratch (e.g., a singly-linked list) in CS-2.

  • We like to teach inheritance and polymorphism early in CS-2, because it follows naturally in our CS-1 design methodology, and because it allows us to derive special purpose objects from STL components. C++ polymorphism requires the use of pointers or references, necessitating coverage of pointers early in our CS-2 course. This early coverage sets the stage for discussion of how STL components are implemented later in the course.
  • Most non-trivial STL operations involve the use of iterators. An early, simple treatment of pointers in CS-2 generalizes nicely to a discussion of iterators. A "peek beneath the hood" at iterator implementation reinforces the abstraction.
• Values can be stored in a vector, a list, a set, a map, ... How do students decide which component to use? While students in a "black box" approach can learn by rote the rules for proper use of STL components, we believe that students are better served by understanding the implementation differences of these objects, and the differing algorithmic complexities that result from those implementations. This argues against the "black box" approach.

  We believe that to "use" STL components properly requires that students be at least as knowledgeable about algorithm complexity as was typically the case in the traditional CS-2 course. STL thus shifts the treatment of algorithm complexity in CS-2 from an abstract, theoretical topic to an immensely practical, applied topic.

A Glass Box Approach: Data Structures

It should be apparent that if CS-2 is already a "full" course, then it is not feasible to cover all of the "new" STL-related topics and all of the "old" topics that are traditionally covered in CS-2. After careful analysis of what we were trying to accomplish with CS-2, we arrived at the syllabus below. At Calvin College, CS-2 receives 4 hours of credit, with three lecture hours and a two hour closed laboratory session each week.

Much of the treatment of specific topics is integrated throughout the course, using the "spiral" approach. For example, pointers are introduced early (motivated by the run-time flexibility of a vector), and subsequently used in studying polymorphism and the implementations of the various STL components. Similarly, algorithm complexity is introduced near the middle of the course (motivated by discussing the difference of inserting into a vector or list), and subsequently used to motivate hash tables, sets and maps.

A Glass Box Approach: Algorithms

To "make room" for the STL topics in CS-2, we have shifted much of the algorithm-specific material (e.g., sorting) to a new "CS-3" course titled Algorithms and Data Structures. This course applies our "glass box" approach to the study of algorithms, "looking under the hood" of the STL algorithms templates when applicable.

For course projects, our CS-3 course introduces additional data structures that are not provided by STL (e.g., graphs), and implements class templates for such objects, and implements algorithm templates by which they can be processed.

Other Position Papers