Project #6: Redux Group Project

In this project, you will select a problem and a solution algorithm to contribute to the online, interactive, knowledge base of canonical CS problems, Redux.

Objectives

1. Gain experience working in a group
2. Gain experience contributing to an existing, real-world code base using git
3. Gain experience with formal definition, implementation, and algorithmic solution of computer science problems

Teams

This will be a group project on which you will all work in teams of 2-3 students. As a team you will hand in one report and also do one group presentation on the last day of class. Your team will all receive the same base grade for the project. To augment this, each team member will e-mail me a thoughtful and honest evaluation of the contributions of their team members, including themselves. For each individual, this evaluation should include a score from 1 to 10 indicating your evaluation of their work (10 meaning they were a valuable member of the team that made significant contributions to the project and were good to work with, 1 meaning they contributed nothing and were difficult to work with). If you would like, you may also include any clarifying comments, etc. (especially for low scores). If a person receives consistently low evaluations from peers, then their score will be proportionally decreased.

Framework

Information is available on the Redux site for how to get started and how to contribute to the project. In short, you will fork any repos that you plan on contributing to (likely only the backend repo) and clone any repos you don't need to change (likely only the frontend repo). Then you can run a local version of Redux that will reflect your changes and allow you to develop and debug. When your contributions are ready, you will submit them as a pull request to the appropriate repository.

Selecting a Solution Algorithm

You should choose a problem requiring an algorithmic solution. This may or may not be a problem currently implemented in Redux. It may be a problem we considered this semester or another problem of your choosing. When choosing, take note of which complexity class the problem is from (P, NP-complete, NP-hard) as it will affect how you approach your implementation. You must get your problem and solution algorithm approved by me. First come, first serve. Groups may choose to add a new solution algorithm to a problem that is already in Redux, and/or multiple groups may choose add a common problem and then add different solution algorithms. The goal is to add something of value to Redux.

To Do

1. Complete the Redux Consent Form indicating your decision as to whether you give your permission for contributions on this project to be incorporated into the live Redux website. (If you do not want your contributions incorporated, please follow the special instructions below to submit your work.)
2. Form a group of 2-3 people. For contributions to be incorporated into Redux, all group members must give their permission. If your group does not plan to incorporate your contributions into Redux, please follow the special instructions below.
3. Select an algorithm to implement that isn't already implemented (as a solver) in Redux. If the problem your algorithm solves is not already in Redux, you will add the problem as well. If the problem your algorithm solves does not already have a Verifier in Redux, you will add the Verifier as well.
4. Email Dr. Bodily the problem and algorithm for approval. This email should include all information that would go in the information dialog boxes in Redux for the problem and algorithm.
5. Upon approval, implement the solver (and, if necessary, the problem and/or verifier) in Redux.
6. Implement unit tests inside of redux-test for your solver (and, if necessary, the problem and/or verifier) to demonstrate correctness. Make sure unit tests cover edge cases. Run tests with: dotnet test.
7. Submit a single pull request with all of your contributions. When you submit a pull request, you will be prompted to complete the contributor license agreement (CLA). The Redux repo is configured such that we cannot merge your pull request until all contributors on the PR have completed the CLA. This is separate from the research consent form you (should have) filled out previously. The CLA form allows us to use contributor's code (including non-students) in an open-source project whereas the research consent form allows us to publish student work which without such consent would violate FERPA rules.

How to submit your work without including it in Redux

While contributing your work to Redux has some potential benefits to you (e.g., showing prospective employers examples of your work on a real-world, full-stack development project), there may be some who do not want their work to be made public. As a general rule, FERPA prohibits requiring students to post work in a public space without providing a private alternative or a signed waiver. I want to respect this right, and you will not be penalized if you do not want to contribute your work to Redux. If you do not want your work included in Redux, you need to take the following steps:

1. After forking the Redux repository, detach your forked repo from the parent repo
2. Make your repo private
3. Add the TA as a contributor on your repository
4. Before making any changes, create a new branch on your repository
5. After you have made your changes, submit a pull request to your private branch which the TA will then review

What is a verifier?

A verifier takes in a proposed solution and verifies that it, in fact, solves the problem instance. For P-time problems, this can be implemented simply as a call to your solver and then a check to see if the proposed solution and the solver's solution are equivalent (be sure to account for problems having multiple correct solutions , e.g., Shortest Path). For NP-complete problems, a polynomial-time verifier may not use a solution algorithm because polynomial-time solutions do not exist (but typically have very simple implementations all the same).

Grading

No report will be required for this project. Your grade will be determined from the pull request submitted based on the following criteria:

1. Proper naming of the solver (and, if necessary, the problem and/or verifier)
2. Proper definition and descriptions in the respective information dialog boxes of the solver (and, if necessary, the problem and/or verifier)
3. Proper sourcing of the solver (and, if necessary, the problem and/or verifier)
4. Proper contributor attributor information provided in dialog boxes and on 'About Us' page
5. The solver (and, if necessary, the problem and/or verifier) programmatic implementation is correct
6. The pull request should include comments specifying the names and specific contributions of each team member (so we can follow up with questions later if necessary)
7. Thorough unit tests implemented

Oral Presentation

Each group will give a short oral presentation of their project on the last day of class (5 minutes). The presentation should introduce the problem you chose and the algorithm you chose to solve the problem. Explain why you chose the problem/algorithm (while giving appropriate attribution, any challenges/detours along the way, and the pros and cons of your approach) Your presentation should primarily consist of a live demo of your contribution in Redux (a locally running instance is fine). Be sure to point out and explain all information in each dialog box. The presentation should be professional, and will need to be practiced to make sure it fits the time constraint.