Master Theorem,Gaussian elimination and A2

Last week we had quite a few recursive functions that are not strange but unfamiliar in another way: their complexity. During the lecture last week we had a little review of the Master Theorem with the example of multiplying two 4-digit binary numbers. As we went over the process of "unwind--non-decreasing--general cases", the result we came upon was T(n) = theta(n^2), which seemed fair enough for me because I thought there were no other way that can do it better (I am probably not the only one). However, by the wise of Gaussian elimination, which was originally a method in linear algebra, we change the function

into one that seemed a little more complicated:

one might think that this modification have only made the problem worse at the first look, but if we try to analyse it, Gaussian elimination successfully reduced the number of multiplication (in this case is the "a" in the Master Theorem) from 4 to 3. Hence, the T(n) now would be theta(n^(lg3)). Though the difference of lg4 and lg3 is fairly small, it can mean a huge difference when n is large enough.

Red line - n^lg3
Blue line - n^lg4

We also discussed about the closest pair-of-point on the lecture, it was fun and interesting!!!!!

For now I have done my first draft of A2 and my feeling is it is very much different from A1, now we not only need to provide a formally induction-based proof, we also need to try hard to work out a claim to proof, and it sometime can be difficult...

Well, I guess it's time to stop and get back to work on the second term test, hope I can do well this time too!

Officially, First SLOG!

Well, this is officially my first SLOG(as well as my first blog, ever!). So I am going to talk a little bit about what happened during my first "SLOG week".

When me and my friends went to the lecture last Wednesday we were talking how easy the term test was and if the tests of this course were all that easy, we would definitely get straight "A"s. However, during the first 30 minutes of the lecture, I couldn't understand a bit about what was going on on the big, lovely screen! I was terrified, kept asking myself: "What on earth is this T(n)? Did I miss something last time? How can I not know anything on the note?". But right after Professor Heap mentioned "clg(n)", something struck me and all my memories from last Wednesday were back online. That was a quite unfamiliar experience to me since I had reviewed last week's note twice in that week, but I still couldn't remember anything. I am so glad that I was just on a lecture, not on a quiz, or even worse, on the final exam! I looked up this symptom after the class, medical researches show that this kind of symptom is common and mainly caused by anxiety, god I need to learn to relax or this COULD very much likely to happen during the test!

The lecture was not very difficult(except the first 30 minutes for me...), practiced more about unwinding on merge sort and other stuff. In the last 40 minutes, the test paper was handed back. I am surprised that the papers were marked so quickly(it usually takes up to two weeks in other courses). Though I know I was doing fine on the test,I was still a little nervous about the marks. "14 out of 15?! "I was shocked. I never expected that I would do this well on the test(maybe it's because the test is quite easy).

Well, I need to go to the lecture now, and I guess that is it for now, I will keep writing and if there is anything that you want or don't want me to write in the future, please let me know!

P

Hello to all!

Hello to dear instructor, TAs and all fellow classmates. 

Thank you for visiting my blog! 

My name is Peter and I am now in my second year in CS specialist. 

This is my first blog and I am not a native English speaker, so if there are any things that are not appropriate in the following articles, please feel free to let me know and I will fix them ASAP.

This is just a "say Hi" and there will be some more stuff coming up in the future weeks, stay tuned! :)

P