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.