Well-Ordering and Structural Induction

Professor Heap talked about Well-Ordering and Structural Induction in the third and the forth week. I had never heard of either of them and found them a bit confusing at first. I thought Well-Ordering was some kind of a proof technique and I couldn't figure out what it really means. However, after I spent some time reviewing my notes and examples presented in class, I learned that Well-Ordering is just like a fact: every non-empty set of positive integers contains a smallest element (http://en.wikipedia.org/wiki/Well-ordering_principle), and we refer to the fact when proving another statement.

Structural Induction seems like a kind of Simple Induction / Mathematical Induction to me. It's just that it deals with operations of two elements, so it didn't take too much time to understand.

Strong Induction vs Complete Induction

So Professor Heap talked about Mathematical Induction and Complete Induction during the first weeks. Although I've done tons of Induction proofs, I've never heard of Complete Induction, so I looked it up on Google, and it seems to be just a different name of Strong Induction (http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction). Nonetheless, the structure of Complete Induction used by Professor Heap and the TAs is different from the Strong Induction I know. As far as I remember, you need Strong Induction only when one base case is not enough.

Example (taken from quiz#2): Prove that you can make n cents using only 2-cent and 3-cent coins using Strong Induction.

BCs:
n=2: use a 2-cent coin
n=3: use a 3-cent coin

IH: Assume P(2), P(3), ..., P(n) true

IS: Want P(n+1) true.
n+1 = (n-1) +2

Since n-1 >= 2, we can use IH: P(n-1) is true
By IH, we can make (n-1) cents using only 2-cent and 3-cent coin(s)

Thus, we can make (n-1) + 2 cents using another 2-cent coin.
Thus, P(n+1) is true as needed.

Conclusion: blah blah blah

The structure Professor Heap uses seems to put the Base Cases into one case in the IS (Induction Step), which confused me at first--it seems like a Proof by Cases in a Mathematical Induction. To me, I think the structure of Complete Induction / Strong Induction should be similar to that of Mathematical Induction as possible--it should be more intuitive that way.

My First SLOG

Hello World!

I'm required to write my SLOG for csc236. Personally, I'm not very happy with this kind of assignment (see, I'm honest). It would make more sense if this was a research project or something that requires feedback from the professor or other classmates, but we will see how it goes.

A bit about myself: I'm a third-year, transfer student enrolled in the CS Specialist program. The reason I'm taking this course is because the transfer credit center at UofT didn't grant me the credit for the course, and it's mandatory for the specialist program. Anyhow, I'm taking this course and, hopefully, I will have a better grasp of the material by the end of the course.

So far, I have not seen any material taught in this class I'm not familiar with, and so the assignment and the first two tutorials were like a review to me. I will be talking about my reaction/opinion to the concepts of the material in the next entry.