******************************
Assignment #1
******************************


Question #3) This was the coin collectors problem. Here is how the
	marking was broken down

1/5 : Mention of induction, and the use of optimal sequences, but in a
fashion which made little or no sense to answering the problem.

2/5 : Mention of induction, and the use of optimal sets, but in a
fashion which made little or no sense to answering the
problem. Showing that when no coin was chosen the algorithms sequence
was extendible to an optimal sequence.  Showing that when a coin was
chosen that was in the optimal sequence that the algorithms choices
were still exetendible to an optimal sequence.

3/5 : Mention of induction, and the use of optimal sets, but in a
fashion which made little or no sense to answering the
problem. Showing that when no coin was chosen the algorithms sequence
was extendible to an optimal sequence.  Showing that when a coin was
chosen that was in the optimal sequence that the algorithms choices
were still exetendible to an optimal sequence.  Claim that the
algorithm cannot choose the wrong coin, but failling to provide a
valid proof that this claim was true.

4/5 : Mention of induction, and the use of optimal sets, but in a
fashion which made little or no sense to answering the
problem. Showing that when no coin was chosen the algorithms sequence
was extendible to an optimal sequence.  Showing that when a coin was
chosen that was in the optimal sequence that the algorithms choices
were still exetendible to an optimal sequence.  Claim that the
algorithm cannot choose the wrong coin, and providing a proof of this
claim which has a few minor mistakes.

5/5 : Mention of induction, and the use of optimal sets, but in a
fashion which made little or no sense to answering the
problem. Showing that when no coin was chosen the algorithms sequence
was extendible to an optimal sequence.  Showing that when a coin was
chosen that was in the optimal sequence that the algorithms choices
were still exetendible to an optimal sequence.  Claim that the
algorithm cannot choose the wrong coin, and providing a correct
convincing proof of this claim.

Question #5)
	Modified shortest path quesiton.

	There were two ways of marking this question. You received the
mark which was higher of the two methods of marking.

First Method)
	If you're algorithm was correct it received 6/6.
	Small to large errors received 1 to 3 mark penalties.
	Order n^3 time algorithms received a 0/6.	


Second Method)

	2 marks for giving the array. This should be the array used in
your algorithm. Many people gave arrays which ended up having nothing
to do with their algorithm. Such an array was not worth anything. An
3-d array received 0 marks, as it will necessarily take. 1 mark off
for small errors.

	2 marks for giving the recurence. Again the recurence should
be the one implemented in the algorithm, and should involve at most a
2-d array, and clearly be implementable in order n^2 time. A
reccurence which takes order n^3 time to fill in the array received
zero. 1 mark off for small errors.

	2 marks for an algorithm implementing, in order n^2 time, the
above reccurence relation to compute the array. 1 mark off for small
errors, or if you implemented a small error from your recurrece
relation.  0 marks for major errors, and n^3 time algortihms.

***********************************************
Quiz #1
***********************************************

Question 1c) 2 marks for compelete correct proof.  1 mark for a proof
        with a minor mistake, but in which the writer clearly shows
        that he/she understood the concept of the proof.  0 marks
        otherwise.

Quesiton 3)
There are 4 post marks listed below.

3/12 marks for stating that if A(k)=A(k-1) we consider the problem
A(k-1) recurisvely.

5/12 marks for stating that if A(k)=A(k-1) we consider the problem
A(k-1) recurisvely. And for stating that we look for the first
occurence in the array where A(k)=p_{i_0} + A(H(i_0)).

8/12 marks for stating that if A(k)=A(k-1) we consider the problem
A(k-1) recurisvely. And for stating that we look for the first
occurence in the array where A(k)=p_{i_0} + A(H(i_0)) and f_{i_0} =
u_k.


12/12 marks for stating that if A(k)=A(k-1) we consider the problem
A(k-1) recurisvely. And for stating that we look for the first
occurence in the array where A(k)=p_{i_0} + A(H(i_0)) and f_{i_0} =
u_k. Finally, state that we recurse on A(H(i_0)), and finish if
H(i_0)=0.


>From the above post marks, 1-4 marks could be subtracted due to poor
explanations, minor and major errors, typographical mistakes, etc...