===========================================================================
CSC 236           Homework Assignment 1 -- Marking Scheme       Winter 2008
===========================================================================


NOTE TO STUDENTS:

You will find below the marking scheme used for your homework, including
the meaning of marking codes and number of marks associated with each one.
This file also contains my instructions to the marker (so you can get an
idea of how the homework was marked) and the marker's comments about each
question.

Please take the time to read this carefully before you ask questions about
the grading of your homework.


NOTE TO MARKER:

Be picky!  On any homework, it is the responsibility of students to show
that they understand how to solve each problem and to write up their
answers carefully.

For each question, I list solution elements with an associated code for
writing on student papers (the letter(s) between underscores _) and a
number of marks.  There are also general errors (with associated codes)
given below, with a maximum number of marks to take off for each type of
general error (as a percentage of the value of the question).  You will
likely encounter other common errors, or maybe decide to break down the
marking scheme further.  Simply make note of these changes/additions to
the marking scheme, and introduce new code letters (or short words) to
allow you to quickly give accurate feedback to the students (both in terms
of what they did wrong and how many marks it cost them).


GENERAL ERRORS (marked negatively, in addition to any other errors):

    _A_rithmetic/_A_lgebra [up to 10%]:  calculation error

    _N_otation [up to 20%]:  incorrect/ambiguous notation/terminology

    _V_agueness [up to 20%]:  incorrect/unjustified/vague claim

General marker's comments:

As you will see, many comments are highly related.  I would highly
recommend for students to read all comments, rather than only what is
marked on their papers.

See overall marking codes below, following the marking scheme for each
question.


1.  [33 marks]

    For each part:

    _S_tructures [3 marks]:  Clear attempt to give two different inductive
        proof structures.

    For each proof structure:

    _C_orrectness [4 marks]:  Correct proof structure, clearly written up
        (proof structure is correct and proves the statement for the right
        values).

    Marker's comments:
    Total marks are 33, evenly split among the three subquestions.  For
    each subquestion, and for each alternative answer, 2 marks for the
    clear attempt and 3.5 for correctness.  This makes 3*2*5.5 = 33.  The
    students are not very familiar with alternative applications of
    induction, and many times they were juggling between 2 or more
    approaches in the same argument.  In my opinion, this is totally
    predictable.  I think of it like someone trying to write how one can
    bike, in the same time he is learning how to bike (and not being able
    to yet).  What I mean by that, is that it would be much easier for the
    students to repeat the same arguments on real (simple) examples.  If
    you ask me, I understand their confusion.


2.  [27 marks]

    _C_onjecture [3 marks]:  Clearly stated and correct conjecture.

    _S_tructure [3 marks]:  Clear and correct proof structure
        (independently of its correctness), i.e., definition of predicate,
        base case, inductive hypothesis, inductive step, and conclusion.

    _P_redicate [3 marks]:  Clear and correct definition of the predicate;
        in particular, correct quantification of all variables other than
        the one being inducted on.

    _B_ase _C_ase [3 marks]:  Clear and correct proof of the base case(s).

    _I_nduction _H_ypothesis [3 marks]:  Clear and correct statement of the
        inductive hypothesis.

    _I_nduction _S_tep [12 marks]:  Clear and correct proof of the inductive
        step, including rigorous justifications for properties of the game
        needed in the proof.

    Marker's comments:
    This was proved very difficult for most of the students.  Many of them
    were not even able to come up with the right structure.  Some tried
    (unsuccesfully) to do induction on n, having fixed some arbirtrary k.


3.  [20 marks]

    _S_tructure [3 marks]:  Clear and correct proof structure
        (independently of its correctness), i.e., definition of predicate,
        base case, inductive hypothesis, inductive step, and conclusion.

    _P_redicate [3 marks]:  Clear and correct definition of the predicate;
        in particular, correct quantification of all variables other than
        the one being inducted on.

    _B_ase _C_ase [2 marks]:  Clear and correct proof of the base case(s).

    _I_nduction _H_ypothesis [2 marks]:  Clear and correct statement of the
        inductive hypothesis.

    _I_nduction _S_tep [10 marks]:  Clear and correct proof of the inductive
        step, including rigorous justifications for properties of the game
        needed in the proof.

    Marker's comments:
    Most did well.


Overall marking codes:

M1.
You have to be careful while encoding the subsequence of integers on which
you are doing induction.  For example, we cannot prove that something holds
for all odd integers >= 3, by considering the sequence 3n, or the sequence
n, n (- N.  You can not even refer to the inductive step as n+1 (if n was a
multiple of 3, then n+1 is not -- or if n was odd then n+1 is not).

M2.
Consider as example solution 1a3.  For the predicate
    Q(n) = n is odd /\ n >= 3 -> P(n),
there is no base case, while in the inductive hypothesis, we do not suppose
the correctness of P(n).  Instead, we start with n is odd /\ n >= 3.
Moreover for 1c3 (for example), consider the predicate
    Q(n) = -] k, n = 2^k -> P(n).
