WEEK 11&12

Since brief fall break in week 11, therefore, we did not have lecture last week, which gave me a period of time to recall and to summary what we have learnt before.

What I Learnt

This week we mainly covered computability, countablility and induction.

Computability

    Computability problem was the most difficult part I felt in CSC165. In order to overcome it, I went to both Denny and Larry’s lectures about this part. I have to say, different ways in teaching this part really inspired me a lot. After class, I reviewed the slides and added the notes I wrote myself. In addition, I also communicated with classmates about how they understood computability and saw their slogs on the website. I found the course notes that Yahui Liu posted is really a helpful supplement to the slides and also improved my understanding to this part. (http://yahuiliuslog165.blogspot.ca/2014/11/week-11.html).

Summery:

We use reduction to decide whether it is computable or not

f reduces to g

g computable implies f computable

f non-computable implies g non-computable

a)    Want to prove a function computable: show this function reduces to a function g that is computable.

b)   Want to prove a function non-computable: show that a non-computable function f reduces this function.

This is a typical example:

Interesting Part: Countablility and Induction

I was so surprised that there were so many parts overlapped with other math courses. In countablility, the definitions of 1-1 and onto I have learnt in MAT223. Besides, the proof technique--induction was also an important content in MAT137. I felt happy and interesting because all the knowledge is relevant and interact each other.

Achievement about Assignment 2

     I was so exciting because I got 100 in A2, which was unbelievable. It was my first full mark and would be a milestone in my campus life. My effort was rewarded, which, in a large extent, encouraged me to do better in the final exam and further study.