WEEK 11 JOURNAL: HALTING PROBLEMS

    This week, we talked about how to write a halt function, how to define a computable function, what is reduction and what is a countable set.
    First, we proved that we cannot write a halt(f, n) works for all functions f. To prove this, we can say that let the function test itself. Case 1 is that if the halt function does not halt, we can return a number, but if the function returns a number, it actually halts. Thus, we get a contradiction. Case 2 is that if the halt function halts, this function will continue run the while loop, this is an infinite loop and the function won't halt. Thus, we also get a contradiction for case 2. Therefore, we cannot write halt(f, n).
    A computable function is a function that f(x) is for every x in some certain domain and we know how to compute f(x) for every x in domain. Otherwise, f(x) is non-computable. For example, the halt function is a non-computable function.
     We say that f reduces to g if we find that f can be implemented by extending another function g. We can use reduction to show whether a function is computable or not, because a computable function reduces to a computable function.
     We use |A| to represent the size of  set A and if  |A| ≤ |ℕ|, we say that set A is countable. 

WEEK 10 JOURNAL: BIG-OMEGA, GENERAL PROPERTIES

    This week we continue talking about the big-oh problem. This time, we learned how to prove some general statements about big-oh. For example, we want to prove that for all f, g, h belong to F, (f∈O(g) and g∈O(h) ) => f∈O(h). In this question, we first know that if f∈O(g), and g∈O(h), then f <= c1g and g <= c2g. We want to show that f∈O(h), thus we need to choose a suitable c. We can easily know that when c >= c1*c2, f is always smaller than or equal to h. Therefore, we can pick b the biggest between b1 and b2 then pick c as c=c1*c2, then this statement is proved.
    Another statement is that ∀ f, g ∈ F, f ∈O(g) =>g∈Ω(f). Since f ∈O(g), we know that n>=B => f<= cg. Since g∈Ω(f), we know that n>= B' => g>=c'f. Because f<= cg, g>=f/c, thus, we can pick c' = 1/c and let B' = B. Then this statement can be proved.
    There is a tricky question: ∀ f, g ∈ F, f ∈O(g) =>f∈O(g*g). This statement is false, because g*g is not always bigger than g (i.e. let g = 1/(n+1)^2).
    In conclusion, to prove these statements, we need to find the relationship between the c we want to show and the c we have already known, and we also need to use the upper bound and the lower bound to bound the function.

WEEK 9 JOURNAL: BIG-OH OF POLYNOMIALS

    This week we talked about how to prove 7n^6 - 5n^4 + 2n^3 ∈ O(6n^8 - 4n^5 + n^2). To solve this problem, we first need to find the relationship between these two functions. We find that 6n^8 - 4n^5 + n^2 >= 6n^8 - 4n^5 >= 6n^8 - 4n^8 = 2n^8 since n is a nature number. Then, we can also find that 7n^6 + 2n^6 = 9n^6 >= 7n^6 + 2n^3 >= 7n^6 + 2n^3 - 5n^4. Therefore, our task now is to make some connections between 9n^6 and 2n^8. We need to make the constant the same and the number to the power of n to be different so that we can judge which one is bigger. Therefore, we choose our c = 9/2, and c * 2n^8 = 9n^8 >= 9n^6. Therefore, (6n^8 - 4n^5 + n^2) is always bigger than or equals to (7n^6 - 5n^4 + 2n^3) when c = 9/2. The hard point in this problem is that we need to pick a c that can connect both functions together.
 
    I remember that the test question 2 is a little bit similar to this question. In question 2, we need to find a "d" to make the negation of the statement to be true. Since "∃ d", this d must be unique and cannot be a universal number. The principle we judge whether a number is unique or not is that whether this number we choose can connect the antecedent and the consequent together. How to choose a unique number is quite hard sometimes, and we need to keep on practising.

WEEK 8 JOURNAL: BIG O PROBLEMS

    This week, we we talked about the formal definition of O and Ω, and we learned how to prove a function is in O. The definition for O is that ∃c∈ℝ+,∃b∈ℕ,∀n∈ℕ,n≥b => f(n) ≤ cg(n). This definition means that after a break point "b", f is always smaller than g. Conversely, Ω means that after the break point "b", f is always bigger than Ω. Therefore the definition of Ω is that ∃c∈ℝ+,∃b∈ℕ,∀n∈ℕ,n≥b => f(n) ≥ cg(n).
    To prove a function is in O, we need to find a suitable c such that f(n) ≤ cg(n). For example, in class we talked about how to prove the worst case complexity of insertion sort is in O(n^2). To solve this question, we can pick n = 10 then Wis = (3/2)n^2 + (9/2)n - 4 ≤ 10n^2. Next, we pick a b ≤ 10. Therefore, we proved that Wis is in O.

WEEK 7 JOURNAL: THE PROVE STRUCTURE

    This week, we became more familiar with the proof structure and we learned about how to make the statement precise and short. In programming, every statement must be precise, otherwise the program won't work. However, some programs are precise but because the program is too long, the working procedure will take lots of time. Thus, we should make our statement short and precise. In order to do this, we need to find and delete the sufficient but not necessary condition in our statement.

WEEK 6 JOURNAL: PROVE BY CASES

    This week, I learned how to prove a statement by cases. We can divide a statement into several situations, and show that for every situation, this statement is always true. Then, the statement is true. I find using this method can make some problems be easier to solve, because we only need to proof each part of a statement is true, and then the whole statement becomes true. However, the drawback of this method is that when we proof by cases, we must cover all the cases, otherwise the proof won't make sense. For now we have learned several methods to proof a statement is true or false. In some proofs, we need to use several methods to prove, and I think that's the hard point. Because in the sample problems, we only prove each statement by using one single method, and when we need to prove a statement by using several methods, I think it is hard to choose which method I should use and which I should not use.

WEEK 4 JOURNAL: IMPLICATION, DISJUNCTION AND PROOF

  This week we first talked about the bi-implication and its negation. Bi-implication can be written as A <=> B. This is equivalent to (A => B) ∧ (B => A) or we can write this as (¬A ∨ B) ∧ ( ¬B ∨ A). The negation for bi-implication is  (A ∧ ¬B) ∨ (B ∧ ¬A).
  Then we talked about some thing about how to prove a universally-quantified implication is true. If we want to prove A => B, the key to prove this implication is that we need to find the relationship between A and B, in other words, there must be some common traits between A and B.  We can use Venn diagram and truth table to help us find the common traits between A and B, and then we can judge which statement is true. For example, if we find that A ⊆ B on Venn diagram, we can say that A => B.
   When doing assignment 1, I find it is hard to judge when to use the imply symbol and when to use and. Because according to the truth table, "∧" and "=>" are always the same except vacuous truth. In addition, use vacuous truth is a quicker way to find examples or counter-examples.