You have to state explicitly the relation between n,k.  The induction is
basically then no longer on n, but on k.  Therefore, there is no meaning in
considering Q(n+1) -- the induction does not prove Q(n+1) from Q(n), but
rather Q(2^{k+1}) from Q(2^k).

M3.
Wrong base case.  If you have to prove a statement for positive multiples
of 3, the base case is P(3) and not P(0).  This is very important, since
otherwise you might be able to prove even wrong statements.

M4.
When parameterizing a statement you have to be consistent with what you
define.  In particular the inductive proof has a special form.  Please read
carefully the third alternative solutions of 1a,1b,1c.
Moreover, if for example you have to consider all multiples of 3, and you
check a predicate P(n), for some n multiple of 3, the next integer to
consider is not n+1, but 3(n+1).
Always remember that the ultimate goal in an inductive argument is to
reduce the validity of a statement of an argument that depends on n, to the
validity of the same argument for a strictly smaller n.  Now if the
integers you have to consider are multiples of 3 for example, the validity
of the statement for some multiple of 3, n, cannot be reduced to n-1,
simple because n-1 is not a multiple of 3.

M5.
I think you are not familiar with induction.  Induction is more than an
mechanical argument, where details do matter.  I think you have to practice
a lot on induction, especially on real examples, and try to convince
yourselves that your argument is valid.  If you do not feel comfortable
with this technique, please consult us during office hours.  I also
recommend you read carefully all posted comments, even if they do not apply
to you.

M6.
There are students, whose answers are a little confusing, although not
wrong.  I am not 100% sure that they know exactly what they are arguing
about, but I did not reduced their mark.  So if someone has high mark,
please do not rely on this, especially if you believe that induction is a
weird creature.
The reason I am commenting on this is because many students tried to
combine different proof techniques.  Since the result is a correct high
level proof, there is a way to fill in the details so that the proof is at
the end correct.  However, many times, these details are quite involved
(and maybe students do not understand it).  For this reason, I would
recommend for them to understand the sample solutions.

M7.
I encountered a nice argument that proves first that if a number is even,
then it can be constructed.  However, there was a gap in proving that it is
possible to construct ALL possible odd numbers.  Note that in this
direction it is not enough to argue how to construct some of the odd
numbers.  I removed 4 marks for that mistake.

M8.
Incomplete (or incorrect or missing) inductive argument.  Examples,
intuitive thoughts or high level arguments do not count as formal proofs
(as requried).  The inductive step should involve a clear inductive
argument.  Deduction of marks varies according to the argument given.

M9.
If the predicate you define is P(n), the induction has to be on n (and not
on k, even if n <= 2^k).  This is a very serious mistake!  [Instructor's
comment: be careful with notation; don't get fooled by variable names.]

M10.
(Can be thought as more comments along the lines of M7).  It is not
difficult to prove that if n is constructible when starting with (2^k,0),
then 2n is constructible when starting with (2^{k+1},0).  This is not the
same as saying that starting with (2^{k+1},0), all even numbers t <=
2^{k+1} are constructible.  However, it turns out that they are equivalent,
as long as the first statement holds for every n <= 2^k, although it
involves a small argument.  In other words, proving that you can produce
some even numbers, it does not mean always that you can produce all even
numbers.  Try to think of it.

M11.
Your argument is wrong.  To convince you, consider (2^10,0), and suppose
that you know how to find all the following configurations: (2^10-1,1),
(2^10-2,2), ..., (2^10-48,48).  Can you really use this information, along
with your arguments, to come up mechanically with the configuration
(2^10-49,49)?  I claim you cannot.

M12.
In the inductive argument, when we need to show P(n) refering to a tree of
size n, we have to do the following: Start with an arbitrary tree of size
n, and reduce the validity of P(n) to P(m),P(k) with m,k < n (using this
way complete induction).  Note that this way we make sure that we deal with
ANY complete tree on n nodes.
Consider now some other procedure:  Start with some small trees on k,m
vertices respectively.  Introduce then a new root v, and connect v with the
roots of the small trees, creating this way a new complete root with
n=k+m+1 vertices.  Note that we fixed some small trees, and therefore we 
came up with a specific tree on n vertice (not an arbitrary one).  However,
we had to prove the statement for some arbitrary tree on n vertices.  You
can also think of the procedure as dealing with an adversary who gves the
tree on n vertices, and then waits for the proof.  If you do not choose the
smaller trees wisely, I am sure that you would disappoint her.  By this I
am not claiming that for any tree with n vertices, there is not an
appropriate choice of 2 smaller trees that makes the second attempt
correct.  What I am saying is that this does not follow from the second
attempt.  -8 for this mistake, which I find very serious (and here I am
picky consciously).

M13.
The question is about full binary trees and not complete and full binary
trees.  The proof for the later is much simpler.  For solving the later
problem and not the one required, -8.