2014年11月18日星期二

week 10: Term Test 2 Results Out! + finishing asymptotic proofs

This week we wrapped up the proofs for big-Oh and big-Omega statements and started the new chapter about computability. Larry introduced the final kind of statements: general big-Oh statements.


①tips for picking c and B for general big-Oh statements:
1. if the antecedent contains one big-Oh/Omega:
   for instance:
   pick B' = B
   get the appropriate c' = 1/c by computing f(n) ≤ c * g(n) and g(n) ≥ c' * f(n)

2. if the antecedent contains two big-Oh/Omega:
   for instance:
   pick B" = max(B, B')
   get the magic c" = c + c' by computing f ≤ ch, g ≤ c'h, and f+g ≤ c"h


②introduction of computability:
Some questions that look easy for computer to solve are actually non-computable, like halt. I'm taking csc108 so I know some about python, but stuff here is more about logic(e.g. REDUCTIONS, write halt(f,I) by using a helper function) rather than coding.

First let's define the terminology based my own understanding:
well-defined: every x has a corresponding f(x)
computable: there is a way we can get f(x) by x

Knowing that this is a logic course, we are more focusing on using functions for proofs. The main question for this part is:given any function, decide whether it is computable or not by using reductions as I mentioned above.

After reading the course notes, I finally generated a clear plan on how to prove a function non-computable:

Step 1: assume the function is computable, in order to derive a contradiction, which in the case given during lecture, is to derive "halt is computable"

Step 2: find a way to compute halt use a helper function:
what we want is: If halt(f,i)halts, then the helper function makes halt returns True. Vice versa

This time the average is around 72%, which is lower then last time but still pretty good. However, my grade surpassed the average by more than 10%. It seems to be a improvement to me, maybe because I'm better at proofs. Overall, the result is a cheer-up to me!



2014年11月5日星期三

Week 9: exercises of proving Big-Oh (using limit techniques)

This week is all about big-Oh proofs.




I like the graphic expression. In the picture on the left, point B is indicated as a break point, beyond which f(n) is upper-bounded by cn^2.

Note: remember noting that O(n^2)belongs to a set of functions
functions that take in natural numbers and return non-negative real numbers



For exercising, I want to pick the more complicated one from examples taught in class to analyze:

To prove





①negate
 then we have
②prove the negation 
the hardest part: picking a wise n

Since we want both n≥3c and n≥B, we need more than "pick n=max(3c,B)". Instead, we pick n = max(floor of 3c, B)+ 1 because the value of floor of 3c is either 3c or (3c -1)by the definition of floor. Then (floor of 3c) +1 must ≥ 3c. 
④brainstorm finished. Now we only need to follow the proof structure write down the thoughts step by step, watching out indention errors. 


tips of using limits techniques to disprove big-Oh:

By proving limit, we can obtain either 2^n / n^2 > c or 2^n / n^2 < c depending on the value of the limit:

Then we can use the result to disprove big-Oh, since its result is f(n)≤c*g(n).