Notes from Workshop on Future Directions of Data Structures.
U. Wolz, March 25, 1997

Disclaimer: the following is NOT intended to be a definitive summary of the activities of the workshop. It is heavily biased by my personal perspective. I would hope that it can be used as a starting point for a more objective report on the proceedings.

Summary of impressions (not in any particular order):

General Conclusions:
  1. The first two courses are about programming and computational problem solving and to some extent Software Engineering (w/o the managerial issues.)
  2. The courses addresses programming in the small and medium, leaving in the large for later. The object-oriented approach should be used as a basis for this. There was a fair amount of controversy over where some topic come in, CS 1 or CS 2. The focus seemed to be on where students should be at the end of CS 2. Note that many schools had a "CS 3" for programming in the large/software engineering as well as a "CS 7" for more theoretical algorithm analysis.
  3. Abstraction is key to the second course. Implied but never really discussed, the first course offers basic tools, the second course introduces notion of abstractions and their implementation. The question we kept asking was "but which abstractions should they learn, to what level of detail, and to what end."
  4. My concern was with the confusion between language driven curriculum and language in service of curriculum. I kept hearing "I've given up N, in order to cover M". N tended to be a concept (e.g. graphs) M tended to be language "feature" e.g. templates in C++. To be fair, at one point in our small group discussion we brought a C++ feature issue (deep vs. shallow copy) up to the conceptual level. However, in later discussion with the whole group this did not emerge as an obvious part of CS 2 content.
  5. The prevailing language at the conference seemed to be C++, not necessarily by choice. Although cogent arguments were made for using C++, the prevailing point was that this is the language students wanted/needed. Does this mean Java will supersede it? We asked this question, but didn't discuss it.
  6. As an extension of point 5, we COULD NOT get away from the language issue. People's own frustration at mastering C++ came out. Yet we continue to assume we will use this as an introductory language. Little discussion of Java as an alternative. I would have liked more discussion from Gore and the Reeks about Eiffel. They did quietly point out that the inheritance problems(which are SO ugly in C++) are irrelevant to Eiffel where inheritance is natural.
  7. At a number of places the WAY we teach was discussed rather than WHAT we teach. Mentorship, apprenticeship, practicum, close student, faculty contact, closed collaborative labs all came up. There seemed to be general agreement that these courses needed to be "non-lecture" based. Students learn by doing, not by listening.
  8. There was almost no discussion of continuity and a cohesive thread in the program, beyond the very vague term "abstraction." No one seemed to be particularly concerned with a collection of ideas (e.g. encapsulation, pointers, ADTs (although no real agreement on what these were). The question WHY are students doing this was either taken for granted, or lost in the focus on topics. I'm not sure which, but suspect the former. I think this one is critical to programs that want to attract women, assuming one buys into the problem of small isolated topics driving women away. We never really said that the reason we all like teaching CS 2 is that the idea of abstraction is "really cool." Many people admitted that this is a fun course to teach. But we never really said why.
  9. It was heartening to see that analysis was taken seriously, in the context of trade-offs between implementations. Formal analysis was viewed as not nearly as important as having intuitions about space and time complexity.
Conclusions for CS 2 at TCNJ:
  1. The object paradigm is important for both courses: encapsulation first, and inheritance (if done well) second. To do objects right in the second course we need to do it in the first. Our current approach is far to fragmented: too much time spent on learning C/C++ in the second course. Two languages (Java and then C++) would create a conceptual thread and still address the problem of a "favored language."
  2. We need to make a clear distinction between concept, use of concept and implementation of concept. We should teach students to the use of the black box, to know when to use the black box, and then later show them what is inside.
  3. Informal analysis is critical. Students should be well versed in doing intuitive analysis. This circles back to the trade-offs issue. In both CS 1 and CS 2 the ability to decide which tools to use under what circumstances is key. Discrete mathematics as a vehicle for aiding this analysis is essential. I think this is what we do differently: by closely articulating the three courses we specifically address how theory contributes to practice.

The following is a re-organization of my notes from the workshop.

Michael Mann

Focused on three areas. These kept recurring in later discussions:

  1. Teaching large classes with diverse backgrounds (I extrapolated this to mean nature of student/teacher interaction. His point was that he needed to find ways to learn what was going on in individual's heads.) He touched on:
  1. Language & PDE's, he asked to what degree do we focus on these.
  1. Fundamental Issues what is the content of the course?:
Jacob Gore

Presentation focused on the object paradigm and why you should use it. His point was that the paradigm should service the concepts. OOP for its own sake (e.g. worrying about templates) looses sight of the purpose of the course. My conclusion was that the problem is the bias of a heavily typed language like C++. In an untyped language like CLOS you don't run into these conceptual problems. In particular:

My comments on Mann/Gore presentations:

Are we creating ambiguities:

  1. Language considerations vs. concepts: pushing things into the curriculum because of the language
  2. Are CS 1 and CS 2 programming courses? bite the bullet they are. Period.
  3. Engineering vs. Science: what are we focusing on anyway. How to or why?

Other issues:

The following are my notes on the small group discussion. We focused on:

We have to teach programming, but low status, but important, but a learning vehicle.

We went around the room and asked: What ARE the postconditions for CS 2, what do we want students to come away with?

characterize
describe solution
implement
debug
(not going to get this elsewhere)

We then asked what to avoid:

Interesting Points from the whole group discussion:

The afternoon small group discussions were to focus on :

Our group, having been articulate in the morning was less productive with regard to the task at hand. We never did articulate what we thought should be in the curriculum. One important point for me was the discussion of deep vs. shallow copy. It is necessary to explain this to students if they are going to "build" objects in C++. But if you don't focus on the big picture (dynamic vs. static storage) then it is just an awkward piece of "gunk" for them. Although the concept is important, does it belong in CS 2? We never really answered that. This again returns to the them of language driving content or content driving content. Especially since the other groups didn't come up with this as a major item of CS 2, I believe it is an example of language driving content. Copy constructors are iky in C++. Period.

Results from afternoon small groups: other two groups:

These are my text-based transcriptions of the slides that were shown:

First Group:
  1. Goal is to develop an independent apprentice practitioner:
    design
    code
    test
    debug experiment
    group coordination
    documentation
  2. Degree to which Analysis is incorporated
    informal time/space
    making informed choices
    appreciation for design choice
  3. Need to distinguish interface from implementation
    read, understand, use spec. for:
    common container classes
    apply common storage techniques and relevant algorithms
  4. Abstractions
    Functional abstractions (black box)
    Data abstractions (encapsulation and info hiding)
  5. Intro to Programming in the Large
    use of libraries
    group work
Second group
  1. Programming considerations
    The following should be included in the curriculum:
      tree
      BST
      one other (e.g. expression)
      traversals
      binary search
      read/write/modify/write interfaces
      implement linked structures
      [linear?, nonlinear?]
      map/dictionary
      alternate implementation that differs in complexity
      recursion
      linear structure/ADT
      stack, queue, list
      (able to implement)
      sorts (fundamental algorithm)
      n^2, nlogn
      bigO
      average, worst case

    The following should fall outside the curriculum:

      balanced tree
      backtracking
      priority queues
      hashing

    My comments on these:

      ADT has well defined interface
      Which is an ADT and which is an implementation
      An assumption here is that algorithms are <= n squared.
      What about applications that are exponential or uncomputable?
      What are the basic operations? Find, merge sort organize
  2. Abstraction :
    Include:
      ADT
      encapsulation
      information hiding/access
      data orthogonal to structure [e.g. generic]
      iterative enhancement
      use provided components/data structure
      Exclude:
      project oriented (inheritance, polymorphism
      iterator
      information hiding [build]
  3. Controversies: no consensus within the group regarding place in the curriculum. (AKA Gunk?)
      component libraries e.g. STL, JGL
      design that students do
      group based programming
      build from scratch
      patterns, software architecture
      there are only 4 languages (Java, C++, Ada95, Eiffel)

 

Summary of the day:

There was remarkable consensus (at least from the outspoken members of the workshop) on the general goals of CS 2 (as articulated by our group in the morning), and in the specifics of content as presented by the other two groups in the afternoon. We even agreed on the "controversies" those things that we couldn't agree upon.) All in all it was a very productive and enlightening meeting.