Data Structures final project specs

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.

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

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.

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.

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.

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.

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.

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.

wikipedia

The Priority Queue page on wikipedia is extensive

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.

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.

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!

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

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

resources

book

The git book by Scott Chacon and Ben Straub

readme.md

Write a readme.md 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.