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.
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.
Our reasons for rejecting the "black box" and "no box" approaches in favor of our "glass box" approach are as follows:
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 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.
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.
Week | General Topic |
---|---|
1 | Review C++ and Classes |
2 | Introduction to Pointers, Indirection and Iterators |
3 | Pointers and vector Implementation |
4 | Introduction to Derivation and Inheritance |
5 | Introduction to Polymorphism |
6 | Introduction to Lists |
7 | list Implementation |
8 | Algorithm Analysis and Complexity |
9 | Introduction to Hashing |
10 | Implementing Hash Tables |
11 | Introduction to Trees |
12 | Sets and set Implementation |
13 | Dictionaries and map Implementation |
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.
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.