Leaving Toronto for awhile!

Since there's some personal issues, I will be leaving Toronto for about 10 days. That since Blogger does not work in China (blocked like facebook and youtube), which means I will not be update my SLOG for about 13 days. See you all when I am back!

Some thoughts after the midterm

First of all, I have to say reading the questions carefully is more important than understanding the question. e.g. Q2 on the midterm, the question was asking number of leaves instead of number of total nodes in the tree, which makes the question lot easier by only asking the lowest level of the tree. From the observation, the worst-case is when we have a full binary tree, where it's lowest level always has 2^(n-1) leaves.

Second, any non-full binary trees will be smaller than full binary trees, therefore we can prove in both cases, P(n) is true!

Finally! My first SLOG update!

After a long and busy week, finally, my SLOG is here live! Assignment #1 of CSC236 was extremely hard, which is mainly because I was trying to "prove" or "explain" everything instead of writing down a clear and easy understanding idea. Already, jump right into the topic: such as question 4 on the assignment, " use complete or mathematical induction  to prove that any binary string that begin and ends with the same bit has an even number of occurrences of substring from {01, 10}."

Prof Heap has mentioned that he prefer mathematical induction in class, so I tried to think in that direction, and then came up with the following:

P(n): any binary string n, if its first digit n[0] is same as the last digit n[-1], then it has even number of occurrence of {01, 10}. (IH)

Proof (by Complete Induction)

Special Case (Base case): When len(n) = 0, then length of the binary string n is 1, which implies that n is a single-digit string {0, 1}. Since a single-digit string can never include {01, 10}, so that the occurrence of {01, 10} is 0, which is even.

E.g. S = 1 or S = 0.

Induction Step: Assume len(n) > 0, and that for every natural number 0 < j < len(n) then (n[:j]) is true.

Case 1: n[0] = 1 and n > 0: then n[0] and n(1) both {0, 1}.

Subcase 1.1: n[0] = n[1] then since n[0]= 1 (mentioned in Case 1), then n[1] = n[0] = 1, which gives the first 2 digits of n is “11” that ∉ {01, 10}, so the first two digits of the binary string n contains 0 of {01, 10}. And we slice n = n[1:] , then move onto the next digit

Subcase 1.2: n[0] ≠ n[1] then since n[0]= 1 (mentioned in Case 1), then n[0] ≠ n[1] = 0, which gives the first 2 digits of n is “10” that {01, 10}. so the first two digits of the binary string n contains 1 of {01, 10}. And we slice n again so that n = n[1:] , then move onto the next digit

Case 2: n[0] = 0 and n > 0: then n[0] and n(1) both {0, 1}.

Subcase 2.1: n[0] = n[1] then since n[0]= 0 (mentioned in Case 1), then n[1] = n[0] = 0, which gives the first 2 digits of n is “00” that ∉ {01, 10}, so the first two digits of the binary string n contains 0 of {01, 10}. And we slice n = n[1:], then move onto the next digit

Subcase 2.2: n[0] ≠ n[1] then since n[0]= 1 (mentioned in Case 1), then n[0] ≠ n[1] = 1, which gives the first 2 digits of n is “01” that {01, 10}. So the first two digits of the binary string n contains 1 of {01, 10}. And we slice n again so that n = n[1:] , then move onto the next digit

    Since binary string n contains 1 of {01, 10} every time there is a different digit in the string, and I assume P(n), which means n[0] = n[-1], and it has to have ∃x ℕ, there are 2x times of occurrence of digit that is not the same as n[0]. In addition, if n[0] = n[1] = n[2] = ··· = n[-1], there will be 0x times of occurrence of digit that is not the same as n[0]. Which 2x and 0x are both even numbers. I conclude that for all non-empty binary string n, P(n).

And as you can see, I used the complete induction instead, which result in having a loop case in the proof! I wish I can find out where it went wrong.