Comments on Assignment #2

Assignment 2 was not done as well as I would liked.  The average was
50%.  Please read through these comments so that you can learn from
your (and your classmates') mistakes.

It seems that, in many cases, students did badly because they started
at the last minute (i.e. less than a week before the assignment was
due).  

As mentioned in lecture, the markers found many of the assignments
poorly written, and badly organized and in some cases illegible.  
It is very important to proofread your papers carefully.  While you
proofread, you should look for grammar and spelling errors, but you
must also think about each step of your arguments, ensuring that the
step is correct and adequately justified.  You should also think about
whether you have expressed yourself in the clearest possible way.
When I looked at some of the papers, I saw lots of silly errors that
could easily have been caught and corrected if the student had 
proofread the paper.  Don't throw away marks.

Since you have a month to do each assignment, you should spend some
time polishing your papers.  In order to do this, you must start early!

*************************************************************************

ABBREVIATIONS

Some of you may have found abbreviations used for the comments on your
paper.  Here's what they mean.

General
	NAP	(Not a proof)
		A lot of hand-waving, but there is no supporting logical 
		argument.



Question 1)

	NPT  (No proof techniques given)
		No proof techniques were named in the proof of validity.

	CPE  (Contradiction in premises poorly explained)
		You allude to a contradiction in the premises, but are very 
	unclear as to where exactly it is.

	VPE  (Validity poorly explained)
		You show there is a contradiction in the premises, but you fail
	to show that this makes the argument valid.

	WPTN (Wrong proof technique named)
		You named some proof techniques, but they did not correspond
	to the ones actually used.

	IPV  (Incorrect proof of validity)
		Your proof of validity was just incorrect.


Question 5)
	MIV  (Missing Important Invariant)
		Depending on your algorrithm you were
		Missing a invariant which says something like "There is an x
		A[f]<=x<=A[l], where f=first, l= last, A= array, and x is in
		S, but not in A."
	
		An invariant of this form is NECESSARY for the proof of 
		correctness.

	MBIV (Missing Bookkeeping Invariant)
	
		Depending on your algorithm you were missing an invariant of
		the form 

		1<=f<=mid<=l<=n.

		An invariant which says that your variables are remaining in
		their proper domain.

	MPIV (Missing Proof for Important Invariant)
	
		Because you missed the important invariant you also missed 
		the proof for the important invariant.

	MPBIV(Missing Proof for Bookkeeping Invariant)
		
		Because you missed the bookkeeping invariant you also missed
		the proof for the bookkeeping invariant.


**************************************************************************

COMMON ERRORS

#1:  This one was generally fairly well done.
     Often, answers were too brief; the proof should contain enough
	detail to be convincing.

#2:  In the base case, when considering formulae of length 1, students
	forgot to consider the formulae T and F.
     Some students tried to use ordinary induction instead of strong
	induction on the length of the formula.
     In the inductive step, some students did the following:
	Consider an arbitrary formula alpha of length n+1.
	Then alpha has the form beta /\ X or beta \/ X or ~beta,
	where beta is a formula and X is a propositional variable.
	This is not true!  Consider the formula B /\ (C \/ D), for
	example.  When you are doing a proof by cases, then you must
	make sure that you cover all of the cases.
     Some students' induction hypothesis did not depend on n.

#4:  Improper manipulations of logarithms.
     Improper manipulations of the summation symbol.  The most common
	error here was trying to use a formula for 
	(1^2 + 2^2 + 3^2 + ... + n^2) to compute the value of
	((log 1)^2 + (log 2)^2 + (log 3)^2 + ... + (log n)^2).
	Any such attempt was doomed to failure, obviously.
     Some bounded both f and g from above.  See the solution sets
	for a correct answer.  Many tried saying things like this:
	f is in O(n), g is in O(n^2) and therefore f is not in O(g).
	This is an incorrect inference.  For example, if f(n)=g(n)=n,
	then f is in O(n) and g is in O(n^2), but f is in O(g).
     Some people thought that if f is not in O(g) then g must be in O(f).
	See the newsgroup for an example of two functions that show
	this inference is incorrect.
     It does not follow from the fact that g > f that f is not in O(g).
	For example, if f(n)=n and g(n)=n+1, then g is always greater
	than f, but f is still in O(g).

#5:  Many got the algorithm approximately correct.  Perhaps some special
	cases were omitted but, overall, it was well-done.
     Many had trouble coming up with useful invariants.  It's important
	that your invariants are both true AND useful.  In order to be
	useful in proving your algorithm correct, the invariant should
	capture some notion of the progress you are making toward your
	goal (i.e. towards the postconditions) with each iteration of
	the loop.
     For those who got the invariants, the proofs were reasonably well-
	done.
     Termination must be proved!
     Post conditions must be proved using the invariant and the fact
	that the loop terminates.

#6:  Some people are still having trouble with the format of a proof
	by induction.
     Tracing the algorithm for one input does not prove anything about
	its general behaviour.  The trace was intended merely to give
	you an idea of how the algorithm works so that you could guess
	what the invariants are and why they are true.  Whenever you
	prove an algorithm correct, you must prove that it works
	for *any* input that satisfies the preconditions.