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 >=.

Ninth Week

                         27th Oct ~ 1st Nov  

•    BIG O
•    O(n²)   
•    Ω(n²)                     

  This week，we learn more about Big O. How to find a expression about the worst case's steps of a function is the most important step, which needs us to analyse the function like a computer. We can first come with some simple cases to grasp a general idea of how this function works.
  Besides, we learn about what's is Ω，O. O is the upper bound of the worst case's steps and Ω is the lower bound of the worst case's steps. With the help of algebra, I can easily find the corresponding constants of Ω（f(n)), O(f(n)). In general, the total process is to find  the upper and lower asymptotes of a function in math.

Eighth Week

                                 20th~24th Oct

• Inferences
• Introduction of Sorting strategies

  This week, we still work on the proof of statement with mathematical expression.

 Besides, we are given many allowed inference. Conjunction elimination, existential instantiation , disjunction elimination...There is so many and their names is a little bit of hard to memory.But I understand their meanings and working conditions. So, I just need to take some time to remember their name.

  With the help of 'euchre'(It seems to be a card game, though I never play before), Heap wants to induce us to think about the concept of sort.
   What sort method can you think of?
   What's their difference?
   Which is more efficient?
  I know three searching method - bubble sort, selecting sort, merge sort. I think they are similar to the ones listed on the slides - insertion sort , selection sort.What we are required to emphasize on is the 'steps' that every sort method need. By myself, it is similar to say the efficiency of every sort method. The steps we now looking on is the total steps when using a sort method to solve the worst condition. And we can denoted as O()(We call it 'BIG O'). And to a computer scientists, all quadratic functions are the 'same' - they are in O(n^2)

     

Sixth Week

                                13th~17th Oct

• Mathematical expression

  This week, we follow Mr Heap finishing many different examples of proving statement with mathematical expression.

  By using many tricks, such as changing to prove the contrapositive, making a header and conclusion first, etc.

  The most important is that we must pay much attention to prove with rigorous logic order, which means we have to state every domain one by one including their own quantifiers. To the domain with universal quantifier, we need to note that the variable is generic. Besides the domain with existential quantifier, we need to note that we pick it and it equals to something or has some special features.
  When it comes to the most key part of proof---assuming the antecedent and proving it can imply the consequent. Sometimes, the process does not go very smoothly. At this case, Heap tells us not to be hurried and panic, write down every small steps you could think of, keep it in your mind taht what conditions you have not used and think about it how to use it in your proof.
  Last but not the least, the indent is also very important. Every time you assume something at the header of the proof. You need to indent and continue the next proof. When finishing proof of the following part is right under the condition of the assumption, you need to echo the assumption at the end of the proof. 

Fifth Week

6th~10th Oct

•  Structure of systematic proof

  This mid-term test worried me a lot before. But I really put a lot of efforts in this course. So, the answer won't makeme disappointed.
  This week，Heap teaches us to use systematic and rigorous proof structure to proof some statements. As to me, the most important part is prove with step by step. To every step, we need to clarify the reasons. It is really interesting like we are simulating the execution of computer. I believe the requirement of writing reasons is also teaching us to write annotations when we program.

Fourth Week

Sep 9th - Oct 3

• Transitivity
• Order of quantifiers

  Transitivity provide us a tool to make connection between several different statements' relationships.

Just as this statement, If the both sides of Conjunction sigh is true, we can deduce that by drawing a Venn diagram.

  Besides, I learn that the order of quantifiers may cause a big difference to the correctness of a statement.For example, (S1=S2={1,2,3,4})

To the two statements, the up one is true but the bottom one is false. Heap uses a smart instance to reveals the difference of them. If a very worst people want to make a gamble with him, the bad guy say 'if I choose a arbitrary number is S1 could you find a element in S2, that x+y=5.' Heap says 'of course'. Why Heap is so confident because that every time Heap's choice is depending on the bad guys choice. Conversely, if the bad guy wants Heap to choose first, Heap will lose too. The story just want to tell us that the order of the quantifier also carries some logic meanings in it. Hence, we could not use them casually.

Third week

                          22th ~ 26th

• laws of arithmetic in logic and set operations
• Process of solving problem

  This week, combining with the working on the Assignment 1, I gain a deeper understanding of implication, negation, conjunction, disjunction...several concepts and how to translate an implication from English languages to symbolic language and the reverse.

  The laws of arithmetic in logic and set operations is really cool, which teaches us to transform expressions of relationships between two statements like manipulating multiplication. By drawing Venn diagrams, we can prove them true.

  At Friday's lecture, Heap says no one in this University teach how to solve a problem systematically but he wants to teach us about it. He tells us to work as a team to investigate the changes of the pattern of little folds of a strip when being folded with the times increasing. It seems not very hard, but when we work on it with the solving steps that learned we find there are many things that worth thinking and learning.For example,What are the input and output of the question? To my mind, input is folding a strip and make it has several upward and downward folds.Output is to find the regularity or traits that can account for the results of every time's folding. Besides, when we write down every times pattern, how to make it more explicit for us to find regularity is very important.I choose to let '0'means upward and '1'means downward, which helps me to gain a comprehensive version of the problem in order to reduce the subtraction of distinguishing up and down signs. In addition, I make every sequences of figures to the middle alignment which can help to analysise the pattern from different sides. After trials and errors, I find the regularity. This exploration really teach me a lot. As Heap says, it is not the result but the process that makes you learn the most.

