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. 

5th week

This week, we get to proofs! We have different approach for different proofs. For proving universal, some proofs are easier to prove using contradiction, others are easier using contradiction. Because to prove a universal, we cannot have any counter examples. For existential, we need to find out at least one example to prove it.

Proofs seem like the most challenge material for this course. It requires lots of thinking. We have to believe the statement and understand the statement in order to prove it. The thinking part comes from practice. So doing lots of practices will help me to think faster. And I think the very important thing for me to do is to get familiar to the math definition. Since I forgot those math terms, it will trouble me a lot. Like prime numbers, R set, N set, etc.

And for the midterm, the most challenge thing to me is the time, because I am not a fast-thinking person. So in that short amount of time, when I was nervous, it made me think even slower. But after all, I finish all my questions. I think the lectures, assignments and tutorials are important, because this course is more towards understanding than memorizing.  And lectures, tutorials and assignments help me understand the materials well. 

4th week journal

The materials are getting harder and harder. This week, we learnt mixed quantifiers, bi-implication, transitivity and the basic proofs. From mixed quantifiers, I knew that the domain of a set is really important. The order of the quantifiers matter a lot, when there are a combination of universal quantifiers and existential quantifiers. For transitivity, this is important for proofs. Same as math, if a>b and b>c, then a>c. For proofs, we learnt the format for writing the proofs, and the starting steps when we first see a proof.

The proofs seem troubles me a lot, because I didn’t understand the example that was given out in the lecture today. I will try to understand it or ask it through piazza. Other than the new materials, we finished our first assignment. This assignment is harder than I thought it would be. Because I studied the materials before doing the assignment and I thought I understood everything. However, when I was doing the assignment with my group, I found that I didn’t know the materials that well. Especially when it comes to venn diagram and the existential statement. I will focus more on these materials while I am studying for my term test.  After doing this assignment, I found myself have a better picture of how everything we learnt links to each other. Doing the assignment in a group is better than doing it individually, since everyone will give out their own opinions and discuss. This is more interactive and I learnt a lot from my group mates. 

We also did a problem solving problem in class this week. It is called folding. We first need to understand the problem. So the purpose for this problem is to predict the sequence of ups and downs for any number of times that we carry out the folding operation. The ups and downs were accounting the creases point vertex up or down. Second, we devised a plan. We decided that one of people would do the folding and the other two would do the recording, so that we could compare our records and avoid mistakes. From our knowledge, we know that the paper can be only folded 5 times. Then we started doing the folding after all the planning. The first 4 could be easily read, but when we folded the paper the 5th time, the ups and downs are hard to distinguish and we checked it over and over again. After we got all the data, we started finding the pattern, since we could not fold the paper again. First, we counted the total number of each fold. The total numbers of ups and downs are 1, 3, 7, 15, 31 accordingly. And we found that the total number of each fold was different by 2 to the n powers. Then we were stuck when finding the patterns of ups and downs. Danny then told us to flip over the paper to look at the hints. After looking at the hint 1, asking that ' is one pattern somehow 'contained' in the other, we suddenly realized that the 2nd fold actually contained the sequence of 1st fold, and the 3rd fold contained the sequence of 2nd fold as its last portion of sequence, and so on. After looking at the second hint, suggesting that we could organize the fold patterns symmetrically. We looked back and carefully rewrite the patterns symmetrically. We finally found the pattern! This was actually a fun problem and following the problem solving steps made the thinking process more organized and clear. 

3rd week journal

This week, we learnt more symbols of the language of Math. ‘And’ and ‘or’ are two words that we use very often in daily life. In math, ‘and’ is called conjunctions, which has a similar meaning to natural language. ‘Or’ is called disjunctions and has a different meaning from natural language. In natural language, we usually give two choices and use ‘or’ to connect them, this is an exclusive or. But in language of math, ‘or’ is an inclusive or. Negation is easy to express when it is in natural language because I just need to add a ‘not’, but it becomes a bit more complicated when it comes into language of math. Since adding a negation to a sentence with a combination of conjunctions, disjunctions and implications, we need to apply laws to change it properly.

It’s hard to memorize all the laws, and understanding the laws will make me remember them better and longer than just memorizing them. To me, using different examples is the easiest and most efficient way to understand the laws.  From my experience from PHL245(modern symbolic logic), practice is the key. I am going to do lots of practice during the weekend. And I found out that the interaction in class is pretty important too. Because it will help me to think more if I interact more in class. 

CSC165 2nd week journal

In the first two weeks, I knew that programming language is very precise and logical symbols are used to prevent ambiguity. The two quantifiers in logical notation are universal quantification and existential quantification.  To disprove an universal quantification, there simply needs to exist one exception. To show that something exists, simply find one case where the property applies to one instance. Implications is one of the forms of a sentence. If I study hard, then I will do well in this course.  And the converses, contrapositive of the implications have different meanings from the original implications. While equivalence means antecedent implies consequent and the meaning is the same the other way around.

These are techniques we are building up to solve proofs later on in this course. Proofs will be formalized and presented in not only a precise and accurate manner, but also logical.  

Although human language may be ambiguous at times, it is more intuitive for solving problems. It is then translated into symbols to reason more precisely. This is the background I come from, as I took PHL245 (modern symbolic logic) before, that was when I found myself really interested in symbolic logic. I am not a computer science student, but I am looking forward to learning more from this course because it is interesting. From this week’s materials, since I have learnt the logical notations from PHL245, so converting English sentences to symbols is something I am familiar with. Different from PHL245, this course is more towards mathematical expression and reasoning.  This is something I have to work on more. I am going to review the related material from the course notes during weekend and try to understand the material better.