Programming Projects Index

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

1. The statistician class: Keeps track of various statistics about a sequence of numbers.

Container Classes with Arrays

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

Dynamic Arrays

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

Linked Lists

1. 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.
2. Extending the linked list toolkit
3. Polynomial class: Using a linked list.
4. A CGI program: Using the polynomial class in a CGI program that displays on a web page.

Templates and Generic Programming

1. List template class.
2. Sequence template class.
3. Bag template class: With an internal iterator (preliminary version).
4. 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.
5. Using the map class.
6. A phone book data base: Using the map class.

Stacks

1. A calculator program.
2. Evaluate postfix expressions.

Queues

1. A priority queue class: Implemented with a linked list.
2. Traffic intersection simulation.

Recursive Thinking

1. Five recursive functions.
2. Generate a 3D Fractal.

Trees

1. The bag class: Implemented with a binary search tree.
2. Expression tree class: Includes a recursive function to evaluate an expression tree.
3. 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

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

Searching

1. A table class: Implemented with chained hashing.

Sorting

1. Quicksort.
2. Advanced Generic Quicksort.
3. Faster Quicksort.
4. Testing Four Sort Methods.

Inheritance

1. The carnivore class.
2. Implement a two-player strategy game: Derived from the abstract game class.
3. Tictactwice: Derived from the abstract game class.

Projects with the WinBGIm Graphics Library

1. A flock of flying birds.
2. Graphical blackjack game.
3. A cd player.
4. A clock: The background changes throughout the day.
5. Conway's game of life.
6. Graphical craps game.
7. A 3D wire-frame cube. A more advanced version is also available.
8. An old telephone.
9. Modeling evolution.
10. Eyes follow the mouse.
11. Mandelbrot's fractal.
12. Adds zooming to the fractal.
13. A cd player.
14. A remarkable pattern: Created by the rules of Langton's ant.
15. Pegboard pinball.
16. Drawing graphs.
17. A first simple graphics assignment.
18. Turtle graphics.
19. Using a 3D graphics class.

More Programming Projects (including CS1 material)

1. Body mass index.
2. A calendar for any month.
3. Decoding secrete messages.
4. First exposure to functions.
5. Compare two investments.
6. Verify ISBN numbers.
7. Fox and goose populations.
8. Lattice gas wind tunnel.
9. How long to become a millionaire?
10. Recognizing palindromes.
11. A first simple assignment.
12. Statistical computations: Using an array.
13. Simple text processing: A first for-loop program.
14. Who is the mole? Simple string processing.
15. Complex text processing: Using the Penn corpus.
16. Print a temperature conversion table.