Contents

• Colophon
• Dedication
• Preface
  • Goals
  • Approach
  • Outline
  • Suggested Course Outline
  • Online Course Materials
• Introduction
  • What This Book Is About
  • Object-Oriented Design
    • Abstraction
    • Encapsulation
  • Object Hierarchies and Design Patterns
    • Containers
    • Iterators
    • Visitors
    • Adapters
    • Singletons
  • The Features of C++ You Need to Know
    • Variables
    • Parameter Passing
    • Pointers
    • Classes and Objects
    • Inheritance
    • Other Features
  • How This Book Is Organized
    • Models and Asymptotic Analysis
    • Foundational Data Structures
    • Abstract Data Types and the Class Hierarchy
    • Data Structures
    • Algorithms
• Algorithm Analysis
  • A Detailed Model of the Computer
    • The Basic Axioms
    • A Simple Example-Arithmetic Series Summation
    • Array Subscripting Operations
    • Another Example-Horner's Rule
    • Analyzing Recursive Functions
      • Solving Recurrence Relations-Repeated Substitution
    • Yet Another Example-Finding the Largest Element of an Array
    • Average Running Times
    • About Harmonic Numbers
    • Best-Case and Worst-Case Running Times
    • The Last Axiom
  • A Simplified Model of the Computer
    • An Example-Geometric Series Summation
    • About Arithmetic Series Summation
    • Example-Geometric Series Summation Again
    • About Geometric Series Summation
    • Example-Computing Powers
    • Example-Geometric Series Summation Yet Again
  • Exercises
  • Projects
• Asymptotic Notation
  • An Asymptotic Upper Bound-Big Oh
    • A Simple Example
    • Big Oh Fallacies and Pitfalls
    • Properties of Big Oh
    • About Polynomials
    • About Logarithms
    • Tight Big Oh Bounds
    • More Big Oh Fallacies and Pitfalls
    • Conventions for Writing Big Oh Expressions
  • An Asymptotic Lower Bound-Omega
    • A Simple Example
    • About Polynomials Again
  • More Notation-Theta and Little Oh
  • Asymptotic Analysis of Algorithms
    • Rules For Big Oh Analysis of Running Time
    • Example-Prefix Sums
    • Example-Fibonacci Numbers
    • Example-Bucket Sort
    • Reality Check
    • Checking Your Analysis
  • Exercises
  • Projects
• Foundational Data Structures
  • Dynamic Arrays
    • Default Constructor
    • Array Constructor
    • Copy Constructor
    • Destructor
    • Array Member Functions
    • Array Subscripting Operator
    • Resizing an Array
  • Singly-Linked Lists
    • An Implementation
    • List Elements
    • Default Constructor
    • Destructor and Purge Member Function
    • Accessors
    • First and Last Functions
    • Prepend
    • Append
    • Copy Constructor and Assignment Operator
    • Extract
    • InsertAfter and InsertBefore
  • Multi-Dimensional Arrays
    • Array Subscript Calculations
    • Two-Dimensional Array Implementation
    • Multi-Dimensional Subscripting in C++
    • Canonical Matrix Multiplication
  • Exercises
  • Projects
• Data Types and Abstraction
  • Abstract Data Types
  • Design Patterns
    • Class Hierarchy
    • Objects
      • Implementation
    • The NullObject Singleton Class
      • Implementation
    • Object Wrappers for the Built-In Types
      • Implementation
    • Containers
    • Visitors
      • The IsDone Member Function
      • Container Class Default Put Member Function
    • Iterators
    • The NullIterator Class
    • Direct vs. Indirect Containment
    • Ownership of Contained Objects
    • Associations
      • Implementation
    • Searchable Containers
  • Exercises
  • Projects
• Stacks, Queues and Deques
  • Stacks
    • Array Implementation
      • Member Variables
      • Constructor and Destructor
      • Push, Pop, and Top Member Functions
      • The Accept Member Function
      • Iterator
    • Linked List Implementation
      • Member Variables
      • Constructor and Destructor
      • Push, Pop, and Top Member Functions
      • The Accept Member Function
      • Iterator
    • Applications
      • Evaluating Postfix Expressions
      • Implementation
  • Queues
    • Array Implementation
      • Member Variables
      • Constructor and Destructor
      • Head, Enqueue, and Dequeue Member Functions
    • Linked List Implementation
      • Member Variables
      • Constructor and Destructor
      • Head, Enqueue and Dequeue Member Functions
    • Applications
      • Implementation
  • Deques
    • Array Implementation
      • Tail, EnqueueHead, and DequeueTail Member Functions
    • Linked List Implementation
      • Tail, EnqueueHead, and DequeueTail Member Functions
    • Doubly-Linked and Circular Lists
  • Exercises
  • Projects
