CS 138 | SCS | UW

CS 138 Introduction to Data Abstraction and Implementation

Objectives

This course introduces Software Engineering students to elementary data structures and their implementation, and to the object-oriented 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. The UNIX operating system, the Bash shell, and command-line tools such as the g++ compiler.

References

  1. Absolute C++, 6th edition, by Walter Savitch and Kenrick Mock. Pearson.

    2. 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.