Week 8 - Iterative Correctness

This week, we have moved our attention from recursion to iteration (looping), which is also an implementation of repetition. But the difference is, for iteration, we are also checking that the loop eventually terminates with its work done. Termination means that there is some decreasing sequence of natural numbers, , where i is the loop index. Other than this, it contains pretty much nothing new. The proof procedure is still the same: using Simple Induction. I found no problems with this week's materials.

To continue with what Danny left on the Wednesday slides for the counter example:
Show that 7a(i+1) + b(i+1) = 7ai + bi - 1

Case 1: If bi != 0, then from line 5: b(i+1) = bi - 1 and a(i+1) = ai since a it is not modified anywhere. Therefore, 7a(i+1) + b(i+1) = 7ai + bi - 1

Case 2: If b = 0, so a != 0, then from line 8: a(i+1) = ai - 1, and from line 7: b(i+1) = 6. Therefore, 7a(i+1) + b(i+1) = 7(ai - 1) + 6 = 7ai - 7 + 6 = 7ai - 1 = 7ai + bi -1 (since bi = 0).


ASSIGNMENT #2

I wouldn't consider this assignment to be very hard, but due to the amount of workload from other courses (midterms, projects, etc.), I was not able to start on this assignment until one day before the due date. With help from the TAs, I solved all the questions with no problem. However, I couldn't finish typing out the final copy before 10pm. I left out question #4 unfinished, and this is really going to kill my mark. I assume at least 20% will be deducted... Now, I regret so much on how I wasted my time earlier. Even half an hour more would be enough to save this 20%. =(