CSC165 Week12

Finally, we are here, the last week of this semester, cheers!!!

We covered countability and induction in the last week. For the countability part, we got a very tricky question at the lecture. It asks if X={natural numbers} has the same size as Y={even natural numbers}. Intuitively thinking, X contains 0,1,2,3,4,5...... and Y contains only 0,2,4,6.....so X's size is larger than Y's. BUT, THAT IS WRONG!!!!  In fact they have the same size! It was quite confused to me but it make sense after Larry's explanation. We can think in this way, say X={number of coin in the world}, Y={number of tail of coin in the world}, then it is easy to see that these two sets have the same size, since each coin has one and only on tail, so the number of coin must be equal to the number of tail.

The second part of lecture involves the introduction of induction. Induction is a very important tool in mathematic proof. When we get several special case for some NATURAL number, we may possible to prove some properties for all natural number. This is called the induction, The following is an general example in class.

The last part of the lecture was about the review for the final exam.

That's all for week 12. Good luck everyone on your final exam!!!

CSC165 Week11

There was no class for my section since we had a fall break. Not too much to say about week 11 here.

CSC165 Week 10

We finished about the proof of big-Oh and big-Omega. Here is a short summary of chapter 4 about those proofs:

1. Definition of big-Oh, big-Omega.

2. big-Oh proofs for polynomials(standard procedure with over/underestimates)

3.big-Oh proofs for non-polynomials (need to use limits and L’Hopital’s rule)

4. proofs for general big-Oh statements(pick B and c based on known B’s and c’s)

 We also started chapter 5 this week. It's about the computability. For anything that in order to be computable for computers, that function can only go through by finite times. It can not be infinite. If the function is supposed have infinite loop inside, the result will never be computed. 

CSC165 Week9

For this week, we started the proof of 'big-Oh' of polynomials, non-polynomials and limits. The proof structure is the same as we used before but with much more details in it.  It involves a lot of application of math which means it is not that easy to see how to do it, since some math stuff can not be used directly.

For those function in form of polynomial the proof is kind of easy. Basically is find the upper-bound of the left side by overestimating and find the lower-bound of the right side by underestimation and then choose a c that connects the two bounds. For disproving, it just the same as what we've done before, prove the negation of the original statement.

For non-polynomials we need to use limits to prove the big-Oh. The steps are follow:
1. Prove the limit of the function is infinite as n goes to infinite. This step may involves using the L'Hopital's rule.
2. Translate the limit into its definition.
3. Relate it to the definition of big-Oh.

CSC165 Week7

This week we learned more proofs. They involves more rules and many other concepts. The proofs covered in this week are more and more detailed.

For most of mathematic proofs, the key thing is to understand the definition we are given.Then try to derive something that has the same form of the definition. For example

In the above example, we have 7(7i^2+2i)+1. We have to see that is the same form of 7k+1, just for k=7i^2+2i. The idea is the same as picking delta wisely for the last week's proof.

CSC165 Week 6

It looks like most people did very well in the midterm test. Cheers!

This week we learned more about the proofs. Proof of some mathematical things are not that direct, especially for some limits. For those kind of proofs, we need to understand what does limit mean in mathematic. Then, in order to prove it, it is necessary for us to pick delta wisely. 

Disprove something is the same as prove the negation of that. That is quite straight forward for me.

Since we only had a two hours lecture and no tutorial this week..I guess thats all for this week.

CSC165 Week5

Took 2 hours lecture after the test is so tired but start learning proof is exciting. Especially the one given in class showed that 'it is not bad even if you left everything blank and others did well'. You are much better than this if wrote something in the test.

There are several ways of thinking about proof. I believe that in most cases it is not that easy to show something directly, therefore we have to come up with some alternative ways, such us using contrapositive, contradiction. For example, to prove P=>Q is the same as prove ~Q=>~P, because we know that the contrapositive is the same as the original statement in logic. Here is the proof of that
(~Q=>~P)=>(Q or ~P)=>(P=>Q)

Another way of proving an implication statement is by using contradiction. To use this we need to assume the negation of the statement is right, then derive some results based on these assumptions, if some of them contradict each other, it means our assumptions are wrong which is the negation of the original statement. Therefore the original statement is true.

The last part of the lecture was about proof for existence. It seems easy for me because once we can show one example then we can finish the proof.

Hope everyone get a great mark for the test.