• Ordered Lists and Sorted Lists
  • Ordered Lists
    • Array Implementation
      • Member Variables
      • Inserting and Accessing Items in a List
      • Finding Items in a List
      • Removing Items from a List
      • Positions of Items in a List
      • Finding the Position of an Item and Accessing by Position
      • Inserting an Item at an Arbitrary Position
      • Removing Arbitrary Items by Position
    • Linked List Implementation
      • Member Variables
      • Inserting and Accessing Items in a List
      • Finding Items in a List
      • Removing Items from a List
      • Positions of Items in a List
      • Finding the Position of an Item and Accessing by Position
      • Inserting an Item at an Arbitrary Position
      • Removing Arbitrary Items by Position
    • Performance Comparison: ListAsArray vs. ListAsLinkedList
    • Applications
  • Sorted Lists
    • Array Implementation
      • Inserting Items in a Sorted List
      • Locating Items in an Array-Binary Search
      • Finding Items in a Sorted List
      • Removing Items from a List
    • Linked List Implementation
      • Inserting Items in a Sorted List
      • Other Operations on Sorted Lists
    • Performance Comparison: SortedListAsArray vs. SortedListAsList
    • Applications
      • Implementation
      • Analysis
  • Exercises
  • Projects
• Hashing, Hash Tables and Scatter Tables
  • Hashing-The Basic Idea
    • Example
    • Keys and Hash Functions
      • Avoiding Collisions
      • Spreading Keys Evenly
      • Ease of Computation
  • Hashing Methods
    • Division Method
    • Middle Square Method
    • Multiplication Method
    • Fibonacci Hashing
  • Hash Function Implementations
    • Integral Keys
    • Floating-Point Keys
    • Character String Keys
    • Hashing Objects
    • Hashing Containers
    • Using Associations
  • Hash Tables
    • Separate Chaining
      • Implementation
      • Constructor and Destructor
      • Inserting and Removing Items
      • Finding an Item
    • Average Case Analysis
  • Scatter Tables
    • Chained Scatter Table
      • Implementation
      • Constructors and Destructor
      • Inserting and Finding an Item
      • Removing Items
      • Worst-Case Running Time
    • Average Case Analysis
  • Scatter Table using Open Addressing
    • Linear Probing
    • Quadratic Probing
    • Double Hashing
    • Implementation
      • Constructors and Destructor
      • Inserting Items
      • Finding Items
      • Removing Items
    • Average Case Analysis
  • Applications
  • Exercises
  • Projects
• Trees
  • Basics
    • Terminology
    • More Terminology
    • Alternate Representations for Trees
  • N-ary Trees
  • Binary Trees
  • Tree Traversals
    • Preorder Traversal
    • Postorder Traversal
    • Inorder Traversal
    • Breadth-First Traversal
  • Expression Trees
    • Infix Notation
    • Prefix Notation
    • Postfix Notation
  • Implementing Trees
    • Tree Traversals
      • Depth-First Traversal
      • Preorder, Inorder and Postorder Traversals
      • Breadth-First Traversal
      • Accept Member Function
    • Tree Iterators
      • Member Variables
      • Constructor and Reset Member Function
      • Operator Member Functions
    • General Trees
      • Member Variables
      • Member Functions
      • Constructor, Destructor, and Purge Member Function
      • Key and Subtree Member Functions
      • AttachSubtree and DetachSubtree Member Functions
    • N-ary Trees
      • Member Variables
      • Member Functions
      • Constructors
      • IsEmpty Member Function
      • Key, AttachKey and DetachKey Member Functions
      • Subtree, AttachSubtree and DetachSubtree Member Functions
    • Binary Trees
      • Member Variables
      • Constructors
      • Destructor and Purge Member Functions
    • Binary Tree Traversals
    • Comparing Trees
    • Applications
      • Implementation
  • Exercises
  • Projects
