Course Description

This course introduces software engineering students to elementary data structures and their implementation. Software abstractions via elementary data structures and their implementation; encapsulation and modularity; class and interface definitions; object instantiation; recursion; elementary abstract data types, including sequences, stacks, queues, and trees; implementation using linked structures and arrays; vectors and strings; memory models; automatic vs. dynamic memory management.

Textbooks (All Optional):

Absolute C++, 6^th ed., by Savitch (Addison-Wesley)
(Any "good" introduction C++ should suffice.)

---

Lecture Content

Introduction (3 hours)
Operating system and Unix concepts, programming language concepts

Introduction to C++ concepts (3 hours)
C++ basics, basic types, IO
Use of simple 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 solutions 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
Objects 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 heuristics and strategies for object-oriented programming

Office Hours

Time	Room	Instructor
TBD	TBD	Prof. Mike Godfrey
TBD	MC 4065	Edward Shao (ISA)