CSC165 sorting strategies

 In these week lecture, we learned about the sorting strategies, using an example of  ordering a deck of cards from largest to the smallest. we have insertion sort , selection sort and other more complicate sorts such as Radix, Quick sort, Tim, Merge sort. 

we always think about the worst case in sorting or counting costs.

We also talks about how to disprove a implication, which maybe useful in A2
conjunction elimination: when A and B is True ,then both A B is true. If A and B is false, then at least one of them is false.
existential instantiation: we just need one example
disjunction elimination: If we know A or B is true ,while A is false ,we certainly know that B must me true
implication elimination: When A implies B, if A is true, then B must me true. (know A then know B)If not B is true, then not A must be true.
universal elimination: if there exists one x that is not P(x), then the universal statement will be false

OCT.18th.2014 CSC165 Proof

In this week lecture,we learned how to make a proof.

Some points should be made attention:
1) the form and the structure of a proof
2)the key point(maybe the most complicate part)
3)the  annotation

sometimes we find the statement to difficult to proof, we could think about the contrapositive or the negation of the origin, since they have connections to it.


proof by cases
In such problems, the provident should be separated into several cases.such that case, case2 and so on (i.e to prove all natural number, we should divide them into case1: odd number case2: even number)

when we need to prove a existence we just need only one element.

OCT 4th CSC165 Double Quantifiers

In the lecture this week, we talked about transitivity , double quantifiers and how to transform a statement graphically.
When we have two different quantifiers in one statement, we could not switch their position  at any tome since it may be totally change the meaning.
If the statement talks about subset , and the quantifiers are in the same type ,the order doesn't matter.

Also ,we learn how to draw it in a graph.
lim x ^2=0.36

x ->0.6 

The graph shows that every time my 'enemy' finds a e ,the I find a d.However, if e is chosen after d,everything will mess up. Every time I pick a d, my 'enemy' will pick a higher number,then I will fail to satisfy it all the time.

Something that I have made sure in the TUT:

there exists a dog doesn't have its day and its cat means neither have is day nor its cat.

Also, here is the Guarantees that make us really uncomfortable:

(A ∨  B) ⇒C⇔(A  ⇒  C )∧( B ⇒ C )
(A ∧  B) ⇒C⇔(A  ⇒  C )∨( B ⇒ C )



(A ∨  B) ⇒C
when the statement is true :
1) if c is true , then A and B at least one true
2)if c is false, then both A and B must be false
when the statement is false:
c must be false