Problem solving session penny piles

This problem solving session is based on the lecture in 10.28 which the problem of penny piles is discussed.

A problem solving session contains four parts:

1. Understand the problem

2. Devise a plan

3. Carry out the plan

4, Look back,figure out when and how you are stuck

Each part would be discussed carefully.

1. Understand the problem

To rephrase the question: You have two number 64 and 0. You can do an operation to change the number. The operation could be done if the number is in even, you divide that number by 2, and add the divided number to the other.

For example, now one have two number 48 and 16. If you do this to 48, then it becomes 48/2 = 24 and the other number becomes 12+24 = 40. Or, you do this to 12, then it becomes 12/2 = 6 and 48+6 = 54.

We want to prove that any number in the range [0,64] are able to achieve.

2. Devise a plan

Initially we have number 64 and 0, and the only operation we can do is to divide 64 by 2 and add 32 to 0, so it becomes 32, 32. Here since the numbers are the same, the next step would change it to 48 and 16.Then we have two choices which are 24, 40 or 56, 8. Then four 12, 52; 44, 20; 28, 36; 60, 4. So far the question has already become very complicate and would be even more complicate as there are more and more possibilities. Anyway, from the sample we have seen so far, we can see the pattern that they are all even number. That is quite reasonable as an odd number means we can no longer do operation to it. For example, 17, 47 seems hard to get. If we think it in a reverse way, the answer is quiet obvious. 47*2>64, so the only possible choice is 17*2=34 and the previous numbers are 34, 30.Again, 34*2>64. Thus, the previous one is 4,60. Then 8, 56. Then 16, 48. Then 32, 32. Then 64, 0 which is the beginning.

Now it is easy to see the pattern, we do it reversely. Sdince we have the last step and we could assume the previous step until we get 64, 0.

3. Carry a plan

We have an input (A1, A2)

Let

While  (A1,A2) != (64, 0) or (0, 64):

    If A1>32:

        A2 = A2/2, A1 = A1+A2/2

    else:

        A1 = A1/2, A2 = A2+A1/2

4. Figure out when and how you stuck

In this problem solving session, I stuck for a long time when facing to the data I collected as it is hard to find the pattern. Then at one point, I got the idea to think reversely and solve the problem quiet easily. I think this is the key for the question.  

Reflection of CSC165 Lec. 12 Nov. 25th

Reflection of CSC165 Lec. 12   Nov. 25th

I forget a lot after one week's rest. Assignment 3's Q5 and Q6 really test my understanding to the content of week 10 and definitely I need to work more on it.

12.1 Countability

There are three types of countability in this course.

 1-1 means each x would correspond to each y (implies each x may correspond to more than one y and some y may not correspond to x.)

Well-defined means each x maps to a unique y.

onto means every y has some x that maps to it. (but x could correspond to more than one y or no y)

In conclusion, we can say a well-defined function is 1-1 and onto

Now, try to prove:

X =  {natural numbers}

Y =  {even natural numbers}

Intuition : X > Y as every two natural numbers generate one even number

Intuition 2: However, there are infinite X, so there will also be infinite Y and infinite = infinite

Work  with the countability:

We can find every X correspond to Y, which means they are well defined, every x has a unique y mapping to it. Thus |X| = |Y|.

Also there is a concept called "countable". In convention, any set A that satisfies |A|≤|N| is computable. 

Actually, there are countably  infinitely many python functions as all python functions could be transfer to natural number series which belongs to N. Thus it is countable  

Reflection of CSC165 Lec. 10 Nov. 11th

Reflection of CSC165 Lec. 10   Nov. 11th

10.1 Big -omega proof

After the big oh proof we did last week, omega proof is taught today. The principle of big-oh proof and omega proof is the same since big-oh means the upper bound and big-omega means the lower bound, they are almost in opposite position.

In definition, Big- omega means:

A function f(n) is in Ω(g(n)) iff:

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

