12th week journal

From reading others' slogs, I know that many of them have taken MAT137 or other intensive math course before. So many of them have already done lots of proofs, and just relearning some of the concepts like limits and induction in this course. I don't have this advantage. Especially when it came to this week topic. Induction is very unfamiliar to me. We continued on the topics of computability and countability. The most important concept here is that countable is listable, So when we say a set is countable, it also need to be listable. Also, there is another techniques for proofs is induction. This technique is used to establish a given statement for all natural numbers. So basically the base case implies the behaviours for all the same behaviour in all the following steps. Those steps are called inductive steps. I am really confused about this week materials too.

And my group has already done the assignment 3. Question 5 was the most challenging question to us and we spent lots of time to it. For question 6, we spent a lot of time understanding this concept together. We followed the structure on course note and slides, and hope it will be correct since it makes sense to us. Next week is the last week of the semester and we are going to do reviews.

Overall, I enjoyed this course a lot. I like the professor and the TA. The tutorials, lectures and assignments helped a lot! And also the piazza!! It is very helpful and I also got lots of hints for the assignments from there. Hope the final will go well!

11th week journal

The week, we were introduced to a function called halt. This is the most confusing topic ever. Basically this is a non-computable function, and it is impossible to write one halt(f.n) that works for all functions f. Halts mean stop. If a function does not halt, it will go into an infinite loop. When I was taking CSC108, I sometimes ran into infinite loops and didn't know the reason for it. It's cool that now I get to know this. We used a technique called reductions to prove this. If some functions f is non-computable, some functions g could be extended to build f, and this is saying if g is computable, then f is computable. The contrapositive of this implication is that if f is non-computable, then g is non-computable. And this is saying f reduces to g. To prove it, we need to use some python codes, and find the contradiction from there. We want the function f(n) halts, then the other function g(n) will return false. This means that f(n) is non-computable, then g(n) is non-computable. The other topic we covered is computability. The sets of  functions are called 1-1 is when each function has its unique variable. This is to prevent over counting. And the sets of functions are called onto is to prevent under counting. The example Danny gave in class helps me to understand 1-1 and onto. He used the first row of students as examples. There were 10 students in the first row, he pointed at each student, their names as a set, and assigned them numbers to each person, and the assigned numbers as another set. This is 1-1 and onto. To violate 1-1, he double counted the third person, by assigning him number 3 and 4. To violate onto, he skipped the third person. This example made me understand this concept much better. But this week materials are still so confusing. Hope I will understand it more after doing the assignment 3.

10th week journal

I found that other slogs are very interesting. Some of the people gave out really detailed summary of the lecture. Like Celina, (link: http://celinasopiniononcsc165.blogspot.ca/), she always gave out examples, and I found it useful to me too! And they usually have some interesting names for their posts too. This week was an extension of big-O, big-omega proofs. We were proving the general case about big-O and big-omega. We are considering not any specific function but all the functions. For proving general cases, we need to think according to the definitions of big-O and big-omega. We first need to understand the statement. For definition of big-O, O g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≤ c·g(n)}, it means that f grows no faster than g. For definition of big-omega, Ω g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≥ c·g(n)}, it means that f grows faster than g. I usually find that it is easier to understand it to translate it into English words and draw a graph of it. And I found that proving that there exists certain functions is in big-O or big-Omega was harder than proving for all the functions, with certain properties.  Because it's hard to come up different equations, and the proofs are not as straight forward as the other cases. 

We finished up the materials about big-O and big-Omega. To conclude, we learnt three parts of the big-O proofs. Proofs for polynomials, proofs for non-polynomials and proofs for general big-O statement. For polynomials, we just need to know the definitions and start overestimate and underestimate the functions. For non-polynomials, we use limits. For general proofs, we need to pick B and c based on known B's and c's.  

9th week journal

This week, we are doing the actual proofs for big O and big omega. Since the definition of big-O is beyond a certain breakout point B, a function f(n) is upper-bounded by cg(n). We use some techniques to prove the function belongs to big-oh. O g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≤ c·g(n)} For polynomial, we first need to look at the highest degree of the function and the relation of inequality to find certain c. In order to do this, we need to analyze if there is any function that will be certainly larger than the function by adding one more degree. To see if a function is belongs to big-oh function, we just need to compare the highest degree. If the function's degree is smaller than the big-oh function's degree, then it is in big-O.Some proofs are more complicated and it requires us to approach it from the top to bottom and bottom to the top at the same time, then they will reach at a certain time that we need to determine c at that time.  Big-omega is the lower bound, meaning the f(n) is lower-bounded by cg(n). Ω g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≥ c·g(n) } For theta, we need to set two bounds. Choose the upper-bound to overestimate the function that we are proving, and choose the lower-bound to underestimate the function. θ g(n) = {f : ℕ à ℝ^≥0| ∃c1, c2 ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ c2 g(n)≤f(n)≤c1·g(n)}And we can choose c to connect these two bounds. For non-polynomial, we use the math tool, limit. First, we need to use L'Hopital's rule to define the limits of these two functions are approaching infinity when n increases. Then we need to translate it into its definition then relate it to the definition of big-oh.

This week material is also about proofs. But I found these proofs are easier than the proofs we learnt before. We can justify it easily and prove it using definition of big-oh and finding bounds. I need more practices of the general proofs because I found the midterm is quite hard. I think I didn' t do that well in this midterm, but I wrote all the structures, hope I can get some marks for that. More practice will make myself get more familiar with different techniques and think more quickly, especially during the test. Sometimes, I know the thoughts but I find difficult to use the definitions to prove it.