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.

week[4]_termTestOmg

I just finished my term test and thank god that was an easy one. The whole test is pretty similar to the past test, especially the first question. However in the last 5 minutes of the test I found I misread the first question and all my answers are matched to the opposite situations. It was really a heart attack I tried my best to correct them all but since all this was in a hurry I realized that I probably messed up the quantifiers of the last two questions. Now I prey TAs won’t be so harsh on me, lol.

This week we are studying contradiction, existence and sequences. It is not hard as well since it’s all about prove a statement in different ways, but still some of them are quite “mind-wrecking”. Besides that I really like my instructor Larry and his lecture notes. Compared to the dull and plain course notes written by professors, Larry’s notes is really simple to understand and fun to read. These proofs and logic stuff are not only boring anymore with the memes, but also kind of pulling me to read and study it. If I really did well in this course, half is the time and work I spent on this course and another half is Larry’s interesting lecture and patient help :)

week[3]_a1

This week we have done our first assignment. This assignment is a bit harder than I expected, I started late but fortunately I finished it just in time and hopefully they are correct. For me, the most challenging part in this assignment is question 5, because I found these questions are really "flexible". You can think the question in a really complicated way, but they still make sense if you use a really simple method. This confuses me that it makes me not so sure which way should I use and which way is correct. Other than that I think it is pretty simple one.

Also, this is the fourth week which means 1/3 of our semester is gone, and so does the course contents. We finished the first part of the course, symbols quantifiers and logic statements, and two more parts are waiting which are proofs and algorithms. Proofs are easy too since the problems are not that hard as far as I see, all we need to do is write them in another way: the structured proof.  I hope I will be ok with that, and time to start reviewing our first term test.

week[2]_foldingQuestion

This week we studied conjunctions and disjunctions. This is pretty much union and interaction so this part is not that hard for me. The more interesting thing is, I see instructor posts folding problem on next week slide and I decide to talk about it here this week.

Here is what I got from the Wikipedia.

The napkin folding problem is a problem in geometry and the mathematics of paper folding that explores whether folding a square or a rectangular napkin can increase its perimeter.

The rule is one can consider sequential folding of all layers along a line. In this case it can be shown that the perimeter is always non-increasing under such folding, thus never exceeding 4

Robert J. Lang, who is an American physicist, devised two different solutions. Both involved sinking flaps and so were not necessarily rigidly foldable. The simplest was based on the origami bird base and gave a solution with a perimeter of about 4.12 compared to the original perimeter of 4. The second solution can be used to make a figure with a perimeter as large as desired. He divides the square into a large number of smaller squares and employs the 'sea urchin' type origami construction described in his 1990 book, Origami Sea Life. The crease pattern shown is the n = 5 case and can be used to produce a flat figure with 25 flaps, one for each of the large circles, and sinking is used to thin them. When very thin the 25 arms will give a 25 pointed star with a small center and a perimeter approaching N2/(N − 1). In the case of N = 5 this is about 6.25, and the total length goes up approximately as N.

week[1]_logics!

This week we are introduced symbols and quantifiers.

Symbols and quantifiers themselves are not difficult at all, I’ve seen them in my math books before especially the Vein diagram. However the tricky part is transfer daily language into logic statements and vice versa. For example, in our daily life we say “Go buy that headphone only if that headphone is half price off” but in logic we “say” Buy the phone -> Half price off.

Moreover I find the vacuous truth is more like a mind blow for me. For instance, if x^2<0, then x>x+5. In our daily life this is totally wrong and if we write it is correct in our math exam I would absolutely get a zero. However! However in logic, this is correct, isn’t that incredible? But after all that, when I get used to the logic language, I find it is fun to translate normal language to logic statements.

Besides I found an easier way to solve logic statement problems, which is simplify the question description and draw a Vein diagram about it, then everything is so clear and can’t wrong.

week[0] = "Hello world!"

Hello world! Probably this the simplest way to greet each other by computer scientists, or a super novice computer scientist.

I’ve written a slog for CSC148 last term so this is my second slog. As always, I would like to introduce myself a little bit, since there are not much actual contents in the lecture (lecture is doing introductions too!). I’m a second year student and I’m aiming to enroll computer science major program. I love computer games, I start playing games on console when I was 4 years old, then on computer a few years later. My favourite games at that time were SimCity 3000 and Red Alert. I really enjoy the game and for me it is a miracle that how computers can calculate the data, stimulate complex conditions and display fantastic images. This becomes one of my reasons to study in computer science when I graduate from high school.

Now I know that computer science is not only games but consist by lots of scientific fields, such as programming, designing, algorithms, hardware, arts design etc. My favourite part among here is art design, such as design character 3D models, that’s my dreaming job. However I believe do well in computer science will give me some outstanding background knowledge in computer science field, no matter what I’m going to do in the future.

And that’s pretty much about me. Good luck to me this term!