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.

8th week journal

This week, we learnt the algorithm of insertion sort. We derived the exact form of the W(IS) and determined the upper bound and lower bound. We learnt how to prove the time complexity of the insertion sort. First, we need to analyze the sorting method and define the worst case. 'O' is the upper bound and the 'Omega' is the lower bound.

We need to get familiar with how the sorting methods works and practice a lot of proofs. I found that analyzing the steps that we are going through the sorting methods are hard. But once I get familiar with the sort and the knowledge with the 108 of python code, I think it will become easier. And proofs need a lot of practice. I think after I finish the assignment 2, I will get more familiar with the techniques that I can use in the proofs.

7th week journal

This week, we learnt more techniques for proofs. Proofs by cases are sometimes handy when I am stuck at certain proofs. The cases are required to cover everything in the sets, and start proving it using the given definitions. We also learnt the introduction rules and the elimination rules. And it comes to an end to the proofs and we get to touch on some more complicated materials--algorithms. Running time is the most important factor when computer scientists decide which algorithm to use. 

For proofs, I need to do lots of practices and start from finding certain pattern. I can use the rules to keep trying. This will make me get closer to the target. After two weeks of proofs, I found proofs are not as hard as I thought before, maybe because I practice a lot and I learnt more techniques for the proofs. For algorithms, this is important in computer science. We can sort a list using different algorithms. Like bubble sort and merge sort. Different sorting algorithms take different amount of time. Some have more steps than the others. Once we have a super long list, we would want to use the algorithms with less steps, because that will save lots of time. I need to get familiar with how each algorithms work before analyzing it.

6th week journal

This week, we learnt proofs. Proofs require lots of thinking. We learnt how to prove a non-boolean statement, how to disprove a statement, and proof about limits. A non-boolean statement is usually likes a function. Not a equation that returns true or false. A typical non-boolean function is the ‘ the floor of x’. We cannot apply quantifiers to this non-boolean function.  And to disprove a statement, we just need to prove the negate form of that statement. To prove a limits, the order of quantifiers matter a lot. I can always think that given such statement, how I can choose a statement to win the statement.

The proofs are challenging, especially the proofs about limits. The proofs have specific formats, so I think the first thing I need to do is to get familiar with the formats. The most important thought about proofs is that I have to understand the statement clearly and need to believe the statement is true. By following the format, then I need to practice a lot to improve the thinking. There are many ways to prove a statement, so practice will help a lot. And I believe there are some patterns for proofs. Like proving an implication, while choosing the arbitrary numbers or functions, we can also do the latter part first then come back to this function. Because it’s easier and more accurate that way.