Entry 11- last post

Finally, the fall section in U of T ended. Many friends of mine highly recommend me to take CSC165. CSC165 is extremely useful in science course because it trains me how to think logically.

Topics in CSC165 were very new concept to me and they were broken down to:
1. Reading and writing with symbols
2. Logic
3. Proof techniques
4. Growth rate questions such as Big O, Big Omega
5. Counting steps of codes
6. Computable

Overall I really enjoyed learning new concepts in CSC165. It is really well designed course with topics broken down which teaches you mathematical reasoning and expressions step by step. Each topics, I had to fully understand previous materials very well in order to understand the next topic. Although it is CS course I recommend this course to students who studies mathematics but with lack of proving skills.
 
Lastly, I would like to thank my prof. Danny Heap and my TA who helped me out to understand these materials.

Entry 9-Assignment 3

The assignment is due 1st December. The first four questions are not that hard and they are similar to the questions that Danny did in the class.

However, the last two questions are very challenging and hard. First of all, I have to decide whether to prove or disprove the statement. I pick the side of disapproval at first. I try to find two functions such that one does grow faster than and not grow slower than the other function. I try to find an equation that in some interval, one function is growing faster than the other; then in other interval, the one is growing slower than the other. Following this idea, I successfully find that trig functions fully satisfy my requirements. Now the questions becomes that how can I disprove the statement using the two trig functions, sinx and cosx.

I spend 1 hour to prove the negation of given statement. I realize the sin and cos are  not good example. Therefore I give up trig function and try to come up with another examples. Trig functions are continuous functions, and one-piece continuous functions are hard to approach in this problem, so I try to find two-pieces functions that satisfy the condition.

Eventually, I find one!!!! Even though this question takes my 2 hours, I feel it is worthwhile！！！

Entry #10 Reading my peers' slogs

I think this week's materials are the hardest ever. Danny introduced some terminologies such as computability,  diagonalization,  and .countability. I find these definitions are ambiguous and confusing.. When I read my peers' slog, I find that several people have same question as me. They also feel that the materials are challenging.

When I read Matt Cheung's slog, he gives some examples to distinguish well-defined functions from not well-defined function. I feel that it is very clear.

• well defined: x = {1, 2, 3, 4}, y  = {a, b, c, d}

• not well defined: x = {1, 2, 3}, y = {a, b, c, d}
• not well defined: x = {1, 2, 3, 4}, y = {a, b, c}

Danny said that well-defined functions have to be 1-1 and onto. The last two example violate 1-1 and onto respectively. Therefore, they are not well-defined function.

In the Lukas Frantzke's slog, he/she talked about his./her opinion about infinite loop. He/she mentioned that infinite loop is different from long running time. Sometime it is very hard to tell which one the program counters. Last year, when I took csc108, some program that I wrote took more than 3 minutes to run. In the beginning, I thought there was a error in my program; however, it eventually returned a value.

Entry #8- Problem Solving WIKI

Problem Solving Wiki: How thick will the paper be when folding it

Problem: 

measure the thickness of the paper when I fold it

Plan: 

I will measure the thickness of original paper, record the data.  Then I fold the paper once, measure the thickness and record the data.Fold it again, measure the thickness and record the data. I will repeat the process.

Carry out the Plan:

I cannot not measure the thickness of one piece of paper, because it is too thin to measure. I realize that my plan fail. Therefore I re-plan.

Plan II:

I will measure the thickness of 20 pieces of paper(the measurement divided by 20 will get the thickness of one pieces of paper). Then I fold 5 pieces of paper together, and measure the thickness and record the data(the measurement divided by 5 will get the result of thickness of one piece of paper). The I fold 3 piece of paper three times, measure the thickness and record the data. Repeat the process by fold only one piece of paper four times and five times.

Result:

The second plan allow me to measure the thickness of paper. However, there is a significant shortcoming in this plan. The error is extremely big and not neglectable. The error come from two part: measurement and folding. Also, I can only have data up to the 6th fold. I can not fold it anymore. Therefore, I can only check my generalization using first six folding data. 

Entry #7- Big Omega

 I performed extremely well on the mid-term. It was reassuring that a lot of the questions resembled ones we had gone over previously with some minor differences. Also, I was able to score well on the quiz in last week's tutorial, so my results on both evaluations were definitely a confidence booster.

We learned more of boundings  of functions this week. Since, there exist of an upper bound(big O) there should be lower bound for function. This lower bound is called big omega(Ω) and in symbolic form, it is written as

This definition is saying g grows at least as fast as f thus it is lower bound.

The most important part of Big-Omega is also finding c and  b that satisfies the inequality.

When Proving Big Omega, proof structure looks like this.

Let c = __
Let B = __
Assume n ∈ N
     Assume n >= B
       
                  .
                  .    #playing around number until I get f(n)>=c g(n)

          Then f(n)>=c g(n)
     Then n>= B  ->f(n)>=c g(n)
Then  ∃ c ∈ R+    ∃ B ∈ N     ∀n ∈ N    n>=B  ->  f(n)>=c g(n)

Entry #6

We finally got to the topic of counting running time.  Previously in CSC165, we learned how to express with symbols, logics and proof with mathematical background. This week I studied about Big O which is about growth rate. Big O is the symbol that computer scientists use to show the upper bound of function's step. In other words, it is the maximum steps that a function can reach(over-estimation). In symbolic form, it looks like this.

At the first glance, it looked so cryptic and I had no idea what this statement was all about. I have a tendency to get discouraged when I see bunch of symbols that forms a statement. With Danny's help, I could figure out what this statement is all about although it took me some time. First, I looked at statement by parts.
first part is saying that takes natural number as input and returns positive real number. There is constant c which is positive real number and B a natural number that for all n if n is greater than B f(n) is equal or smaller than c * n^2 . B is the natural number that is n's minimum in this statement, and c is the multiplier that makes f(n) always smaller  c *(n^2).