• Search Trees
  • Basics
    • M-Way Search Trees
    • Binary Search Trees
  • Searching a Search Tree
    • Searching an M-way Tree
    • Searching a Binary Tree
  • Average Case Analysis
    • Successful Search
    • Solving The Recurrence-Telescoping
    • Unsuccessful Search
    • Traversing a Search Tree
  • Implementing Search Trees
    • Binary Search Trees
      • Member Variables
      • Find Member Function
      • FindMin Member Function
    • Inserting Items in a Binary Search Tree
      • Insert and AttachKey Member Functions
    • Removing Items from a Binary Search Tree
      • Withdraw and DetachKey Member Functions
  • AVL Search Trees
    • Implementing AVL Trees
      • Constructor
      • Height, AdjustHeight and BalanceFactor Member Functions
    • Inserting Items into an AVL Tree
      • Balancing AVL Trees
      • Single Rotations
      • Double Rotations
      • Implementation
    • Removing Items from an AVL Tree
  • M-Way Search Trees
    • Implementing M-Way Search Trees
      • Implementation
      • Member Functions
      • Inorder Traversal
    • Finding Items in an M-Way Search Tree
      • Linear Search
      • Binary Search
    • Inserting Items into an M-Way Search Tree
    • Removing Items from an M-Way Search Tree
  • B-Trees
    • Implementing B-Trees
      • Member Variables
      • Constructors
      • Private Member Functions
    • Inserting Items into a B-Tree
      • Implementation
      • Running Time Analysis
    • Removing Items from a B-Tree
  • Applications
  • Exercises
  • Projects
• Heaps and Priority Queues
  • Basics
  • Binary Heaps
    • Complete Trees
      • Complete N-ary Trees
    • Implementation
      • Member Variables
      • Constructor, Destructor and Purge Member Functions
    • Putting Items into a Binary Heap
    • Removing Items from a Binary Heap
  • Leftist Heaps
    • Leftist Trees
    • Implementation
      • Member Variables
      • SwapContents Member Function
    • Merging Leftist Heaps
    • Putting Items into a Leftist Heap
    • Removing Items from a Leftist Heap
  • Binomial Queues
    • Binomial Trees
    • Binomial Queues
    • Implementation
      • Heap-Ordered Binomial Trees
      • Binomial Queues
      • Member Variables
      • AddTree and RemoveTree
      • FindMinTree and FindMin Member Functions
    • Merging Binomial Queues
    • Putting Items into a Binomial Queue
    • Removing an Item from a Binomial Queue
  • Applications
    • Discrete Event Simulation
    • Implementation
  • Exercises
  • Projects
• Sets, Multisets and Partitions
  • Basics
    • Implementing Sets
  • Array and Bit-Vector Sets
    • Basic Operations
    • Union, Intersection and Difference
    • Comparing Sets
    • Bit-Vector Sets
      • Basic Operations
      • Union, Intersection and Difference
  • Multisets
    • Array Implementation
      • Basic Operations
      • Union, Intersection and Difference
    • Linked List Implementation
      • Union
      • Intersection
  • Partitions
    • Representing Partitions
    • Implementing a Partition using a Forest
      • Implementation
      • Constructors and Destructor
      • Find and Join Member Functions
    • Collapsing Find
    • Union by Size
    • Union by Height or Rank
  • Applications
  • Exercises
  • Projects
• Dynamic Storage Allocation: The Other Kind of Heap
  • Basics
    • C++ Magic
      • Working with Multiple Storage Pools
    • The Heap
  • Singly Linked Free Storage
    • Implementation
      • Constructor and Destructor
      • Acquiring an Area
      • Releasing an Area
  • Doubly Linked Free Storage
    • Implementation
      • Constructor and Destructor
      • Releasing an Area
      • Acquiring an Area
  • Buddy System for Storage Management
    • Implementation
      • Constructor and Destructor
      • Acquiring an Area
      • Releasing an Area
  • Applications
    • Implementation
  • Exercises
  • Projects
• Algorithmic Patterns and Problem Solvers
  • Brute-Force and Greedy Algorithms
    • Example-Counting Change
      • Brute-Force Algorithm
      • Greedy Algorithm
    • Example-0/1 Knapsack Problem
  • Backtracking Algorithms
    • Example-Balancing Scales
    • Representing the Solution Space
    • Abstract Backtracking Solvers
      • Depth-First Solver
      • Breadth-First Solver
    • Branch-and-Bound Solvers
      • Depth-First, Branch-and-Bound Solver
    • Example-0/1 Knapsack Problem Again
  • Top-Down Algorithms: Divide-and-Conquer
    • Example-Binary Search
    • Example-Computing Fibonacci Numbers
    • Example-Merge Sorting
    • Running Time of Divide-and-Conquer Algorithms
      • Case 1 ( )
      • Case 2 ( )
      • Case 3 ( )
      • Summary
    • Example-Matrix Multiplication
  • Bottom-Up Algorithms: Dynamic
    Programming
    • Example-Generalized Fibonacci Numbers
    • Example-Computing Binomial Coefficients
    • Application: Typesetting Problem
      • Example
      • Implementation
  • Randomized Algorithms
    • Generating Random Numbers
      • The Minimal Standard Random Number Generator
      • Implementation
    • Random Variables
      • Implementation
    • Monte Carlo Methods
      • Example-Computing
    • Simulated Annealing
      • Example-Balancing Scales
  • Exercises
  • Projects
