Problem #1:

1. Initial conditions y_0, y_1 (2 pts)

   Recurrence relation (5 pts)

2. Characteristic equation (5 pts)

   Correct roots (2 pts)

   The equations to find the value of C and D using the initial conditions (4 pts)

   Correct C and D and final result (2 pts)  ( If you didn't get the correct recurrence relation, but solved the relation you found, you will get full points for the 2nd step in Problem #1.)

Problem #2:

1. Iteration method (a_0=?, a_1=? .....) (3 pts)

   Explicit formula (7 pts)

2. Base step (2 pts)

   Induction hypothesis (2 pts)

   Induction step: (a) even case (3 pts); (b) odd case (3 pts)

 

Problem #3:

4 pts for each question. For question #2, if you state something similar to "two vertices are connected if and only if they are adjacent", this is wrong.

Problem #4
1. Yes/No answer for (a)/(b) gets 40%
2. Yes/No answer for (a)/(b) and attempted to prove but failed to provide
a complete argument gets [45-60%]
3. (b) forgot to show deg(v_13) (-2)pts
4. (b) forgot to show that G is connected (-2)

Problem #5
1. Forgot to quantify "x>?" across -10pts
2. forgot to quantify "x>?" only when claimed f(x) in O(h(x)) -5pts
3. Quantified "x>x_o$ for both f, and g -8pts
4. Does not understand the definition of Big-O gets [0-3]pts
5. "Proved" 2 gets 0pts
6. Have stated the definitions correct but failed to prove gets 5pts
7. Definitions are incorrect/incomplete but derived transitivity gets
5pts.