Second week

                                           15th 

• implication 
• boolean function 

  Today, it begins with quantifiers with many exercises. It is a little bit confusing sometimes even Heap made a mistake.
  Then, we learn to use a boolean function to reveal a relationship between two sets which is more brief and familiar to python in other words computer than using mathematic symbols ∈ and ⊆ . 
  At last, Heap uses an order that his mom used to talk to him in his childhood" If you eat your vegetables, then you can have dessert" as a example to clarified that if the antecedent is false, then no matter the consequent is true or false the implication is always true. So, It is true that he could do not eat vegetables but to have dessert. This white-haired man is really cute , still looked like a innocent children. 
  This concept is a little bit difficult to understand. Heap does not make explanation because of time. I have been taught this concept in MAT137. The teacher says if the antecedent is false, there is no valid condition for us to show the consequent true or false which is called vacuous truth.I hope Heap could make a explanation in the next lecture because I hear many classmates talking about this after class.
                                   

                                     16th(Tutorial)

• Meaning of "Some"

  The TA Madina is a cute girl, who leads us to review the knowledge of set learned in Lectures. Because of preparation of the tutorial material, I found it easy to follow Madina's words. 
  Although there is no new or hard something to learn, it answers a question that always bothers me.Before the tutorial, I always thought that "some" means "At least one but not all" and the fact is "Some" just means "at least" .Hence when drawing the Venn Diagrams, I always think about one more situation than others. 
  The question bothers not only me but some other students who raise the misunderstanding in the tutorial.  I guess it derives from my primary  English education. When I learn English words, I will awkwardly and directly translate English word into my mother language. "some" in Mandarin is the meaning of "At least one but not all". Luckily, the little but can not be ignored mistake has been eliminated now.


                                      17th

• Implication, Conversee, Contrapositive
• "Natural" Language(P => Q)

  At the beginning of the lecture, we do some exercise about 'Implication information'. I can understand the meaning of an implication if it is true, but I do not really understand the question"what can you deduce about the following sets". So the first half of the lecture, I am struggling to understand the answers from Heap and other students. 

  After the lecture, I asked one of my friends for help who is also not very sure the goal of the problem. Hence, I posted it on Piazza. To my delight, an instructor makes a quick reply. By the way, the instructor also eliminates my misunderstanding of a concept that the contrapositive of a implication that has quantifiers does not need to change the quantifier from the universal one to existential one.Here is the link of my post. 

  When it comes to the "Natural" Language part, Heap lists lots of sentences expressing implication P=>Q in English ways and asks us to found the corresponding P and Q. The first several sentences are plain and direct. We could find the answers without much thinking. 

  However, the next following ones become more and more confusing to distinguish which is the antecedent P and which should be the result Q. 

  I find a trick that what we need to do is to find what leads to what. For example, a sentence' You can't stay in enrolled in CSC165 without a pulse.'.We can re-read it in our mind in our own words such that 'Without a pulse means that You can't stay in enrolled in CSC165' or "With a pulse means that You can stay in enrolled in CSC165.'So the key condition that decides that whether you can enrolled in CSC165 is that if you have pulse. 

  Hence, obviously, we conclude that 'without a pulse' is the antecedent of the result "can't stay in rolled in CSC165". Namely, 'without a pulse'is P,'can't stay in rolled in CSC165' is Q. 

  I believes that my trick is like the steps of solving a problem as mentioned before and understanding the problem is an important key of solving a problem. 

   

First week of CSC165

                                1st Lecture

• Goal of the course
• Precision

  Honestly speaking, I was not very clear about what I am going to learn in CSC165. To my delight, the first lecture eliminate my doubts.

  At the first lecture, Heap showed the syllabus and some related notification.Then he explained "What's CSC165" and "Why CSC165", which motivated me to learn it well and determined to lay a solid foundation for my further Computer Science study.
  At the end of the lecture, he introduced the concept of precision of language to us,which he took some interesting English phrases(although some is difficult for a foreigner like me to understand) to show us the ambiguities in human language, which was difficult for computers to understand. Hence, the course will teach us to use rigorous mathematical expression and reasoning to convert our intentions to computers and keep a good balance of precision between computers and humans.




                           2nd Lecture and 3rd Lecture

• Set and proposition
• Steps to solve unknown problems

  Luckily,I took the MAT137 and CSC108. So, before Heap talking about set and quantifiers, I have reviewed set and proposition in MAT137. Besides, Heap uses the code of Python to demonstrate the concepts, I did not take much effort to understand it because the CSC108 was talking about Python.
  In addition,the four steps to solve a problem that we have not seen a template for was penetrating and useful for not only CSC165 but also many other subjects, like math and physics. As to myself, I believed the first step(Understand the problem) is most significant to solve a problem. When confronting with a seemed insolvable problem, I will learn to calm down and get to know what is given and what is required systematically instead of being confused by tons of figures and words. The last step(Review) is also very useful for thoroughly understanding roadblocks before and optimizing your solution by convincing a skeptical peer and leading you to extend the solution to another new problem.