Keep in mind Big-oh means:

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

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

The proof of big-omega means you need to underestimate f(n) and overestimate g(n) in order to make the overestimated cg(n) equals to underestimated f(n)

10.2 Big-Oh proof for general cases

After proofing a lot of specific cases of Big-oh proof, it is time to find some general pattern or do some proof without any actual functions and numbers.

Proof:  ∀f,g,h∈F, (f∈O(g) ∧ g∈O(h)) →f∈O(h)

Assume f,g,h∈F, f∈O(g) ∧ g∈O(h)

    Then ∃c∈R+, ∃B∈N, such that ∀n∈N, n ≥B →f(n) ≤ cg(n)    # def of f(n) is in O(g(n))

    Then ∃c'∈R+, ∃B'∈N, such that ∀n∈N, n ≥B' →f(n) ≤ c'h(n) # def of f(n) is in O(g(n))

    Pick c'' = c*c', then c''∈R+

    Pick B'' = max(B,B'), then B''∈N

        Assume n∈N, n≥B''

        Then f(n) ≤ cg(n)

        Also g(n) ≤ c'h(n)

        Then f(n) ≤ cg(n) ≤ cc'h(n) = c''h(n)

        Then ∀n∈N, n≥B'' → f(n) ≤ c''h(n)

    Then ∃c∈R+, ∃B∈N, ∀n∈N, n≥B'' → f(n) ≤ c''h(n)

Then ∀f,g,h∈F, (f∈O(g) ∧ g∈O(h)) →f∈O(h)

In this case, the tricky choose of c is the core of answering the question. The answer substitute cg(n) to cc'h(n).

In fact, the choice of c plays an important role in this type of general question. It is used to link the condition together to form what we want to prove.

                                                                                

10.3 introduction to computability

After studying this section, I think it is the most difficult part so far I have learnt in this course. It is so abstract that I cannot get it from the example showed in the slide. Also the last question of Assignment 3 talks about the halt problem. I think I do not do it very well. Even though, I will try to explain this part in my words and comment on the question of Assignment 3.

Computer computes things by using algorithm, it is so powerful that it can solve a lot of complicate questions and returns the answer. However it is not always the case, sometimes the an easy program may lead to problem like infinity loop, which the computer would work forever inside the loop and cannot return the answer.

A typical infinity loop program may be this:

def blah(x):

    if x % 2 == 0:

        while True: pass

    else

        return x

The function would return x when x is an odd number, but when x is even, it will go into if x % 2 == 0. The while statement is true, so it will loop in the while line forever.

In order to judge this kind of functions, we use halt(f, i) to do so. I spend a lot of time to understand halt because the definition of it given on the slide is too vogue. I think it can be improved like this:

def halt(f, i):

    '''(function, input) -> Bool       

    

    Return true if the function halts (return sth. As result). Return False if it does not return                        anything. (Does not halt)   

    '''

    How to write halt in this case???

     return True

It is said that nobody can write halt(f, n) and it could be proved by contradiction.

So we suppose we can write halt(f,n)

Also I do not recommend to return sth. Like 42 as it is really confused for those who have  not seen or do not know the story and context of it.

 

There are three levels of function in terms of computability.

1. Computable

F is well defined in and we can tell how to compute f(x) for every x in the domain.

2. Well defined

We can tell the meaning of f(x) (what f(x) is for every x in some domain)

3. Non-computable

We cannot tell what f(x) is for some x in all domain.

Halt(f, n)  is well-defined but not computable because we cannot compute the f(x), but know the meaning of it.

After knowing the function for halt is not computable, we can decide any function is computable by using reduction.

We say f reduces g, if

Def f(n):

    return g(n)

This simple relation between f(n) and g(n) means their computability is the same.

G computable implied f computable

In contrapositive, f non-computable implied g not-computable

There are still some problems remain  unsolved and I will get the answer as soon as possible during upcoming office hour.