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.