8th Week - Nov1st

This is the last lecture before term2 test and this week’s topic is about counting steps, worst-case, and formal big-oh.

I actually found myself quite comfortable with the lecture contents of this week. Among all the key concepts being talked, ‘two worst cases’ was emphasized. It is saying “a function f(n) is on O(n^2) iff ∃c ϵ R+,∃B ϵN, such that ∀n ϵ N, n>=B =>f(n)<=cn^2”, which is called upper-bound. Therefore, if “a function f(n) is on Ω (n^2) iff ∃c ϵ R+,∃B ϵN, such that ∀n ϵ N, n>=B =>f(n)>=cn^2”, it is called lower-bound. Besides, ϴ(n²) stands for set of functions that are in both O(n²) and Ω(n²) which means functions growing as fast as n². In this case, there is nothing to worry about because it is pretty straight forward -- what we need to do is to tell whether a given function is upper-bound or lower-bound.

Another interesting example would be the problem solving of penny piles at the end of the lecture. It says that “you are sitting in front of two drawers, and the left drawer contains 64 pennies, while, the right drawer contains nothing”, and you are asked to arrange things so that one of the drawers has exactly 48 pennies by transferring half of the even pennies to the other drawer (if the drawer has an odd number of pennies, operation is disallowed). The solution of the problem could be varied, but the easiest way is to draw a “tree diagram”. In this case, we want to achieve [48, 16], so we could know that the case before is [56, 8], and [60, 4] comes before [56, 8], then we can tell [64, 0] comes the first, which again is the original situation. Therefore, you can achieve any arrangement of the numbers that in the range [0, 64].

Lastly, this week’s tutorial was still about proof, which was the contents I was quite comfortable with, and I achieved a pretty good mark on the last week’s quiz. Everything seems getting better to me, and finally, wish myself could make a great progress in term test 2.