Thirteen Week

                                   24th ~ 28th

•   Countability
•   Induction

  Countability is really a difficult concept to understand. Although I've thought about it with referring to Dr Heap's and Dr Larry's slides. I still have some trouble to loo deep inside it.
  My understanding is that if you can find some ways or methods to creates a responsibility of two sets one as input and the other one as output. With the dint of one-to-one and onto, we can compare every functions with nature numbers' set which is acting like a criteria for determining other sets' countability.
  Besides, Induction is familiar to me as it is a very powerful method in matehmatics. We can use it to prove some very weird and interesting mathematical properties not only in math but also in CS.
  To my mind, CSC165 really inspired me a lot about CS and lead me to explorer many interesting aspects of it. Thanks for Dr Heap and Dr Larry and all TAs, they really do an excellent job.

Twelfth Week

                                 17th ~ 21th Nov

• Introduction to computability
• Reduction
• Finite Sets and Infinite Sets
• Countable ---- |N|

  'computers cannot solve the halting problem'.

  It is really confusing when first see this. But computer just know using the algorithm to compute again and again. There is no ending to a finite loop but we could not deny that there may be a end with time moving.

  Hence,Halt(f,n) is non-computable. Hence, to us, if we want to prove a function is computable or non-computable, we need the help of another already known computable or non-computable, which is called 'reduction'.

  The concept of finite and infinite is also interesting. For example, natural number and natural even number has infinite elements but do they share the same size? Actually, I am not really sure about there relationships. I think as to two sets P and Q. If we could say every element in P is one to one to Q, and P -> Q is onto if for all elements y in Q, there is at least one element x in P that f(x)==y.

Tenth Week

                               3rd Nov ~ 7th Nov

• O(n²) 
• Ω(n²)
• ϴ(n²)

  "when finding upper-bound, it is OK to over-estimate the number of steps"

"when finding lower-bound, it is OK to under-estimate the number of steps".This two sentences are very useful in dealing with such kind of finding O problem, which should always be kept in our mind.

This problem and solution really make me learn a lot. If we want to make aconnection between two steps we could overestimate one and underestimate the other and choose a c that could reveal their relationship explicitly with <= or >=.