Homework 1 - Grading Standards

Here is the grading standards, if you still have questions with your grade, 
please go the TA's OH or send him/her email to discuss it. Thank you!


Question 1(Graded by Eric): 8 points
Point Breakdown:
2-points for correct use of the change of variables method.
2-points for correct big-O proof.
2-points for correct big-Omega proof.
2-points for correct solution.

Variations: 
-Use of master method to solve recurrence created by changing
variables. No points were taken off if this was done correctly.
-Finding a solution to the recurrence relation created by the
substitution, but changing it back and proving it for the original
recurrence.  This was harder to do correctly, but there was no penalty
if done right.

Common Mistakes:
-Points were taken off if the change of variables method was not used
 to derive the guess. The problem stated specifically that this was
 required.  
-Often the initial solution was right, but was incorrectly
 changed back to the original variables.  
-Missing proof of big-Omega. Need this to show that it is tight.  Less 
 points were removed if the big-O bound was still correct.  More if it 
 wasn't.


Question 2(Graded by Cynthia): 8 points
6 points for correctly drawn recursion tree.
2 points for correct proof of the tight bound.

Common Mistakes:
-No indication for #levels of the tree or wrong value for the #levels of the 
tree. Lots of people gave the time complexity 
as O(nlogn). The reason is simple: they didn't understand the meanings of the
parameters in tree, so they just copyed #levels from the examples of CLRS.  
Acutally it's easy to figure out the right answer after you get the tree levels
right.
-Subtrees for T(a). T(a) should not have any subtrees because it's value have
 no relation with n's size, that is, it won't change as n changes. 


Question 3(Graded by Joe): 8 points
3-points for 4.3-1; 1 point each for questions a, b, and c solved correctly.
3-points for question 4.3-2 solved correctly.
2-points for question 4.3-3 solved correctly.

Common Mistakes:
-Mostly everyone did 4.3-1 correctly.
-For question 4.3-2, the question asks for the largest integer a,
and some people provided an inequality for their final answer.  1 point 
was deducted for this.
-Mostly everyone did 4.3-3 correctly.
-Some people forgot to do 4.3-2 and 4.3-3.


Question 4(Grade by Eric): 8 points
3-points for basically correct method.
1-point for completely correct method.
2-points for correct recurrence relation describing cost of method.
2-points for correct solution to recurrence relation.

Common Mistakes: 
-Assuming that the cost to read a whole number could be considered
constant.  This cannot be done.  There will always be lg(n) digits to
read and lg(n) != O(1). The total cost of this approach would be
n*lg(n). Assuming lg(n) will always be bounded implies n is bounded, 
it should be obvious that it is not. 
-Assuming that the array is sorted.  It was never stated that such was
the case in the problem, and on DISCUS we specifically said you could
not make this assumption.
-Using radix sort.  Close but not quite.  Reading carefully radix sort
takes O(n*d) time, where d is the number of digits used to represent
the numbers.  In this case this translates to a cost of O(n*lg(n)).


Question 5(Graded by Joe): 8 points
2-points for part a
3-points for part b
3-points for part c

Common Mistakes:
-Mostly everyone got part a correct
-For part b, many people did not consider a case.  They either did not 
state what the algorithm should do for a good-bad pairing, or they did not 
state what the algorithm should do for a good-good pairing.  So they did not consider all possible cases
-For part c, some people neglected to provide the actual recurrence relation.
They just provided the run time.
-At the very least, please attempt the problem.  Some people did not.


Question 6(Graded by Victor): 8 points 
2-points for verifying the correct base case.
2-points stating the correct IH and trying to use it in the IS.
2-points for a correct solution.
2-points for a clean and well structured write-up.

Common Mistakes: 
-Some people checked the wrong base case (P(2)); although this is
almost correct and with the IS together proves most cases it leaves
out one case (n = 1). 
-Some people tried to modify the proposition to an expression that
is essentially the identity, and went on proving this for the n+1
case. In most case this identity was: (1/2 n(n+1))^2 =  
(n^2(n+1)^2)/4. I hope that everyone agrees that this does not
prove anything about the initial proposition.


Question 7(Graded by Victor): 8 points
2-points for an incorrect but thoughtful reasoning.
2-points for identifying the source of the problem (insufficient
basis).
2-points for identifying that the Basis and the IS together does
not imply P(2).
2-points for a clean write-up. 
 
Common Mistakes: 
-Some people found the argument in the IS circular. I think that
that confusion in most of the cases was that in this proof P(n-1)
implies P(n) is shown. This is equivalent to showing that P(n)
implies P(n+1).
- Some people have identified the source of the problem, but did
not shoe why that was a problem. 


Question 8(graded by Cynthia): 8 points
There is actually two ways to prove: one is by induction proof, the other 
is by contradiction. Most answer used the induction proof. So here is the 
grading standards of induction proof:
3 points for correct claim, base step and induction hypothesis
5 points for correct proof in the induction step.

Common Mistakes:
It seems that many of you came to my office hours, so most of you used the
lemma I mentioned in your proof. However, few people really understand why
I used that lemma, and how to use it in induction proof. 
- First, the lemma is: there must exists a depot i, from which you could start
with and reach its neighbour i+1 without running out of gas. This lemma 
could be proved by contradicion as shown in the solution. However, this lemma 
itself could NOT guanrantee i is the start point to travel the whole track 
without running out of gas. So proving this lemma doesn't mean you finish
proving the original statement discribed in the question.
- Second, many people use the following proof:(G1-L1)+(G2-L2)+...+(Gn-Ln)>=0
so G1-L1 >= 0, G2-L2 >= 0, ... Gn-Ln >=0. Please think about this twice, how
could you come to this ridiculous conclusion?

Few of you did this question without any errors. It seems that most of you 
still don't understand the concepts and logic of induction proof quite well.
Please feel free to come to my OH and discuss this question with me again.