CSC165 week12 SLOG:
This week had been a long week, the 3rd assignment is really not easy, and the new materials taught in class were hard to comprehend. For the assignment, the fifth question,∀f,g ϵ Ƒ, f ϵO(g) ∨ f ϵ Ω(g), is very tricky to me, and I did it wrong in my first try,because I did not consider the definition of the big-O and Omega carefully. In the introduction of disjunction, if A is true, then not A or A is True. And I thought big-O and Omega is opposite to each other, then I thought if big-O of this fucntion is wrong, then Omega of it must be right, then I can use introduction of disjunction to prove this claim right. However, there are functions which are oscillating. For example, f(n) = cos n, it is oscillating, it changes it growth rate from positive to negative and then from negative to positive again and again, so it is neither in an big-O nor in a Omega of some functions. Then we should prove the negation of the claim,∃f,g ϵ Ƒ, f ∉ O(g) ∧ f ∉ Ω(g).
In the lecture, we explore further on the computability and introduce a new strategy of proof called induction. About induction, I think the use of it is similar to the way how we write recursive functions for linked list in CSC148. When we write recursive function, we take the first item of the linked list as input, and we need to write a appropriate base case first, then write a case that recalls this function again using the next item in the list as input, then we can get the result of all the items running this function. When we write the proof of the claim ∀ nϵ ℕ, p(n) using induction, we also need to think about a base case first and prove it with the a base number which should be zero,the smallest possible input, in this case, then link all other possible inputs together by finding the relationship between each two inputs. In this case, we can always use the next smallest number (n +1) as new input just like a linked list. Then by proving p(0) right implies p(0+1) right, we know p(0+1) is right also implies p(0+1+1) right, and etc.
-end- :)
