Kerstin Voigt, statement, CS2 workshop

	... on: "Should we teach our students how to understand and
	use class libraries rather than implementing elementary
	data structures form scratch?"
Position: "CS2 should NOT be taught without having students go through the process of implementing elementary data structures"

The above questions seems to imply that understanding of data structures comes from "use" (in preferably complex software artifacts) of data structures. It also seems to imply that having students go through the process of implementing data structures from scratch plays an only minor (if any) role in fostering understanding of the subject matter. I would disagree with this viewpoint, and, as unfashionable as it may sound, I still believe that much of the true understanding and motivation behind data structures is best conveyed by having students go through the effort of implementing those structures ("working under the hood", as I usually tell my students).

Obviously, we would like our students to be proficient in data structures, be able to benefit from the various libraries available, and have the ability to choose among data structures appropriately. However, I strongly believe that "good use" will only follow from "good understanding". And I am afraid, that teaching CS2 without implementation of elementary data structures, will fail to provide the kind of understanding that will pay off in the long run (past finals, past graduation, in the later years of a CS career).

Ultimately, the argument may hinge of what we mean by "understanding of data structures". I can see two views of understanding here. Understanding of type 1, the result of teaching CS2 via practical application of DS, without implementation from scratch, will ultimately consist of the knowledge of sets of rules that prescribe under what application specific circumstances to use what kind of data structures (if ... then use ...). Understanding of type 2 describes the kind of understanding that traditional teaching of CS2 (implementation based) aims at: knowledge of the internals of data structures, associated functionalities, and strengths and limitations derived from their composition. When deciding on how to teach CS2, we need come clear on the kind of understanding (1 or 2) we should be aiming at. What will pay off in the long run for a computer science graduate? What mode of teaching will provide the knowledge and skill that is necessary for the production of not merely functional software ("hey it's a large program, and it compiles!"), but quality software with favorable performance characteristics (due to, among other things, wisely chosen data structures).

Let me elaborate on both kinds of "understanding" in the below anecdotal and somewhat over-the-top manner. Imagine the following two (imaginary) computer science graduates, a couple of years into their CS working life. Both have had different CS2 experiences, one having acquired "Understanding1", the other "Understanding2".

Understanding1: "I know that their exist data structures DS1, ... DSk. For each DSi I know the associated functionalities, and the properties of an application that favor this particular structure. I pretty much had to memorize them for my CS2 final -- but it's been a while since then. I do not know where these properties come from, but I do not care since I am able to create running programs for large and complex applications. I exclusively use the C++ STL for my programming -- <vector> seems to do the job most of the time; seems to be broken, it doesn't do [i] anymore, and they could have done a better job with <stack> it does very little, e.g., it does not let you see what's on the bottom.

What do I remember from my CS2 class? Well, we got to write a lot of cool programs. None of this "compute the average of 5 numbers" kind of stuff. I got most of my projects done in time; it was like magic how some these components (I guess I should call them data structures or libraries) all fit together -- I am not sure how I did it sometimes. Whoever build those libraries, did a pretty good job indeed (aside from the bugs I just mentioned). I am only glad I didn't have to be the one writing all that boring code ..."

Understanding2: "I know about data structures DS1, ... DSk, I remember most of the basic operations they perform. I also know that given a problem, more than one data structure may "work", but usually one will be considered the more appropriate choice. I may have forgotten some of these "rules", and I may sometimes confuse the operations that a data structure is designed to perform (e.g., I recently tried to access [i] of a list -- pretty embarrassing, I know), but once I step back to think about the internals of a structure ("studied to oblivion in my data structures class -- it wasn't much fun then") I can usually figure out what kinds of operations I can expect, and whether the structure will be a good choice in my application. These days, I have given up on using my old class implementations from my CS2 class; I am a heavy user of the STL libraries.

What do I remember from my CS2 class? Well, it was kind of painful at times, and the projects (while they were hard at times) were not all that interesting. I was hoping to get a chance to write my automated lawn mover diagnostics tool, and it was kind of disappointing that that did not happen. I learned a lot more about OO though; having to use so much aggregation and inheritance finally cleared up some questions I had left over from CS1. The various ways of implementing stacks and queues helped with the understanding of encapsulation. And I did get to implement my dream system in "Software engineering". It's web-based now, and my grand-mother uses it all the time."

Whom to we want to have been our CS2 student?

Apart from the above, I am prepared to present some more concrete technical scenarios (actual personal experience) where knowledge of data structures "from the inside" (understanding of type 2) proved crucial in avoiding some potentially embarrassing and mistaken conclusion regarding the relative performances of several related programs.


Owen L. Astrachan
Last modified: Wed Sep 2 00:28:22 EDT 1998