• Sorting Algorithms and Sorters
  • Basics
  • Sorting and Sorters
    • Sorter Class Hierarchy
  • Insertion Sorting
    • Straight Insertion Sort
      • Implementation
    • Average Running Time
    • Binary Insertion Sort
  • Exchange Sorting
    • Bubble Sort
    • Quicksort
      • Implementation
    • Running Time Analysis
      • Worst-Case Running Time
      • Best-Case Running Time
    • Average Running Time
    • Selecting the Pivot
  • Selection Sorting
    • Straight Selection Sorting
      • Implementation
    • Sorting with a Heap
      • Implementation
    • Building the Heap
      • Running Time Analysis
      • The Sorting Phase
  • Merge Sorting
    • Implementation
    • Merging
    • Two-Way Merge Sorting
    • Running Time Analysis
  • A Lower Bound on Sorting
  • Distribution Sorting
    • Bucket Sort
      • Implementation
    • Radix Sort
      • Implementation
  • Performance Data
  • Exercises
  • Projects
• Graphs and Graph Algorithms
  • Basics
    • Directed Graphs
    • Terminology
    • More Terminology
    • Directed Acyclic Graphs
    • Undirected Graphs
    • Terminology
    • Labeled Graphs
    • Representing Graphs
      • Adjacency Matrices
      • Sparse vs. Dense Graphs
      • Adjacency Lists
  • Implementing Graphs
    • Implementing Vertices
    • Implementing Edges
    • Abstract Graphs and Digraphs
      • Accessors and Mutators
      • Iterators
      • Graph Traversals
    • Implementing Undirected Graphs
      • Using Adjacency Matrices
      • Using Adjacency Lists
    • Edge-Weighted and Vertex-Weighted Graphs
    • Comparison of Graph Representations
      • Space Comparison
      • Time Comparison
  • Graph Traversals
    • Depth-First Traversal
      • Implementation
      • Running Time Analysis
    • Breadth-First Traversal
      • Implementation
      • Running Time Analysis
    • Topological Sort
      • Implementation
      • Running Time Analysis
    • Graph Traversal Applications:
      Testing for Cycles and Connectedness
      • Connectedness of an Undirected Graph
      • Connectedness of a Directed Graph
      • Testing for Cycles in a Directed Graph
  • Shortest-Path Algorithms
    • Single-Source Shortest Path
      • Dijkstra's Algorithm
      • Data Structures for Dijkstra's Algorithm
      • Implementation
      • Running Time Analysis
    • All-Pairs Source Shortest Path
      • Floyd's Algorithm
      • Implementation
      • Running Time Analysis
  • Minimum-Cost Spanning Trees
    • Constructing Spanning Trees
    • Minimum-Cost Spanning Trees
    • Prim's Algorithm
      • Implementation
    • Kruskal's Algorithm
      • Implementation
      • Running Time Analysis
  • Application: Critical Path Analysis
    • Implementation
  • Exercises
  • Projects
• C++ and Object-Oriented Programming
  • Variables, Pointers and References
    • Pointers Are Variables
      • Dereferencing Pointers
    • References are Not Variables
  • Parameter Passing
    • Pass By Value
    • Pass By Reference
      • The Trade-off
      • Constant Parameters
  • Objects and Classes
    • Member Variables and Member Functions
    • Constructors and Destructors
      • Default Constructor
      • Copy Constructor
      • The Copy Constructor, Parameter Passing and Function Return Values
      • Destructors
    • Accessors and Mutators
      • Mutators
      • Member Access Control
  • Inheritance and Polymorphism
    • Derivation and Inheritance
      • Derivation and Access Control
    • Polymorphism
      • Virtual Member Functions
      • Abstract Classes and Concrete Classes
      • Algorithmic Abstraction
    • Multiple Inheritance
    • Run-Time Type Information and Casts
  • Templates
  • Exceptions
• Class Hierarchy Diagrams
• Character Codes
• References
• Index

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.