Okay, maybe today isn't the clearest of days. Well, it's raining. So then what did I mean? Last week marked the end of several tests and assignments! But naturally, this next week means 5 more quizzes, 1 assignment and another term test. Hurray for me.
Anyway, Wednesday was the CSC236 term test and I went into it with ~1 hour worth of studying. Having said that, the previous week I had read through the textbook and made my own text document that highlighted each of the four methods of induction - I even wrote about this last entry. Therefore very minimal reviewing prior to the test was needed. I do feel this was an appropriate approach to the test considering that most of the content is learned through application so solving problems and understanding the material way ahead of time is extremely effective. Plus it leaves me time to relax and sleep the night before a test while others struggle and panic.
Being part of the evening lecture, I was surprised to hear from my day lecture classmates that there were only 3 questions. This made me wonder which type of induction would be missing from our test. What an interesting turn of events it was when I discovered that only Mathematical and Complete Induction were on the test. Needless to say that those two inductive methods were the ones I knew the best since I have years of experience using them. Plus they were the first ones learned in class so naturally they'd be the easiest. In general, the test was much simpler than I had anticipated - but you won't hear me complaining.
The second question on our test took the form of CI on Binary Trees. Luckily binary trees have very few inductive properties, the main one being that a root's children both form smaller subtrees. Thus we can use the subtrees with Complete Induction making this problem simple. Since the root's two children can each form a new tree with less than n nodes (n being the number of nodes in the entire tree), we know that they both contain exactly one more node than edge. Thus when we combine the two trees, we have exactly two more nodes than edges. Add in the root node gives us +3 nodes, but the 2 edges that connect the root node to each of the children gives us +(3-2) nodes. Thus we have exactly one more node than edge in the large giant of size n. Thus given that there is exactly one more node than edge in all full binary trees of size i such that 0 < i < n, then there is exactly one more node than edge in a tree of size n as well.
So moving onto the next task I suppose... Maybe it'll be more challenging.
-ラムダ
No comments:
Post a Comment