csc165 Dec 2nd.2014 halt

in the lecture , we learnt the halt and countable and computable.
a computable function is a well-defined function, a well- defined function is a 1-1 and onto  function .
hat(f,n)is a non-computable function.
using diagonalization , implement halt function with a function that we want to prove that is un-computable.

csc165 halt NOV.24th.2014

In last week lecture, we leaned about some functions with "halt"
we know that not all the functions are uncomputable.
infinity is not always equals to infinity. If one infinity has more members that has finite numbers then it should be larger.However, two sets have the same size if they are one to one or onto
one to one is that for every x and y  f (x ) = f (y ) => x = y
onto is that  for every y, there existed a x such that f (x ) = y

 

 

NOV 15th.2014 CSC165 big omega & prove general statement about 2 functions

big omega:
∃C ∈ R+，∃B∈N，∀ n ∈ N,n >=B ⇒ f(n)>=c.g(n)

prove general statement about 2 functions:

I think this is just a little change from the 1function's style.  One more assume for the second function and leads to the conclusion of the connection between the 2 functions.Pay attention to the choice of picking B,C sometimes we use the max or min of the two numbers, of we might use the ceiling or the floor.

 ∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)

Prove:
Assume f,g∈F  #Just the old thing
    assume f∈O(h))∧g∈O(h) #Just the old thing
       ∃cf ∈ R+ ,∃Bf∈N,∀ n ∈ N, n>=Bf ⇒f(n)<=cf *h(n)# nearly the od thing ,just a little bit different on the c, which becomes cf(also B) now.
       ∃cg ∈ R+ ,∃Bg∈N,∀ n ∈ N, n>=Bg ⇒g(n)<=cg* h(n)#now the f(n) becomes g(n),which is for the second function.
       Pick C = Cf + Cg,Then C∈ R+
       Pick B = max(Bf,Bg)
       assume n ∈ N ∧ n >=B
            Then (f+g)(n) = f(n)+g(n) <=Cf*h(n)+Cg*h(n)
                                                      =(Cf+Cg)h(n)=Ch(n)#now we can find how to pick C,which is Cf + Cg
      ∀ n ∈ N, n>=B,(f+g)∈O(h)
       ∃cf,cg ∈ R ,∃Bf,Bg∈N,∀ n ∈ N, n>=B⇒(f+g)∈O(h)
∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)

NOV 9th.2014 CSC165 big-oh of n^2 maximum slice

prove 3n^2+2n∈O(n^2)

that ∃c∈R+,∃B∈N,∀ n ∈ N,3n^2+2n<=C*n^2

pick C = 5
   pick B = 0
      assume n∈N # generic  intro ∀
          assume n>=B 
                assume n>=B #antecendent
                    Then 3n^2+2n <= 3n^2+2n^2 # 2n <= 2n^2
                                            = 5n^2
                                            = Cn^2    #since c=5
                    Then N>=B ==> 3n^2+2n<=C*n^2
....


prove    3n^2+3n+5 ∈O(n^2)
              <= 3n^2 +2n^2 + 5
              <= 3n^2 + 2n^2 +5n^2 # N>=1   #pay attention  to 5n^2  that n=0
              =10 n^2
              =c n^2

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