CS 138 Introduction to Data Abstraction and Implementation

Objectives

This course introduces software engineering students to elementary data structures, and to the functional programming paradigm.

Intended Audience

Software Engineering undergraduates who have taken SE 1A. It is assumed that students have experience programming in an imperative language such as C or C++.

Related Courses

Prerequisite: CS 137

Antirequisites: CS 116, 135, 136, 145, 146

Successor: CS 241.

Hardware and Software

Used in course:

  1. An integrated development environment (IDE) for C++ (such as xCode for Mac OS X).
  2. An IDE for Scheme (such as Dr. Scheme).

References

  1. Absolute C++, 6th edition, by Walter Savitch. Addison Wesley.
  2. How to Design Programs: An Introduction to Computing and Programming, by Mathias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi. MIT Press. This text is available free online at http://www.htdp.org/

    3. Schedule

    Three hours of lecture per week, plus a one-hour tutorial. Normally available in Winter only.

    Outline

    Introduction (3 hours)

    Operating system and Unix concepts, programming language concepts.

    Introduction to C++ concepts (3 hours)

    C++ basics, basic types, IO, use of simply library elements (string, vector).

    ADT and their implementations as linked structures (12 hours)

    The stack, queue, and priority and queue ADTS; the linked list, sorted linked list; Trees, binary trees, binary search trees; the C/C++ memory model: pointers vs references, stack vs freestore; implementing and travesing linked structures; recursion and stack frams; recursive vs iterative solution to ADTs; space and time complexity of solutions; simple testing and debugging strategies.

    Object-based computing (9 hours)

    Interface vs implementation; class definitions, instantiation, object construction and destruction; object vs pointers to objects; interface design and abstraction, responsibility allocation; the adapter design pattern.

    Introduction to object-oriented programming (9 hours)

    Introduction to inheritance and its implementation in C++; introduction to generics, type parameterization, and C++ templates; the template method design pattern; use of generic data containers and the Standard Template Library; design heuristic and strategies for object-oriented programming.