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.
Tuesday, December 2, 2014
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！！！
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.
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.
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.
Wednesday, November 19, 2014
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
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)
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.
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
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.
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.
Subscribe to:
Posts (Atom)