Teaching a first course on data structures: a software engineering approach

ABSTRACT

We discuss our experience with integrating three key ideas of software engineering into our data structures course: formal specifications, information hiding, and bottom up programming. The idea of formal specifications is fostered by the introduction of a simple formal notation, which students use to describe their data structures and to validate their implementation. The idea of data abstraction is fostered by separating, in the very design of our course, the usage of data structures from their implementation. Finally the idea of bottom up programming is fostered by showing students how complex systems can be designed one layer at a time, where each layer refers exclusively to the layer immediately below it.

REFERENCES

• 1: Grady Booch, Software engineering with Ada, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1983
• 2: Peter J. Denning , D. E. Comer , David Gries , Michael C. Mulder , Allen Tucker , A. Joe Turner , Paul R. Young, Computing as a discipline, Communications of the ACM, v.32 n.1, p.9-23, Jan. 1989 [doi>10.1145/63238.63239]
• 3: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 4: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 5: Mili, A. et al. Towards Strnc~nred Specifying: Theory, Practice and Applications. Ellis Horwood T,td, 1989.
• 6: Harlan D. Mills, Princples of Computer Programming, Allyn & Bacon, Inc., Needham Heights, MA, 1987
• 7: Allen B. Tucker, Computing Curricula 1991, Communications of the ACM, v.34 n.6, p.68-84, June 1991 [doi>10.1145/103701.103710]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Computer science education

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues; Trees

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Algorithms, Languages