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.