Reflection of CSC165 Lec.9 Nov. 5th

9.1  Big O proof

Def of O(n2)

A function f(n) is in O(n2) iff:

∃c∈R+, ∃B∈N, such that ∀ n∈N, n ≥B → f(n) ≤ cn2

In English, it means beyond the breakpoint B, f(n) is upper-bounded by cn2, where c is some wisely chosen constant multiplier.

Now let's try to prove 3n2 + 2n ∈ O(n2)

Which means it should fits:

∃c∈R+, ∃B∈N, such that ∀ n∈N, n ≥B → f(n) ≤ cn2

f(n) =  3n2 + 2n, in order to let  f(n) ≤ cn2, c should be larger than 3

Moreover, 3n2 + 2n < 3n2 + 2n2 = 5n2

So, c could be 5 and b could be 1 as it satisfies the condition.

Proof: 3n2 + 2n ∈o(n2) 

3n2 + 2n: N→R>0

Pick c = 5, then c ∈R+

Pick B = 1, then B ∈ N

    assume n ∈N

        assume n ≥ 1

            then 3n2 + 2n ≤ 3n2 +3n2 + 2n * n

                                   = 5n2 = cn2

            then 3n2 + 2n ≤ cn2

        then n ≥ B → 3n2 + 2n ≤ cn2

     then ∀ n ∈N, n ≥ B → 3n2 + 2n ≤ cn2

Then  ∃ ∈R+, ∃B ∈N, ∀n ∈N, n ≥B → 3n2 + 2n ≤ cn2

Then   3n2 + 2n ∈ O(n2)

Then we may face to some cases that are much more complicate. Like to prove:

7n6-5n4+2n3 ∈O(6n8-4n5+n2)

The general step is to assume n  ≥ 1 # As it is applicable in most cases

Then we overestimate the upper bound and  underestimate the lower bound.

So if A < B, and the relation is not really clear, we prove it by using

(A<C<D<E<F<G<B) which the relation of every two of these are obvious

In this case: 6n8 - 4n5 + n2 > 6n8 - 4n5  > 6n8 - 4n8 > 2n8 * 9/2 > 9n6 = 7n6 +2n6 >7n6 + 2n3 > 7n6 - 5n4 +2n3

Disprove of O(n) follows the same pattern. We first negate the initial definition of O(n) and prove the negation is true

Let's think about the case of：

9.2 Big O proof with limits

      

     

   

              

   

           

  

      

       

  

  

    

   

      

        

                    

About The Site

I tried to change my slog site to wordpress, but the UI of wordpress is not so good as well. The word is too thin for people to read. And it is not good at reading special mathematics symbol.

On the other hand, I cannot login to Blogger sometimes (in fact it happens quiet often but not all the time). Anyway, I still decide to update the blog here as long as I can still login.

Reflection of CSC165 Lec. 7 Oct. 21st

Reflection of CSC165 Lec. 6 Oct. 21st

7.1 Proof by cases

Proof by cases is one kind of intuitional way in life. We think every different possibility of one case and prove all these possibilities are true. In class, we face to the following problem:

∀n∈N,n^2+n  is even
n2  + n = n (n+1)

To solve this case, we think all possibilities of n, which means n may be either even or odd.
If n is even, then n(n+1) is also even.
If n is odd, the n+1 must be even, n(n+1) is even.

The thinking above is just a rough one, we need to write the proof process academically:

Assume n ∈N
    then (∃k∈N, n=2k+1)  ∨ （∃k∈N, n=2k）
    Case1: assume ∃k∈N, n=2k+1:
        then n2  + n = n (n+1) = (2k+1)(2k+2)
                           =2 [(2k+1)(k+1)]
                           =2j                         let j be  [(2k+1)(k+1)]
    Case2: assume  ∃k∈N, n=2k:
        then n2 + n = n(n+1) =2k(2k+1)
                          =2[k(2k+1)]
                          =2k                         let k be [k(2k+1)]
Then n2+n is even

7.2 Review of proof patterns

This section aims to conclude all the ways of proof and find the pattern of them.

Generally there are two patterns of inference rules(from what we know to what we can infer):

