Project Option: Choose Your Own Data Structures Adventure

Overview

There are a variety of data structures which we did not write up in projects that are interesting alternatives to those we focused on. These support slightly different operations; improve running time (asymptotically or practically); or emphasize simplicity of coding. Some of these are relatively obscure, difficult to code, or difficult to understand. Implementing and studying these gives you an opportunity to expand your repertoire of data structures and to acquire a deep understanding of their strengths (and weaknesses).

Assignment

For this assignment, you will select a project, define your method of completing this project, and carry out your plan for completion. The project choice is entirely up to you, although we reserve the right to make suggestions/modifications (or even reject) a project based on its unsuitability as a 2-week-long data structures assignment.

You can find some ideas for suitable projects here or here.

Project Mechanics

Because you will be working in an entirely different direction from the majority of the class, the course staff cannot guarantee that we will be able to support you as fully as we could in other projects. However, to ensure that we are prepared to give you the best help that we are able to, we will require the following additional information in your project proposal:

An in-depth description of what you hope to achieve, and the data structures and algorithms which you plan to use (do not assume that we know anything about the data structures and algorithms!).
The resources which you plan to use. This may include websites describing the algorithms which you will use, software packages (such as OpenGL), additional readings, and libraries (such as the STL).

A rough schedule (or list of milestones) for each member of your team. This does not need to be detailed, but does need to be clear enough to give us an idea of your proposed workload. The following is an example of what might be an appropriate schedule:

Monday: (Joe and Billy-Bob) Complete understanding of the FrapToggle
        data structure and the ZapDoodle algorithm.
Wednesday: (Joe) Working prototype for the FrapToggle data structure.
           (Billy-Bob) Unit tests for FrapToggle data structure complete.
Thursday: (Joe) Stable version of FrapToggle data structure complete.
          (Billy-Bob) Begin implementing the ZapDoodle algorithm.
Saturday: (Joe) Working prototype for ZapDoodle visualizer.
          (Billy-Bob) ZapDoodle algorithm completely implemented.

Remember, this is a data structures course, and you have approximately 2 weeks to complete this project. We reserve the right to make large-scale modifications to your project proposal if we feel that your project is not appropriate to the spirit of this assignment. Please choose a project of reasonable difficulty which illustrates a set of reasonable data structures concepts.

Best of luck!