PWO PCI PSI

For the first two weeks, we have done a lot on those Principles( Well-ordering, simple-induction and complete induction). Today's lecture we actually made those principles more clearly about their relationships. Those terms are essentially all the same. One term can be drived from the others. Those proofs are we have done today, is written in textbook as well, so I don't want to repeat here. It is well worthy to read through, an it will make all those concepts are more clearly. 

Full Binary Tree

The full binary tree question is really about the recursive theorem that we have practiced a lot in the course CSC148. Question is quite simple to answer. 

By using the complete induction, we first need to assume all the node n full binary trees have odd nubmer nodes. Since every internal node of a full binary tree have two nodes. We called them Left and Right respectively. 

Futhermore, as we assumed, the number of node for Left and Right is also odd for both of them. Thus, the total nodes for the full binary tree is simple, 1+L+R, where L and R are number of node for Left and Right subtree respectively. 

As we can see. the 1+L+R = 1+(L+R), since L+R is a even number. Then 1+L+R must be a odd number. Then we end the discussion for this full binary tree question. 

Actually before this lecture, I never think about the connection between recursion and complete induction. I think the more knowledge we got, the more connection we can find. All different course and material are actually connected each other.

Complete Induction

Today we have studied complete induction. Since it still part of induction approach, most of the theories are the same. However, instead of show P(n+1) from assumption of P(n), we need a stronger assumption which means we need to hpy. all the cases before the number n are correct/hold, then we need to show P(n) hold.

A simple way to know a induction is simple or complete is to see if we acturlly need mention P(n+1). Part of this because, I am not sure true or not, there is no need to show P(n+1) hold for complete.

The case we have seen in lecture is a great example to get understand the complete induction. First, there is no easy to induct from P(n) to P(n+1). Second, we need more prerequisite we need in order to induct P(n), which means we need P(n-1), P(n) all down to the lowest cases.

The full tree case is interest. I will discuss it afterwards.

All About Setup

I got my slog setup in Blogger. Last year we use UofT Slog system, however, this year, I checked some students already post their slogs. Surprisely, they all use Blogger. So, I am gonna jump in as well. As you can see this is my first slog for CSC236, really not much course content. I might add up course material later on. Ok, enough for the first slog post.