week 9

This week we have the second term test which is about the proof and the structure of a prove. I think I did good on it but I have some thoughts about it.
 First, what kinds of comments are really necessary for the proof.
 Second, when you stuck at some proof you should try the negation and the    contrapositive of the statement.
 Third, is there a way to check whether the proof is right or not?

week 8

This week we learn about worst case complexity and how to calculate it by counting steps.

Every function has an upper bound and lower bound so that we always consider the worst case --- the upper bound for complexity.

Since complexity is going to be a very large number, the constant in it really doesn't matter any more. For example, O(18n^2) roughly is O(n^2).

For calculating the steps of a function, we count the constant steps first and then count the outer loop(let's say n steps) and then the Loop Guard and then the inner loop(lets say n^2) and so on.

week 7

In this week, since we are working on the assignment 2, I have some thoughts about proving structure in general:

    first of all, if it is a universal quantifier, then you assume an general element which meets the requires, then prove it by assuming the first part of the implication True and using the condition to transfer to a statement which is the latter part of the implication.

    Secondly, if it is an existential quantifier(most the case it is in a disproof), then you pick a element that satisfies the implication. After all these, you have proved a negation of an original statement.

Moreover, we learn some sorting algorithms and how to count the steps. Most of the case, we are consider the worst case of an sorting algorithm and after all the constant in front of the number of steps is not that important anymore.