10th Week - Nov 14th

Hey, this is week- ten lecture, which is also the last second lecture before final exam. During this week’s lecture, the ideas of “Big-Omega, big-Theta and general properties” were introduced.

As far as I am concerned, proofs are still the key concepts. Not only the lecture but also the tutorial emphasizes proving a problem by using big-Omega and big-Theta this week. One typical example would be prove 5n^4-3n^2+1 ϵ O (6n^5-4n^3+2n). To solve this question, we need to do a draft sketch to see what is the meeting point between those two functions. Therefore, (6n^5-4n^3+2n) need to be eliminated and 5n^4-3n^2+1 should be introduced. By eliminating (6n^5-4n^3+2n), simply removing the positive terms in this function, which leads to (6n^5-4n^3). And we times 4n^3 by n^2, which makes the function to become 6n^5-4n^5 = 2n^5. Since n>=1, we know 2n^5 > n^5. Vise visa, we introduce (5n^4-3n^2+1) by removing its negative term, which results to (5n^4+1). Multiplying (5n^4+1) by n^4 since n>=1, getting 6n^4. Similarly, we can get n*n^4 = n^5 >=6n^4 if we assume n>=6. After the above preparation, we spot that ‘n^5’ is the meeting point of two functions.

Kay, now it’s time to write down the proof. We can tell that this is a case of universal quantifier since by writing in symbolic form, the question would be like ∃c ϵ R+, ∃B ϵN, ∀n ϵ N, n>=B => 5n^4-3n^2+1 ϵ O (6n^5-4n^3+2n). Therefore, assuming n ϵ N, and n >= 6 is the first step of this proof. Then it comes the mathematic equations we did before as the draft sketch. Following that, we reintroduce ∀n ϵ N, n>=6 => 5n^4-3n^2+1 <= O (6n^5-4n^3+2n) and state the whole conditions as “ Then ∃c ϵ R+, ∃B ϵN, ∀n ϵ N, n>=B => 5n^4-3n^2+1 ϵ C <= (6n^5-4n^3+2n)”. However, this is one thing we need to notice is that we should remark ‘Pick C=1, B=6’, otherwise, the above proof would not make sense. Finally, we can come with the conclusion that 5n^4-3n^2+1 ϵ O (6n^5-4n^3+2n) by definition.

Personally I think, the “Big-Oh” proof is not that difficulty. There is nothing to worry about as long as you do the calculation before ahead correctly and follow the structures well.

9th Week - Nov 7th

By looking backward, the school year has been past so quickly. On this week, the term2 test was given and three proofs were included on this test. Comparing to the first term test, I regarded this one was easier and I was pretty sure that I was able to do it better – I was quite comfortable with the proofs chapter and the questions given on the test were basically like those materials went over during tutorial. Therefore, personally I think there was nothing much to worry about for this test.

Besides the one-hour test, the topics about “Big-Oh of polynomials, non-polynomials, and limits” were taught through the rest of the lecture. Among them, the cases of “Big-Oh” were emphasized. What we normally do to solve “Big-Oh” problems is to pick C (some certain wisely chosen constant multiplier) and B (breakpoint). For example, if we want to prove 3n^2 + 2n ϵ O (n^2), we should always consider the picks of C and B first. In this case, the picks that C > 3 make sense because the coefficient number of the highest-term is 3. Besides, let’s assume n=1, then 3n² + 2n = 3 + 2 = 5 = 5n². Therefore, pick c = 5, with B = 1 is good after you double check with n equals other natural numbers. Since you are on the right track to start with, the rest part was nothing hard but just regular proofs.
 
 Another thing I want to talk about is this week’s tutorial. On this week, algorithm of a while loop functions is asked to consider about. The method talking about during tutorial was to examine form smallest part respectively, and finally we can count the number of steps. However, as far as I am concerned, it would be much easier if we only look at the analysis of the numbers, which just like a pattern observation.

As a brief summary, understanding is the most priority. But based on that, careful observation and considerate thinking are the key points.

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.