week[11]_ending

Our last thing before the final exam is the assignment 3.

To be honest I didn’t put too much time in this course since November, and I was so wrong that I under estimate the difficulty of the course, it is kind of out of my control now :( I don’t have much clues about the algorithms until I forced myself to sit and read Larry’s notes and attended his office hour, then everything becomes clear haha. I didn’t do well on my second test (like 60%), and my second assignment I got like 37%. The situation is much more dire than I expected…I’m so sure most of my work in assignment 2 are correct after compared my answers to the sample answer, maybe my terrible layout ruined it :( I requested remark anyways, I hope the TA will forgive my layout and grade it fairly.

Another remarkable thing is in assignment 3, for question number five I picked f=sinx and g=cosx in the first. However Larry’s notes inspired me that just pick f(n) = 0 when n is odd and 1 when n is even, g(n) = 1 when n is odd and 0 when n is even, the whole problem just collapses. Its difficulty drops from above the highest clouds to the lowest possible seabed. The metaphor may sound funny but that was how I feel when I finally can solve that problem and the only thing left is to write an appropriate proof structure, which is such an easy piece.

One more last thing is, the semester is over. Thanks all for everything! Cheers!! 

week[10]_fallBreak

Finally it’s the fall break, everyone can catch their breath now. Have fun and enjoy!

week[9]_halt

This week more programming things are involved. For example the halt problems. As what are wrote in the course notes, we use the following technique to prove some programs are not computable.

First of all, we proved halt() is not computable. However, to prove some functions are not computable as well, we need to assume halt() is computable. The strategy is using contradictions, that we assume halt() is computable, we use it to prove the function is computable, however halt() is wrong, so does the function.

Generally, we define a halt function, such as

                                                                  def halt(F, I):

Then we use the given function as a helper function within the halt function, such as

                                                                  def given(f, i):

                                                  ‘’’return certain result when certain conditions are satisfied’’’

Then, we write another function within halt() by ourself, it much call the halt() and its result is not affected by the input. For instance

                                                  def given_prime(x):

                                                           F(I)

                                                           return ‘hahafail’

So, put them all together we can write like

def halt(F, I):

    def given(f, i):

        …implement code...

    def given_prime(x):

        F(I)

        return ‘hahafail’

return given(f, given_prime)

so the only thing we need to do here is prove when halt is true, our result is true; when halt if false, then result is false, and by contradiction, given is not computable!

week[8]_termTestTwoo

This week I finally finished my assignment two. I was just in time that the markus stopped working and fortunately I successfully submitted my work to markus at 10:00PM. That was a literally nerve-wracking experience, I swear I’m not going to do that again. :( I attended Larry’s office hour too, I got 90% on my first assignment and I think I can do well too on my second assignment. The only “flaw” is I was in such a hurry I didn’t have time to type it, I scanned it then I stuck with Microsoft Word, it won’t let me arrange the image layout, so my layout is really terrible. I do hope it won’t affect my grade. /prey

We also did the second term test. The first two questions are so easy that I finished them in 10 minutes, but I stuck on the last one. I spent about 30 minutes on it yet I can’t finalize my answer. I really have no idea on that one.

As always, some course contents. This week we talked about prove algorithms by using limits and L’Hospital’s Rule. I definitely forgot like all of the calculus. I’ll just post them here in order to remember them better. Nothing much other than the calculus thing.

lim f/g = lim f’/g’

week[7]_assignmentTwo

For this week I would like to write something about assignment two. I actually start working on this assignment a week ago yet it is still quite challenging for me now. First, the definition is tricky, I try to understand it as what it is defined as however I still can’t use it in the ways I’m familiar with. It feels like use a new word from another language to make a sentence, my brain realizes it but still not even trying to work with it. However, I find the meaning of the symbol and look up the definition of “floor”, things become crystal clear at once. Claim 1.3 and 1.4 is a bit hard to me, too, but I have faith in myself!

For course content, we learned some simple algorithms this week, such as bubble sort, quick sort and merge sort. We also learned how to calculate rough run time in worst-cases. The proof is still same structured as before, the only thing has changed is the problem. The problem becomes much easier when we just simplify the big-Os and big-omegas into greater or equals and smaller or equals. Just be careful count correct steps from the Python functions then all good.

week[6]_pennyPiles

This week we finish the second part of our course, the proofs, and start on the final part, the algorithms, but there aren’t much about it, just a first taste. For proofs, we continued on proving cases and did some review. Assignment 2 is coming I believe.

Algorithm for us now is only like 3 symbols: big-O(<=), big-omega(>=) and big-theta(omega<=f<=O). I think I can manage it as long I remember the relations between them.

Other than that, we are asked to talk about penny piles.

Penny piles is a problem that given the left drawer has 64 coins, the right drawer is empty, then:

If L has even number of coins, transfer half to right.

If R has even number of coins, transfer half to left.

So basically in this case the number of the two piles are 64-0, 32-32, 48-16, 24-40, 44-20, 22-42, 43-21. The questions is what about starting with a different number of coins in the left drawer.

As far as I can find from internet and course resources, this problem can only perfectly be solved by using a proving technique called induction. Unfortunately we are not able to learn it in CSC165, it’s a huge part in CSC236 though. The general I idea is assume a “function” true, and its input is n, such as P(n) and as long as we can prove P(n+1) is true, then P(n) is true. This proving technique sounds more fun and more powerful. Also an interesting thing I’ve found is if something is hard to solve, assume it is true and most likely you are on the right track, lol.

week[5]_rightAndWrongs

Like Yin and Yang, there always would be a matching opposite side of everything, such as sun and moon, hot and cold, man and woman, and definitely right and wrong. This indicates our topic this week, prove and disprove, how can we say that statement is wrong? Easy, prove its negation is correct. For instance a fake god defines all men shall below 2 meters height, then Yao Ming breaks his rule and proves it is a wrong definition.

It is absolutely an important proving technique but for sure it brings more complicity to our questions after all, for example we only need to find a way to prove a statement before but now we have to think it is right or wrong and decide to prove it or disprove it, which negates it the do the proving job.

In addition, I really enjoy writing proofs because it is so organized and my OCD is satisfied! Joke. I never consider myself as a science guy, but I still love writing the structure, the assume lines, the pick value lines, the proving parts whether in cases or not, and the introducing lines, everything is so neat and shows the charm of mathematic.