A3 Marking Scheme
-----------------

1. [25 marks]
   a) [3 marks]
   b) [22 marks]
      breakdown:  10 marks for loop invariant
                   6 marks for partial correctness
                   6 marks for termination
      common mistakes:
         - forgot loop condition (at least i iterations)    -3
         - m and n >= 1                                     -1
         - gcd_i <= gcd_{i+1}                               -3
         - no proof that gcd_i = gcd_{i+1}                  -6

2. [15 marks]
   breakdown: 3 marks if the idea of the proof is correct
              6 marks if math is correct
              6 marks if argument is clear and formal

3. [15 marks]
   breakdown: 
      in each of the recursive calls, you need to to argue the 
      following
         4 marks for proving preconditions hold
         4 marks for proving can apply the induction hypothesis
         4 marks for proving correct value is returned
      3 marks for overall proof (structured argument, cases, etc.)