Collatz


Due: Thu, 11 Sep 2014, 10pm
70 pts, 7% of total grade.


Specification


Write a program, individually, to solve The 3n+1 Problem in C++ with some form of cache:

You may not use new, delete, malloc() or free(). You may use the STL.

Analysis


These are additional descriptions of the underlying math:

Requirements


  1. Estimate time to completion.
  2. Get an educational account with 5 private repos at GitHub.
  3. Create a private Git repository at GitHub, named cs371p-collatz.
  4. Add at least 10 of these requirements as issues to the issue tracker at GitHub.
    Add at least 10 more issues, one for each bug or feature, both open and closed with a good description and a label.
  5. Invite the graders to your private code repo.
  6. Confirm that the graders have invited you back to the public test repo.
  7. Clone your private code repo onto your local directory.
  8. Make at least 5 commits, one for each bug or feature.
    If you cannot describe your changes in a sentence, you are not committing often enough.
    Make meaningful commit messages identifying the corresponding issue in the issue tracker (see here).
  9. Clone the public class repo onto your local directory.
    It is critical that you clone the public class repo into a different directory than the one you're using for your private code repo.
  10. Copy the code files from the clone of the public class repo to the clone of the private code repo.
  11. Run RunCollatz.c++ and TestCollatz.c++, confirm the expected successes, and add, commit, and push to the private code repo.
  12. Fix the given unit tests, confirm the expected failures, and add, commit, and push to the private code repo.
  13. Write more unit tests in TestCollatz.c++ that test corner cases and failure cases until you have an average of 3 tests for each function, confirm the expected failures, and add, commit, and push to the private code repo.
  14. Implement and debug the simplest possible solution in collatz_eval() in Collatz.h and Collatz.c++ with assertions that check pre-conditions, post-conditions, argument validity, and return-value validity, until all tests pass, and add, commit, and push to the private code repo.
  15. Combine Collatz.c++ and RunCollatz.c++ into UVaCollatz.c++ (don't forget to remove the #include).
  16. Create an account on UVa.
  17. Submit UVaCollatz.c++ to UVa and confirm the likely result of time exceeded or wrong answer.
  18. Debug the code until it's accepted by UVa, and add, commit, and push to the private code repo.
  19. Create 1000 lines of acceptance tests in RunCollatz.in and RunCollatz.out that test corner cases and failure cases, and add, commit, and push to the private code repo.
  20. Clone the public test repo onto your local directory.
    It is critical that you clone the public test repo into a different directory than the one you're using for your private code repo.
  21. Copy your unit tests and your acceptance tests to your clone of the public test repo, rename the files, do a git pull to synchronize your clone, and then add, commit and push to the public test repo.
    The files MUST be named EID-RunCollatz.in, EID-RunCollatz.out, EID-TestCollatz.c++, and EID-TestCollatz.out in the public test repo.
  22. Implement and debug the simplest possible cache until all tests pass, and add, commit, and push to the private code repo.
  23. Submit and debug until accepted by UVa and add, commit, and push to the private code repo.
  24. Run Doxygen, which will create html/, that then documents the interfaces to your functions.
    Create inline comments if you need to explain the why of a particular implementation.
    Use a consistent coding convention with good variable names, good indentation, blank lines, and blank spaces.
  25. Create a log of your commits in Collatz.log.
  26. Obtain the git SHA with
    git rev-parse HEAD
  27. Fill in the Google Form.
  28. It is your responsibility to protect your code from the rest of the students in the class. If your code gets out, you are as guilty as the recipient of academic dishonesty.

Requirements for getting a non-zero grade.


  1. [  5 pts] GitHub private repo with graders invited as collaborator and a log of the commits.
  2. [  5 pts] GitHub issue tracker with issues from requirements and more.
  3. [15 pts] Accepted solution to UVa 4073 (C++ 4.3.2) with some form of cache.
  4. [15 pts] Average of 3 unit tests per function with good coverage in the public test repo with the precise naming of the files.
  5. [15 pts] 1000 lines of acceptance tests in the public test repo with the precise naming of the files.
  6. [10 pts] Doxygen documentation.
  7. [  5 pts] Google Form with time estimate.

Penalties


  • Your solution will be verified. Your solution will also be tested against the acceptance tests of five other students. You will be given a max of 10 penalty pts, 2 penalty pts for every set of tests that break your solution.

Bonuses


  • Your acceptance tests will be verified. Your tests will also be used to test the solution of five other students. You will be given a max of 10 bonus pts, 2 bonus pts for every solution that your tests break.
  • Bonus pts will not increase the total score beyond the max score.

Private Code Repo Files


Place the following files, with these exact names, directly in cs371p-collatz, no subfolders:

  1. Collatz.h (do not change the interfaces)
  2. Collatz.c++ (do not change the interfaces)
  3. RunCollatz.c++ (do not run gcov, do not run valgrind)
  4. RunCollatz.in (1000 pairs)
  5. RunCollatz.out (1000 triples, no gcov output, no valgrind output)
  6. TestCollatz.c++ (average of 3 unit tests per funciton/method, run gcov, run valgrind)
  7. TestCollatz.out (include gcov output, include valgrind output)
  8. Collatz.html (output of Doxygen)
  9. Collatz.log (output of git log)
  10. UVaCollatz.c++ (concatenation of Collatz.c++ and RunCollatz.c++)
  11. gitignore.txt (rename .gitignore, for your use only, no need to submit)
  12. makefile (for your use only, no need to submit)

Public Test Repo Files


Place the following files, with these exact names, directly in cs371p-fall-2014/collatz-tests/, no subfolders:

  1. EID-RunCollatz.in (1000 pairs)
  2. EID-RunCollatz.out (1000 triples, no gcov output, no valgrind output)
  3. EID-TestCollatz.c++ (average of 3 unit tests per funciton/method, run gcov, run valgrind)
  4. EID-TestCollatz.out (include gcov output, include valgrind output)

Tools


Guides


Graders


Name GitHub ID GitHub Test Repository Google Form
Henry Chen chukhinhenry collatz-tests Google Form
Sam Thompson st028
Thanh Nguyen thanhcs
Tyler Hunt tylershunt