When Proving Big O, proof structure looks like this.

Let c = __
Let B = __
Assume n ∈ N
     Assume n >= B
           Then f(n)
                  .
                  .    #playing around number until I get f(n) <= cn^2

          Then f(n) <= cn^2
     Then n>= B  -> f(n) <= cn^2
Then  ∃ c ∈ R+    ∃ B ∈ N     ∀n ∈ N    n>=B  -> f(n) <= cn^2

Entry #5 -Term Test 2 and counting costs and steps

This week we did proofs and Danny also introduced more proof structures. I felt that I was so lucky to take 165 this  semester. 165 helps me a lot since most of questions in mat237 are proofs. By writing down the proof structure that Danny taught us, I could focus on the few part which I get stuck on. I could have a clear picture about proofs. 

We did a formal proof about limit this week. Instead of graphing it, we wrote down the whole proof structure. I found it was more easier to understand in this way rather than the way we did in mat137. The things we used or we assumed were written in the comments. I finally understood why we had to choose the minimum number of the two. Since d is the number that we could control, I could choose any number that we want. 

The review on the proof was helpful as well. I was kind of looking forward to taking the term test 2. 

In lectures, we learned how to calculate the steps of an algorithm. I heard that from somewhere else that efficient algorithm sometimes saves billions of dollars in industry, also sometimes saves life. So, it is so important to calculate algorithm's step. 


There is rule of counting step of each of these actions:

method call: 1 step + steps to evaluate each argument, + steps to execute the method.
return statement: 1 step + steps to evaluate return value.
if statement: 1 step + steps to evaluate condition.
assignment statement: 1 step + steps to evaluate each side.
arithmetic, comparison, boolean operators: 1 step + steps to evaluate each operand.
array access: 1 step + steps to evaluate index.
member access: 2 steps.
constant, variable evaluation: 1 step.

Entry #4

This week we did more proofs. It is very challenging but interesting. However, I did have hard time understanding the proof of prime number, because there are many underlying math knowledge.

If I came across this problem for the first time, I could  think of using proof by contradiction. The general structure and first few steps were easy to come up. However, I would definitely get stuck on the fourth line of the proof. I had to know that prime number starts from 2. I felt this comment was not understandable, because I did not know why we could use this fact without proving it. There were more lines that I was confused with. The comment in the line 6 was not a fact that I could come up by myself. 

The question that bothered me was that I did not know what math knowledge that we could use for granted, because I felt like other than some basic algebra knowledge, I had to prove anything in 165. 

I tried to figure out a another way to prove it without using those facts

Plan: prove by contradiction, and get some result that is contradict to a fact

Carry out plan:
Assume there is finite prime number
           then p1,p2,......pk are prime numbers
           then  (where I get stuck)

Result
I could not come up with another to prove it. Therefore, I chose to understand the way that Danny gave us (sad!)

Entry #3

The first term test carried out this week. I went over all the class notes, quizzes, tutorial problems, and past paper. Even though I was nervous, I felt not that bad when I came out of exam center. This year test was pretty much like last year’s, and they all had same structures and questions. Fortunately, I did past term test twice. Everything went smoothly, and I had enough time to check my answers.

Speaking of this week‘s lecture material, we started a new topic this week: proof. The first proof was a limit proof. Danny showed the steps of proof on the graph. It was very clear and interesting. Even though it was a little challenge, it was very interesting.

I did not get the structure of proof at the beginning; however I tried to remember how it worked. When I went over the notes, I finally knew the reason why universal quantifier implication’s proof should have the structure as following:

Assume # x is generic

    Assume antecedent

        then consequence

    then antecedent implies consequence

then for all x, antecedent implies consequence

Indentation helped us to have clear picture of assumption, and under which world we were working in. I had more confidence in proof. 

Entry #2

The first assignment is all about logic that is covered in chapter 1 and 2. Since I have learned most of logic symbol and logical rules in MAT137 last year, in general the first assignment is not that hard for me. However, there are few questions which bother me.  First, since Danny asks us to type the assignment in a pdf or a word, I find that it is hard to type the logical symbols. I spend almost one hour trying to figure out how to type them in a word document. Finally, I find there is a feature called equation, which allows me to type all the symbols. It is very helpful and convenient. Second, the fourth question takes me some time, since I feel it is difficult to find a counterexample.

 First step, I try to find difference between the two statements.

Clearly, the first statement is an implication, and the second statement is a conjunction. If p is true, then Q is true. If P is False, Q is also true. However, P is false, then I can immediately conclude that the conjunction is false, because conjunction is false when there is at least one predicate is false.

After I analyze these two statements. I can solve this problem by finding an example that P is false and Q is true.

Logic is very interesting and I enjoy spending time solving logical problems.

First Post

This week we did more proofs. It is very challenging but interesting. However, I did have hard time understanding the proof of prime number, because there are many underlying math knowledge.

If I came across this problem for the first time, I could  think of using proof by contradiction. The general structure and first few steps were easy to come up. However, I would definitely get stuck on the fourth line of the proof. I had to know that prime number starts from 2. I felt this comment was not understandable, because I did not know why we could use this fact without proving it. There were more lines that I was confused with. The comment in the line 6 was not a fact that I could come up by myself. 

The question that bothered me was that I did not know what math knowledge that we could use for granted, because I felt like other than some basic algebra knowledge, I had to prove anything in 165. 

I still work on this proof and want to find a another to prove it without using those facts.