One project option is finishing our search tree problem!
data structures > final project specs

Data Structures final project specs

We often learn to code best by building a fully-baked software tool that demands correct implementation of specifications. This page outlines options for your final project in CIT-244: Data Structures


Project tracking Google Sheet
Option 1: Search tree problem solving
Option 2: Data structure-based tool model
Option 3: Priority queue implementation
Universal deliverables

bookProject tracker google sheet

Make and regularly update your record in our project tracker

tracker link

arrow_upward top

bookOption 1: Search tree problem solving


Solve the Interstellar problem

Based on our class work using a tree-based data structure whose nodes represent problem states and choices to arrive at that state, complete the project and demonstrate the search algorithm's ability to produce a series of actions that solve the problem.

required organs

Solution vector

Represent a solution to the problem as a vector of GalaxyState objects containing the state and the action taken to arrive at that state from the parent node.

Display the solution to the console in a human-friendly format

expand the galaxy

Our in-class example involved only two planets, and a very simple data bundle on each planet. Augment your program to include more than two planets--perhaps hundreds--which the ship must explore to find a new home for the human race.

Consider a more complex data bundle containing information about each planet. Use a map structure to house key-value pairs pertaining to the conditions on each planet, such as percent Oxygen, gravitational pull, solar radiation intensity (for power), soil composition, or others you design.

solution cost

Encode a leg cost in each action taken, such that the solution to the problem can also be associated with a cost to implement that solution. You'll likely use this information in choosing nodes to expand and choosing nodes along the pathway to the solution.

arrow_upward top

bookOption 2: Data structure-based tool model


Use our foundational data structures of arrays, lists, maps, and/or trees to create a tool for managing data about a subject of your interest.

required organs

Master data structure

Your program should center around one or more master data structures which your functions will manipulate. This could be any of our core structures, such as list, map, or a tree.

Custom type

Your master data structure should contain types of your design, and not simple types, such as string or int (but will certainly contain variables of these simple types). For example, if you're managing homes for sale, you'll want a custom class called House or Property which can be stored in your master structure.

Manipulation functions

The program should use well-defined functions to manipulate your core data structures, possibly using intermediary structures to do so.

For example, if your core data structure maintains a map of House objects keyed by sale status, you'll want functions for reading, inputting, removing, or transferring objects from one key to another.

arrow_upward top

bookOption 3: Priority queue implementation


A priority queue is a foundational data structure in computer science, used widely in process handling and processor time allocation. The goal of this project option is to build your own Priority queue class instead of using C++ standard library functions and demonstrate its use.

required organs

the Queue class

Create a custom type named logically which houses all the required code for viewing, adding to, removing from, and editing queue items

Client class

Write client code to demonstrate the use of the Queue. You'll want to create a use case for your queue to demonstrate its functionality applied to a specific domain of interest, such as a to-do list for a human, an actual queue or people waiting for service, a process queue for an operating system, etc.

Demonstrate that your queue can handle objects of arbitrary type, learning about C++ templating as needed.



The Priority Queue page on wikipedia is extensive

arrow_upward top

bookUniversal deliverables

planning documents

Don't just start coding! Create a hand-written or typed/diagrammed figure which conveys your brain's design process to arrive at the project's structure. Include notes about how these notes helped you.

commented code

Your program should be written in C++ and contain well-structured functions and sensible classes. Comments should be included to describe complex algorithms, all functions, and all classes.

program output

To make your project meaningful to others browsing our library, capture the raw text output of your program or take screen clips of the output in your IDE or on your console.

Include complete documentation of the program's functionality in these output captures: don't forget edge cases!

resource list

None of us are C++ masters yet! Include in your program's documentation an annotated list of sources you used to create your project, such as URLs to official C++ documentation pages consulted, Stack Overflow postings you read through, or tutorials in written or video form.

By annotation, we mean a sentence or two attached to each source citation/URL describing how the resource was used in your project along with attribution to any authors who wrote the resource.

git repository


Push your code to a public or private git repository, and do not include binary/executable files in your git repo


Write a file that contains

  • a description of your project
  • the goals it accomplishes
  • output screen shots
  • sources consulted
  • background information on your journey in the project, including what skills you acquired while creating your tool.
  • build/compile instructions

Don't forget to include any compile instructions for the end user such that they can run your code on their system, even if on a different operating system. Mention required libraries that are outside the C++ standard. Include auxiliary files, such as raw data text files ingested by your code.

arrow_upward top