Project Option: Spiffify A Previous Project

Overview

All of the projects we have done earlier this quarter have rich and fascinating extensions to them. Some of these extensions explore alternative data structures with slightly different operations, improved running time (asymptotically or practically), or simpler implementations. Other extensions included algorithms which added interesting functionality (such as sound reverb or word stemming) or better runtimes.

Implementing and studying these extensions gives you an opportunity to gain familiarity with exotic data structures and algorithms, and to see how in-class concepts translate to real-world applications.

Assignment

For this assignment, you will select a project which you have previously implemented, and use the suggested "Above and Beyond" extensions to help you make it more "spiffy". Since this is a very open-ended project, it is up to you to define your project, create a plan for implementing it, and carry your plan through to completion. The choice of projects and extensions are 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. Remember, your fellow classmates will be implementing at least one new data structure and algorithm; it will not be sufficient, for example, to implement a new visualizer for the MazeRunners.

Possible Extensions

Information about previous projects can be found on the 326 homework page. This page may be useful as a starting point for finding a project which you'd like to extend. Projects of appropriate difficulty may include modifying the MazeRunner assignment to accept cells with an arbitrary number of walls (instead of just 4, as in the SquareMaze), mazes with "one-way" doors, implementing a trie data structure and comparing its performance with the binary search trees, or to implement latent semantic analysis on the word counting project.

Project Mechanics

Because you will be working in a 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!