Overview

The final project is an opportunity for you to apply the data structures and algorithms we've discussed this semester in an application of your choosing. In terms of scope, the project should be similar in nature to the sort of things you've done in Fundamentals of Computing I and II or to the projects we've done in this course.

This project is to be done in groups of 1 - 4 and is due midnight Friday, December 09, 2016.

Requirements

The following are all the requirements for your final project.

Data Structures

Because this is a course about data structures, you must create a software artifact that utilizes any of the following data structures or algorithms in a novel manner:

• Priority Queue

  • Binary Search

  • Binary Heap

  • Merge Sort

  • Quick Sort

• Binary Search Trees

  • B-Trees

  • Red-Black Trees

  • Treaps

• Hash Tables

  • Separate Chaining

  • Open Addressing

• Graphs

  • Topological Sort

  • Shortest Path

  • Minimum Spanning Tree

Some Notes:

• You may use any programming language you wish. You are not restricted to C/C++.

• If you are not implementing your chosen data structure or algorithm, you must be using it in a novel way. For instance, simply using the built-in dict in Python does not qualify as novel, nor is simply using anything in the STL. (That said if you wish to implement a data structure and then compare to an existing implementation like we did in previous projects, that would qualify as novel).

• For a list of possible project ideas, please consult the Lecture 28: Final Project slides.

• If you have a project idea that is not on the list, please get it approved by one of the instructors first.

Code Repository

In terms of organization, your work must be done in a Git repository on either GitHub, GitLab, or Bitbucket. Additionally, it must meet the following requirements:

• The project must include a test suite that is checked on each commit for correctness, performance, and memory issues (if applicable).

• The project must include a README.md file that provides instructions on project dependencies, how to setup or install the code, how to run the code, and other relevant information.

• The project must include a CONTRIBUTORS.md file that details the group members and their individual contributions to the project.

Overall, the project should follow the best practices for the language you are using. For instance, projects using C/C++ should have a Makefile while projects using Python should have a requirements.txt and possibly a setup.py.

Benchmarks

In addition to implementing your software artifact, you must perform some sort of benchmarking or measurement that tests and analyzes the performance of your data structure or algorithm (similar to what we have done this semester in the class projects).

• Your tests should measure either execution time or memory usage.

• You must include the code (ie. scripts, tools, etc.) you used to benchmark your data structure or algorithm in your code repository (preferably in a bench or test directory).

• You must include the data you generated in your benchmarking (if the amount of data is large, then you can just provide a summary).

Presentation

On December 7 or 9, your group will be expected to provide a 5 minute presentation on your project to your classmates. This presentation must answer the following questions:

1. Introduction:

   • Who are you?

2. Background:

   • What is your project?

   • What data structures / algorithms did you use?

3. Measurement:

   • What did you measure?

   • How did you measure?

4. Analysis:

   • How do you know what you did was correct?

   • What did your results reveal?

5. Conclusion:

   • What surprised you (if anything)?

   • What did you learn?

Rubric

Your project will be scored based on the following metrics:

Metric	Points
Software Artifact	6
Test Suite	3
Benchmarks / Measurements	3
Presentation	4
Project Organization / Coding Style / Documentation	3
Individual contributions	1
Total	20

Submission

To submit your final project, you must complete the Final Project Form by including:

• Project Name: This is the name of your project.

• Group Members: This is a comma separated list of the netids of your group members.

• Project Description: This is a brief summary of your project.

• Data Structures / Algorithms: This is to let us know which data structure or algorithm you utilized.

• Repository URL: This is the URL to your Git repository. It must be accessible to the instructors.

• Presentation URL: This is the URL to your presentation slides. It must be accessible to the instructors (we recommend putting them on Google Drive).