Teaching Data Structures (in CS 2 and CS 7)

Assumptions | Our CS 2 Course | Data Structures in CS 2 | Data Structures in CS 7 | Why Ada

Assumptions

To some extent our CS 2 course is shaped by limitation we face with respect to the CS 1 course. Although the CS 1 course is entitled Computer Science I, in fact it is a first course in a programming language. There are two reasons for this, First, the course is also a service course for students in several majors, including mathematics, physics, and chemistry. Second, our experience has been that very few students enter this course with good programming or software development experiences. When they do, we allow them to bypass the CS 1 course and enter the CS 2 course. At most there are only one or two students a year who are capable of doing this. The fact that we use two different languages in CS 1 and CS 2 allows students who bypass CS 1 to come into CS 2 without being placed at a disadvantage.

The CS 2 Course

Although the CS 2 course has the official title Computer Science II, I tell my students that a better title for the course is An Introduction to the Computing Sciences Through Software Engineering. As such the flavor of the course is one of having the students experience and learn good software development skills. As you might expect, the course covers a great number of topics. However, the course is a four credit course, while all other computing courses are three credit courses. We felt it was necessary to do this because of our earlier assumption about the CS 1 course and the desire that this course be a strong course.

A major theme that is started early in the course is software reuse, libraries, and ADTs. All software development assignments require that students either use existing packages that we make available, or construct and properly package their software. Although their is no closed lab associated with this course, there are weekly laboratory assignments. Most labs are constructed to be done by a student in about an hour and a half to two hours. Students may work in groups while performing the labs. Each lab assignment has a particular theme or focus. Students are usually provided with a partial piece of software and the lab requires that they complete a piece of code that focuses on an item that had been discussed in class during the previous week.

A unique feature of all programming projects is that students must submit personal logs with their labs. As the course progresses we take a few lectures to discuss these logs and make them more elaborate. With these logs students are being introduced to Humphrey's Personal Software Process (PSP, check out the SEI web site for information), a software development concept that has come out of the SEI. We use these logs to help students improve the way they develop software. Logs are also used to report on sources used by students while developing software (who do they work with, what references do they use, etc.). Our experiences with these logs has been very positive and we hope to report on it soon.

Data Structures in CS 2

From a data structures point of view there are four themes that are covered in the CS 2 course:
  1. Constructing a strong foundation in the use of static data structures.
  2. Introducing the logical linear structures, with an emphasis on stacks, queues, lists (2 paradigms).
  3. Introduction to non-linear data structures, emphasizing digraphs and tress (binary and n-ary).
  4. Object Technology, not just OOP. That is, we see OO as something that begins with software analysis and design long before we get concerned with programming languages features that support object technology.
The first two themes are handled in the first half of the course. The second two themes are handles in the second half of the course. We take the notion of abstraction to the limit. Students are provided with ADTs for stacks, queues and the two list paradigms. When discuss at length their specifications and applications of these structures. We do not discuss implementations at this time. In fact, we let them know that there are a great variety of implementational issues and tell them they make up the bulk of the CS 7 course.

We also present two list paradigms, a positional paradigms and a recursive paradigm, each supported by its own package. We make use of the two paradigms to assist students in gaining a better understanding of recursive programming by seeing and constructing software based on each paradigm with several parallel assignments (do it once with the positional list paradigm, do it again with the recursive paradigm). Once they go through these parallel exercises, students appear to have an easier time with trees. In fact, we use to present two tree paradigms (positional and recursive) until about three years ago when it became evident to us that the students made the transition to thinking recursively after gaining a better understanding of recursion through the list exercises.

In the CS 2 course they are introduced to the four aspects of data structures:

  1. Abstraction (specifications): Separating a concept from its potentially many representations.
  2. Encapsulation: This issue is missing from practically every book discussing data structures at the CS 2 or CS 7 level. It is the cause of many problems in data structures. In C++ it is the problem of addressing good use of public, private, and protected. In Ada it is addressing the differences between private, limited private, controlled, and limited controlled.
  3. Representation: The traditional material in CS 7 texts.
  4. Measurement: Learning to appreciate the trade-offs between various encapsulations and representations and making safe, efficient software decisions.
Encapsulation is introduced by presenting students with a variety of packaging of each ADT. The purpose of this exercise acquaint students with the issues of initializing ,assigning, and finalizing objects and how certain encapsulations must to associated to certain representations. This material also introduces them to the issues software developers must address when they package in order to maintain an interface that is safe for both the package and the client.

I find the recent emphasis in C++ on the STL most encouraging. Our students have had available a standard template (generic) library since 1991. Our experience with the stability that comes with the use of a standard generic library has been very positive. It provides a basic framework for many student projects in other courses.

Data Structures in CS 7

CS 2 emphasized the data structure ADTS with a hint of the encapsulation, representation, and measurement issues. The CS 7 completes the data structure education with a strong emphasis on the last three issues, encapsulation, representation, and measurement. We use Data Structures: An Object Oriented Approach Using Ada 95, which I recently published with Springer Verlag (ISBN 0-387-94834-1).

Why Use Ada?

We have approached the development of our core courses with the idea that concepts are more important than programming languages. As a result, our core courses have not been influenced by market forces. Our approach has been to select a programming language that allows us to emphasize concepts. At best the programming language should assist in supporting those concepts. At worst, the programming language should not interfere with the presentation of concepts. We chose Ada in 1989 for precisely those reasons. The new Ada 1995 standard has reinforced that choice. With Ada(95) there are free high quality compiler for most of the popular operating systems. Many of our students have their own systems and many commuters have Internet access. By using Ada, we are guaranteed that software written on any of a great variety of systems (Suns, Win 3.11, Min 95/NT, Macs) can be moved, recompiled, and expected to run on any other system.

The emphasis with Ada is correct compilation. The fundamental difference between Ada and other popular programming language for beginning students is very profound. With Ada, they spend more time getting a correct compile and less time with a debugger. We believe this places the proper emphasis on analysis and design. In fact, I do not teach my students how to use a debugger.

If you have not used Ada with one of the current GNAT Ada(95) compiler, try it out. You will be pleasantly surprised.