===========================================================================
CSC 236                     Homework Exercise 2                 Winter 2008
===========================================================================

Due: by 10am on Thu 24 Jan
Worth: 1.5%

For each question, please write your answer formally following the detailed
format given in lecture (in particular, define P(n) carefully in your
inductive proofs).  Keep in mind that approximately half of the marks for
each question will be given purely for having the correct proof structure,
written up clearly and precisely, irrespective of the correctness of the
proof.  Also, make sure that you use notation and terminology correctly,
and that you explain and justify what you are doing -- marks *will* be
deducted for incorrect or ambiguous use of notation and terminology, and
for making incorrect, unjustified, ambiguous, or vague claims in your
solutions.


1.  When computing the product of n distinct real numbers a_1 a_2 ... a_n,
    there are many ways to order the multiplication operations that have to
    be performed.  For example, the product of a_1 ... a_5 could be
    computed in the order (a_1 a_2) (a_3 (a_4 a_5)), or in the order
    a_1 ((a_2 (a_3 a_4)) a_5), or in many other ways.

    (a) Make a conjecture about the number of multiplication operations
        required to compute the product a_1 ... a_n of n distinct real
        numbers, for any n (- N -- in particular, does this number depend
        on the order of the operations?  For example, it takes four
        multiplication operations to compute the product
        (a_1 a_2) (a_3 (a_4 a_5)): first a_4 x a_5, then a_3 x (a_4 a_5),
        then a_1 x a_2, and finally (a_1 a_2) x (a_3 (a_4 a_5)).

    (b) Prove your conjecture using _simple_ induction, by considering each
        possible way that the _first_ multiplication operation can be
        performed when computing the product.

    (c) Prove your conjecture using _complete_ induction, by considering
        each possible way that the _last_ multiplication operation can be
        performed when computing the product.
        For full marks, the inductive step in your proof by complete
        induction must be significantly different from the inductive step
        in your proof by simple induction, i.e., the point of this part is
        to get you to think of a different way of proving your conjecture,
        *not* to repeat your simple induction proof within a complete
        induction structure.  (Hint:  Look at the last example from last
        week's lectures.)