Master Theorem

Today I learned Master Theorem. However, there are not many explanations on the course slides. I was still confused after I read the course notes because it doesn't mention what "d" is in the definition. So I found the clearer (for me, and hope helpful for others too ) version of Master Theorem here:

For the definition of T we have, we can easily use Master Theorem to find the bounds of T without unwinding.

In summary, when we have a definition of T and want to use Master Theorem, we do the following steps:

1. calculate n^log_ba

2. compare if f(n) either greater, less than or equal to n^log_ba
        if f(n) = n^log_ba , then T(n) = θ ( n^log_ba lg n)
        if f(n) < n^log_ba , then T(n) = θ ( n^log_ba)
        if f(n) > n^log_ba , then T(n) = θ ( f(n) )

The summary above just for general case, and understanding. For preciseness, please refer to the Theorem 4.1. =]

term test1 result and Predicate of Induction

I got my term test1 result today. I felt not bad when I just finished the test because I knew how to do every question. However the grade was not good for me. I made a mistake that shouldn't have happened.

As we made a predicate in such form "P(n): For every n belongs to N,13^n-1 = 12y where y is also a natural number. We prove that for all n belongs to N, P(n) by Mathematical Induction". We define what P(n) exactly is in this question, then we indicate that for all n belongs to N,P(n) and what type of Induction would we use. However, I wrote "P(n): For all n belongs to N,  and all y belongs to N,13^n-1 = 12y." which is completely wrong because we should use INDUCTION to do it . Then we can't say all n belongs to N inside the definition of P(n).

It seems like a stupid mistake. The test consists of 3 question and 5 marks each. It cost me 1 mark for every question. So due to this little problem, I lost 20%! I am so depressed about it. =[. That is my fault. I will do better next time and I won't make such a low level mistake any more! I will do better next time.

first midterm

I just came back from LM. Seems like could have a little break from the fast pace of preparing the test. Actually, i wanted to post a new blog yesterday when I was reviewing stuff. However i was too tired and fell in sleep. Haha, guess what? But I still took a picture last night, and it can show you the situation of last night instead of using words. Pretty hardworking right? (;p jkd)

For the preparation, I re-did every question on the
1. course slides
2. assignment
3. the sample test
4. I found the paper of last year.
After  a few practices, I found that the important thing is not just to write it, but we have to understand the principle behind a particular set of questions and better to find the pattern of the same kind of questions. For instance, when I see a question which asks about binary tree, the first thing I would think about is to divide the tree into left subtree and right subtree, then use complete induction to prove the statement is true. I have to make sure that I can solve a similar question use the particular induction method. That means I do understand how it works.
I was afraid that there will be one question like the round-robin tournament example on the week 3 slides. Honestly, I don't really understand this one which is the only one that I have no idea about. I will find the answer today. It is interesting.

ps.What on the test is easy to predict because all we have learned are four type of inductions. The probability of three of four, isn't it? ;p

LAND TO HERE

I had viewed a bunch of people's SLOGs before i started to write mine. The interesting thing here is that most of the first lines of those blogs are "Hello, World!"! Perhaps it's because that is the very first line that most programmers print in whatever language. =] I saw someone created their blog address as "i was force to make this slog" or something like that and someone even post a video named "Introduction to the theory of blogging "  It really makes me laugh out. Seems that SLOG is so much fun for us to learn this course.

This is my first time posting for my SLOG assignment. I am going to share more feelings, expriences, funny things and at times useful links or study methods in my blog. Hope my blog would help some students in this course.

Recently I am working on the next tutorial quesitons. I found that I am better on simple and complete induction rather than mathematical induction and well ordring. This pushed me to spend more time on the methods that I am not that skilled. Actually I searched more practices related to mathematical induction on internet and the materials from CSC165 as well. Wish I would do well on the quiz next week. =p

There is a SUPER useful link that contains teaching videos from wide topics of any level. This website gets thousands of videos of most of the subjects such as computer science, mathematics, algebra, calculus etc. and in a GREET ORDER.
www.khanacademy.org

sample video:

Hope you guys have fun with it. 

sep.25.2012

(posted on wrong website before.)  

TESTING TESTING

hi?
ignore me lol