These are projects that can be used with *Data Structures and Other
Objects Using C++* by Michael Main and Walter Savitch, published by the Addison
Wesley Publishing Company.

**Introduction to Classes**- The statistician class: Keeps track of various statistics about a sequence of numbers.

**Container Classes with Arrays**- Sequence class: Using a fixed-size array.
- The matrix class: Matrixes of double numbers up to 10x10.
- The matrix class with tensor: This version includes the Kronecker tensor product.
- Polynomial class: Using a fixed-size array (preliminary version). Some additional work on the polynomial is also available.

**Dynamic Arrays**- Sequence class: Using a dynamic array.
- The string class: A simple dynamic string class.
- The dynamic matrix class: Convert a matrix class to use a dynamic array so that it's no longer restricted to 10x10 matrices.
- A bag variant: The insert function returns a receipt for each entry.
- Polynomial class: Using a dynamic array.

**Linked Lists**- The string class: A simple string class with a linked list. This version is from scratch. Another version is a modification of the dynamic array version.
- Extending the linked list toolkit
- Polynomial class: Using a linked list.
- A CGI program: Using the polynomial class in a CGI program that displays on a web page.

**Templates and Generic Programming**- List template class.
- Sequence template class.
- Bag template class: With an internal iterator (preliminary version).
- Quantum pseudotelepathy: Modify the matrix class so that it is a template class that depends on the type of components in the matrix. Then use it in a program that verifies the correctness of a quantum computer program.
- Using the map class.
- A phone book data base: Using the map class.

**Stacks**-
**Queues**- A priority queue class: Implemented with a linked list.
- Traffic intersection simulation.

**Recursive Thinking**-
**Trees**- The bag class: Implemented with a binary search tree.
- Expression tree class: Includes a recursive function to evaluate an expression tree.
- Animal taxonomy: Modify the animal guessing game so that it saves the data file when it ends (and rereads that same file when it begins).

**Balanced Trees**- A priority queue class: Implemented with a heap.
- Set class: Implemented with a B-tree that uses arrays to store the data and child pointers.
- Set class: Again, implemented with a B-tree, but using vectors instead of arrays.
- A set class: Implemented with an external B-Tree.

**Searching**- A table class: Implemented with chained hashing.

**Sorting**-
**Inheritance**- The carnivore class.
- Implement a two-player strategy game: Derived from the abstract game class.
- Tictactwice: Derived from the abstract game class.

**Projects with the WinBGIm Graphics Library**- A flock of flying birds.
- Graphical blackjack game.
- A cd player.
- A clock: The background changes throughout the day.
- Conway's game of life.
- Graphical craps game.
- A 3D wire-frame cube. A more advanced version is also available.
- An old telephone.
- Modeling evolution.
- Eyes follow the mouse.
- Mandelbrot's fractal.
- Adds zooming to the fractal.
- A cd player.
- A remarkable pattern: Created by the rules of Langton's ant.
- Pegboard pinball.
- Drawing graphs.
- A first simple graphics assignment.
- Turtle graphics.
- Using a 3D graphics class.

**More Programming Projects (including CS1 material)**- Body mass index.
- A calendar for any month.
- Decoding secrete messages.
- First exposure to functions.
- Compare two investments.
- Verify ISBN numbers.
- Fox and goose populations.
- Lattice gas wind tunnel.
- How long to become a millionaire?
- Recognizing palindromes.
- A first simple assignment.
- Statistical computations: Using an array.
- Simple text processing: A first for-loop program.
- Who is the mole? Simple string processing.
- Complex text processing: Using the Penn corpus.
- Print a temperature conversion table.