Week 8 - Wost Case?

In this week's lecture we started an exciting new chapter, which is about worst case. Worst case is the measurement of the complexity of a program. It count on how many steps it takes for a program to be executed. There are two types of worst case, the first is the worst case for a program is by finding the upper bound of the steps the program need for it to be executed, and the second worst case for a program is by finding the lower bound of the steps the program need for it to be executed.

As we can see from the picture below, these two cases can be written using qualifiers and implication:

(From course note chapter 4, slide 3)

Upper bound (big-O) is the worst maximum steps the program needs to be executed. where the exist a c and a B, and by showing that if the B is smaller than n implies the worst case of n is smaller than c*n we can find a function which will be the maximum number of steps it takes for the program to execute.

Lower bound in the other hand is the max minimum steps it takes for the program to execute. The only thing changed between this and the previous statement is that this time B is smaller than n implies the worst case of n is bigger than c*n.

To conclude this week's lesion is that to be honest I personally don't quite fully understand this new concept of big-O at this moment, so I can really say that much, but I think as I get more practice I will get a better understanding of it for sure.

Week 7 - Examples of Proofs

In this week's lecture we learned more proof examples of non-Boolean statements, and how to solve these proofs.

Basically the first step of proofing a statement is to assume the antecedent variables, assume all the variables and indent the next line under the assumption so we know its under the world of the assumption. Then we start to solve the proof by listing the content of the antecedent, and gradually work our way thought the equation making it exactly the same as the consequent. The last part of the proof is close all the assumptions, and conclude the result by taking away the indentation in front of the line.

I have also learned a few additional information in this week's tutorial. Things like we only have to make assumption for the antecedent only if its universal, and if the statement begins with the existential symbol we can go straight to writing down to picking the value for the existential variable so it can derive the function for the proof.

We have also learned examples of indirect proofs, this is where we use the contrapositive of the statement and proofing it true so that the original statement is true.

This week's lecture is pretty challenging despite we had a little rest on today's lecture by doing the exercise sheet 'coin in the drawer'. There is many new concepts of proofing that were introduced this week and most of it can only be mastered by practice, and because of the announcement of assignment 2 in early this week I had to get ready to prove some proofs myself sometimes soon, and I am pretty excited about that.

Week 6 - In depth of proofs

In this week's lecture we learned more examples of proofs. We practiced proofs from for equations to implication to proofs with qualifiers. Due to the Thanks giving holiday at the start of this week, this week's lecture is also very short, but we have learned many quite important types of proofs which made this week's lecture by no means easier than the previous weeks. There are many types of proofs which can mainly categorized into four different proof types, direct proof, contradiction proof, negation proof, case proof.

-Direct proof is the simplest, it is where we proofing by assuming the antecedent is true, and manipulate the antecedent into the form of the consequent, proving the consequent is true. There are also a type of statement called existential, we can prove this statement true simply by proving that there exist one value that satisfies this statement.

-Contradiction proof is another type of direct proof, where we just use the contrapositive of the implication or quantifiers to proof the original statement. Because of the contrapositive is exactly the same as the original statement, we can just simply prove it by following the structure of the direct proof. This types of proof is used when the implication does not give us a clear picture of how to prove it, and by using the contrapositive of the original statement it can show us a much easier way of proving the statement.

-Negation proof is used for proving a false statement. The simplest way of proving that is to negate the statement, and by proving the negated statement true it will show that the original statement is false.

-Case proof is a type of proof where it is best proven using different cases. By using different cases and listing all the possibilities down, it can give us a clear idea of what and how to prove the statement. If the statement has two cases, we prove the statement is true by simply proving both cases are true.

Week 5 - Proof Structure and Test!

In this week we started to learn more in depth of proofing by learning proof structure. Proof structure has become pretty familiar to me by now since I am taking MAT137 and they also teaches us how to proof theorems. However it is a bit different in the terms of how each different instructor writes their proofs, so I am a bit confused on which structure should I use on writing general proofs. But I found the proof structure we learned in this class is easier for me to understand the relationships of antecedents and consequent, and it is more of a structure than i have learned in calculus so personally I like this proofing structure better.

                                                            (Course note 3.3)

However due to the term test we are having this week we haven't learned that much new stuff, and I have concentrated all my attention towards studying for test. I have check the previous term test Danny provided us, and I didn't take it that seriously because I though this year's test is going to be something different, so I focused on studying course notes.

After the test we learned more examples of proof structure and that's how my busy week ended.

Week 4- What is proofs?

This week's lesson reviewed some of the things we  have learned in the previous weeks, like the transitivity of an implication, the relationship between 'for all' and 'there exist', we also learned many new concepts, like limits and proofs.

Limits we learned in this class is extremely similar to the limit we learned in MAT137. Limits are very familiar for me since I have aced this topic in high school math. However what I didn't expect were that what we learned here about limits is completely different from what I learned in high school. In here we are not learning how to solve the limit, but rather proof that the limit exist. For me, who is very confident in solving problems using equations find is extremely hard to understand the concept of proofing and how to proof that the limit exist. The two main symbol we have to know is e(epsilon) and d(delta). These are the variables that indicates the distance between the positions on x-y axis that we want to find the limit is and the distance to the maximum accepted value for the limit.

As you can see on the graph, the area box surrounded by dotted line is where the limit are, and the area could be infinity small or infinity large so that it could prove that a limit does or doesn't exist on that area.

The next thing we learned and the most important for me so far is the concept of proofing. Proof is a very abstract concept for me, unlike solving equations it makes me feel that it lacks an absolute answer to it, which makes me feel don't know where to start on solving the proof. 

In order to prove something is true we must use previously proven statements to support our proof. First we assume the antecedent is true, then if the consequent is true the whole proof is true. But if the  antecedent is false, then this becomes a vacuous truth statement, meaning that the proof will be true. Proofs are 'if... then...' statements means we can also use conjunction and dejunction as well as quantifiers.

Here is an example on how to proof:

      Example: for all x in the set of real numbers, if x>0 then 1/(x+2)<3

      Solution: first we try to make the antecedent looks like the consequent.

                          (x>0)=(x+2>2)=(1/(x+2)<1/2)

               since 1/2<3 we can rewrite the equation as  1/(x+2)<3

               thus, this shows that consequent is true when the antecedent is true, proving this proof is                      correct.

However we have to be careful when we do the converse of this statement, although this statement is true, the converse of this statement is false, because x can be -3 and 1/(-3+2)<3 but x!>0.