Marking Scheme for Test 1 Section 2:

Question 1:     1 mark for each correct answer
Question 2:      3 marks for each part.
                For part a, I was looking for the mentioning of the notion
of S* EXTENDING Si to award full marks.
                For part b, in order to prove correctness, you had to
prove mention that the GA comes up with an optimal solution.  You had to
show that Sn is in this case the optimal solution that the GA comes up
with.
                For part c, 2 marks for mentioning the two requirements
for Si+1 being promising, i.e., Si+1 is a subset of Si+1* and Si+1* - Si+1
is a subset of Ci+1.  Simply mentioning that Si+1 should be promising
earned 1 mark.  While the 3rd mark was awarded to describing how to find
such Si+1*.
		For part d, 1 mark for mentioning the two requirements
for Si+1 being promising, i.e., Si+1 is a subset of Si+1* and Si+1* - Si+1
is a subset of Ci+1.  Simply mentioning that Si+1 should be promising
earned 1/2 mark.  While the rest of the two marks were awarded to
describing how to find such Si+1*.
                For part e, simply describing the conclusion that there is
a unique optimal solution earned 2 marks.  The 3rd mark was awarded to
descring in each of the two impossible cases as to how to get to that
conclusion.  However, simply describing the consequences of those two
impossible cases without making the conclusion that there is a unique
optimal solution also deserved 3 marks.
Question 3:     6 marks for the algorithm.  The algorithm must attempt in
some logical way to fill the knapsack.  Infinite loops or loops within
the outer loop are grounds for losing marks. Similarly overfilling the
knapsack also lost marks.
                3 marks for the counter example out of which 2 for showing
the greedy solution and 1 for the optimal solution.  If the greedy
solution turns out to be optimal, then the counter example deserves 0.