Posted by: Jesse | September 9, 2011

This rubric is a guideline for how the points will be distributed for homework 1.  further breakdown of points and partial credit will be determined by Jiun-Jie and myself when we start grading.  Please be sure to follow the format for homeworks in this course.  Your proof idea should be clearly labeled and should be an overview of how you will prove the theorem and should be written in English sentences with only the necessary mathematical notation.  See the solutions of homework 0 for examples.

1. (40 points)
(part a) (20 points)
(4 points) for getting the true or false correct.
(8 points) for the proof idea.
(8 points) for the proof.

(part b) (20 points)
(4 points) for getting the true or false correct.
(8 points) for the proof idea.
(8 points) for the proof.

2. (45 points)
(25 points) for the algorithm: 13 for algorithm idea, 12 for algorithm. Note that the algorithm idea should follow the same guidlines as a proof idea.

(20 points) for a proof that the algorithm is correct: 10 for proof idea, 10 for proof.

3. (15 points)
(3 points) for an example at any fixed value of n (e.g. n=4).
(6 points) for a proof idea
(3 points) for giving a correct instance of the problem for all n
(3 points) for proving that the instance is correct