week 12

This week we are working on the assignment 3. After finishing the question 5, I have a general idea about it.

I am thinking that every function has a character whether its gonna halt or not.

Then I can reduce Halt to every function. Simply, I can just put my function in to Halt.

As a result, a function is not computble is a sequence of halt is not computble. The contrapositive is 'if halt computable then the original function is computable.'

Week 10

I got my second term test back this week, I did OK in this test which I got a 80%s BUT I make few mistakes and I think I should learn something from them.(I will analyze them later in this post). And we get our assignment 2 result back, we r almost getting a full mark but has a terrible mistake that we made a typo on a symbol of the negation of a question so its proof doesn't make any sense....

From those mistakes, 

1) double check the negation

2) pay attention to the symbols in () especially when we try to negate it.

3) when stuck, try the contrapositive.

 

week 9

This week we have the second term test which is about the proof and the structure of a prove. I think I did good on it but I have some thoughts about it.
 First, what kinds of comments are really necessary for the proof.
 Second, when you stuck at some proof you should try the negation and the    contrapositive of the statement.
 Third, is there a way to check whether the proof is right or not?

week 8

This week we learn about worst case complexity and how to calculate it by counting steps.

Every function has an upper bound and lower bound so that we always consider the worst case --- the upper bound for complexity.

Since complexity is going to be a very large number, the constant in it really doesn't matter any more. For example, O(18n^2) roughly is O(n^2).

For calculating the steps of a function, we count the constant steps first and then count the outer loop(let's say n steps) and then the Loop Guard and then the inner loop(lets say n^2) and so on.

week 7

In this week, since we are working on the assignment 2, I have some thoughts about proving structure in general:

    first of all, if it is a universal quantifier, then you assume an general element which meets the requires, then prove it by assuming the first part of the implication True and using the condition to transfer to a statement which is the latter part of the implication.

    Secondly, if it is an existential quantifier(most the case it is in a disproof), then you pick a element that satisfies the implication. After all these, you have proved a negation of an original statement.

Moreover, we learn some sorting algorithms and how to count the steps. Most of the case, we are consider the worst case of an sorting algorithm and after all the constant in front of the number of steps is not that important anymore.

week 6 -- solving negation problem analysis

This week we get out first midterm back, overall, I did OK on this test since I got 85%. But I found myself keep having the same problem on how to negate an implication without hesitation.

For an implication like:
                       ∀a∈ N, P(a) ⇒ Q(a)

P(a) ⇒ Q(a) equals:
                      ∀a∈ N, ¬P(a) ∨ Q(a)

hence the negation:

                       ∃ a∈ N, P(a) ∧ ¬Q(a)


Let's try another way(this is a tricky False statement):

the only false of it :
                       ∃ a∈ N, P(a) ⇒ ¬Q(a)
P(a) ⇒ ¬Q(a) equals:
                       ∃ a∈ N,  ¬P(a) ∨ ¬Q(a)

Let's use "negation" of implication:(False)
so the negation of ∀a∈ N, P(a) ⇒ Q(a)
                       is ∃a∈ N, ¬P(a) ⇒ ¬Q(a)
equals:
                   ∃a∈ N, P(a) ∨ ¬Q(a)

week 5 proof outline

proof outline:

1. for all x in R, P --> Q:

The method we learned in the lecture is trying to prove a statement from base case or in other words, using P to get to Q by transforming the equation or inequation. (it's like the firse step of mathmatic indaction)

2. there exist a x in R, P --> Q:

Just find a example.

3. if the sttement is hard to prove:

try to prove the contropositive.