Final Project Details

Use this assignment link to generate your repo and join your project team.

The final project for CIT 5940 is an open-ended group project to be completed in teams of three.

You should choose a project idea that interests you and your group. The broad requirements are listed below. In order for a project to be approved, you must indicate how you plan to satisfy several important requirements. Keep in mind that features like GUIs, web deployments, or the use of libraries in other programming languages are acceptable to include in your project but that they do not count towards the overall completeness & grading of your project.

  • Your project must show meaningful, novel, and rigorous use of material from one unit in this course. There should be at least one data structure or topic that is central to your project and shows thoughtful application of the material from that unit to the specific problem at hand.
  • Your project should show efficient and well-motivated use of other at least two data structures covered in this course. These uses & implementations can be “off-the-shelf” to some degree, but should show that you have thought about the problem and chosen the right data structure for the job.
  • Your project should feature one of the software design patterns discussed in this course. You are allowed to choose patterns not discussed in the course as long as you get approval.
  • Your project must be developed using Git & GitHub, with a clear project management strategy. This includes:
    • issues
    • story points
    • feature branches + pull requests
  • Your codebase must be maintainable and understandable, meaning that it must include:
    • a UML design diagram
    • interfaces for all non-trivial classes
    • thorough testing
    • a clear README
    • neat & informative comments

The first point is one that will likely shape the direction of your project, and is also one that is likely to generate the most questions. There is a list of acceptable & unacceptable project ideas at the end of this writeup that can be used to help gauge whether your project develops an idea to a sufficient degree.

Final Project Proposals

By April 23rd @ 11:59pm, please upload a 1 page PDF of your Final Project Proposal. Additionally, one person from your group must fill out this form.

Each proposal should include:

  • A list of participants.
  • An explanation of the project idea, including a discussion of why your group chose this idea.
  • A list of intended features. This should probably be a longer list than you intend to implement since we will probably reject some ideas and you might not finish everything you set out to do!
    • Mark which feature or features is the one that you feel is the most meaningful and novel use of material from this course.
  • Which software design pattern you intend to implement.
  • Any outstanding questions you have that you would like the course staff to help you answer about your project.

Project Update & Check-In

By May 3rd @ 4:59pm, please email the instructors and your project TAs with:

  • any questions you would like answered
  • a brief status update on your project
    • What have you completed so far?
    • What is giving you trouble?
  • UML diagram(s) & interfaces for feedback

This will count for a portion of your final project grade. A template for this email is provided here.

Final Project Deliverables

The final project deliverables (detailed below) will be due on May 10th. Each group will be assigned TAs; please check in with them if you have any project-specific questions! Groups are encouraged to finish the project & present it early—start your summer break as soon as you can!

Interfaces + Documentation

Full credit will be given for clear method input/output (methods should always have an input and an output for testing), minimization of instance variables, and high cohesion/low coupling. Each class should have its own unique and clear purpose. A class should avoid requiring the use of another class for a significant portion of its methods.

Uploaded to Git + emailed to assigned Project TAs by May 10 and at least 2 hours before project presentation.

GitHub requirements

  • Assignment created in GitHub
  • Use project management
    • milestones, issues, story points, code review
  • Branching and merging
    • feature branches + pull requests

Testing:

Code coverage minimum: 80% (only for Java parts). Will be checked during live/final presentation.

Final Presentation:

Sign up for a timeslot on May 9th here (TBD), or reach out to your assigned Project TAs to potentially schedule an earlier demo.

Detailed 15-20 minute explanation of problem, interfaces, data structures, design, GitHub use, testing, project demo, and individual team member contributions.

Grading

  • Correctness: 40%
    • This category includes the portion of your grade that comes from correctly using appropriate data structures to implement your project.
  • Completeness: 5%
    • This category includes the portion of your grade that comes from completing the project to the extent that you proposed.
  • Testing: 30%
    • Same rules apply as for the homework assignment for all components of the project written in Java.
  • Design: 5%
    • This category accounts for your successful implementation of the chosen software design pattern.
  • GitHub: 5%
  • Style: 10%
  • Presentation: 5%

Acceptable and Unacceptable Ideas

There might be several ideas for projects that center around the use of graphs. Some will be suitably novel and complex and others will not. A graph representing physical adjacency (such as the Engineering Quad example from lecture) or a graph representing a social network are both examples that do not represent sufficiently large developments from straightforward uses of graphs. On the other hand, finding data that can constitue a matching problem and representing that data in a graph in order to find some solution to the problem could be acceptable.

Indexing is often a suitable topic for a project, but it requires data that can be organized and queried in several useful ways. Maintaining a database of image files like the Facebook Haystack architecture would be suitably complex, but building an individual primary key index over a series of text files would not be. For an indexing project to be acceptable, it should be able to answer queries that are not trivially answered by a linear search or binary search over a single view of the data.

Some other potentially interesting data structures & project combinations:

  • An experiment demonstrating the effectiveness and drawbacks of several different hashing implementations, including different choices of hash functions and collision resolution strategies.
  • Creative uses of graph algorithms to solve problems like matchings, set packing
  • Modeling particles in a simulation using a point-based quadtree or octree
  • Exploring the use of a kd-tree for nearest neighbor search in a high-dimensional space
  • Implementing a bloom filter and benchmarking its performance with different settings and also against a deterministic hash table
  • Using the UNION-FIND data structure.

Some data structures or topics that are unlikely to be suitably complex to base a project around:

  • heaps
  • queues & stacks
  • trees & graphs for well-known problems like shortest path, minimum spanning tree, etc.
  • tries
  • lists, sets, maps