Introduction rules start from a small statement and finally infer a bigger statement.
Elimination rules start from a big statement and finally infer a smaller statement.

7.3 Algorithm Analysis and Asymptotic Notation

This section seems very computer science related, but I do not think the professor explain the idea of algorithm very well as algorithm means. I think algorithm is a kind of sovereign goal that every computer scientist may pursue. In a lot of real life situations, there might be a lot of ways to solve a problem. Normal people may simply find one way and solve it. However, a computer scientist may find all possible ways and compare them, choose the best one in the end. The wordload is much higher than simply find one way while the final result is the same----The problem is solved. But this perfectionism makes the progress of the whole subject.

In the class we compare two sorting algorithms which are bubble sort and merge sort. These two can both achieve the goal of sorting certain codes, but the running time is totally different.

Running time does not mean the actual seconds of time the program run, because the actual time may vary depend on how powerful the hardware is. So even the program is not so efficient, one can still get the result faster than those who run a better program but on a poor hardware. Thus, if all programs are run on the same hardware, the number of steps is the real determinants.

By seeing the process of working, we find as the size of codes become larger, the more number of steps bubble would take rather than merge. In conclusion, the general pattern that bubble would take is 0.5n2 (though we do not study why is it.) and merge would take n log n.

Another important idea in algorithm is the significance of highest degree variables. That is to say x2 is no difference than 100000x2 because their variable's highest degree is the same.

Also, we may use the symbol O(f(n)) to presents the idea that a set of functions run no faster than f(n). (e.g.: 5x2 + 3x +1 is in O(3x2))

Reflection of CSC165 Lec. 6 Oct. 14th

Reflection of CSC165 Lec. 6 Oct. 14th

Today's lecture lasted two hours, so the content would be a little bit shorter, again.

6.1  proof about non-boolean functions

Non-boolean functions are another type of function. Compare to Boolean, the result is not simply True or False. Thus, we cannot make a judge (of True of False) by looking at a non-boolean function. 

The most important non-boolean function introduced in class is called "floor". ⌊X⌋  means the largest integer ≤ x.

Although ⌊X⌋  and x looks quiet similar, but they have different property. X is just a variable,  ⌊X⌋  is a function, which in the same as f(x). Thus, we cannot apply ∀⌊X⌋∈R (a quantifier) to a function.

6.2 prove something false disprove something

To prove a statement S equals to proving ¬S.

6.3 proof about limits

Let's try to solve a typical question of proof about limits which mentioned in class.

∀ϵ>0, ∃δ>0, ∀x∈R, |x−2|<δ→|x^2−4|<ϵ

Here the thinking is, since ϵ could be every value > 0, we must change δ according to ϵ in order to satisfy the requirment. Thus, we need to find a constant relationship between ϵ and δ so that no matter what the value of ϵ is, we  can always find a valid value of δ follows the pattern of such relationship.

Since we know that |x^2−4|<ϵ and  |x−2|<δ and we need to build a relation between ϵ and δ, we can try to find the relation between  |x^2−4|  and |x−2|.

We find out |x^2−4|= |x+2|×|x−2|

Since |x−2|<δ 

 |x^2−4|<δ ×|x+2|

Let x + 2 be (x - 2) + 4 = δ + 4 

 |x^2−4|<δ ×(δ+4) 

Now comes to the tricky part:

 make δ≤1,δ ×(δ+4)<5δ<ϵ  so, δ≤ϵ/5  

We also now  δ≤1(as we assume):

δ=min⁡(1,ϵ/5)

However, all the works above is just rough thought and cannot be used as to prove, but the conclusion would be used in the prove.

Prove:

Assume ϵ>0                  # Assume the prerequisite

    pick δ=min⁡(1,ϵ/5)      # from the conclusion of the rough thought above

    then δ>0                   #we can conclude this from the line above.

    assume x ∈R               #Assume prerequisite

         assume |x−2|<δ  #Assume the antecedent, antecedent must be true if we want to prove the implication is true

             then  |x^2−4|= |x+2|×|x−2|<δ ×(δ+4)<5δ<ϵ  #The same process as the rough thought

Then |x−2|<δ→ |x^2−4|<ϵ