Simon Z : http://csc165f1.blogspot.ca/
Jerry Y: http://qhycsc165slog.blogspot.caCSC165 - SLOG
2014年12月2日星期二
12th Week - Nov 25th
This
is week 12, which is the officially last lecture for csc165. In this week, we
have learned countability, and a detailed review guide was talked during class.Speaking
to countability, comparing the sizes of two sets was taught first. Thinking of
comparing the size of two sets, there are actually three types of functions to
analysis: well-defined function, 1-1 function, and ‘onto’ function. A well
defined function a function that each x in function maps to a unique y; 1-1
function is each y mapped to by at most one x; while, ‘onto’ function is that
every y has some x, which maps to it. One typical example I want to talk is to
compare the sizes of X={natural numbers} and Y={even natural numbers}. At the
time when I first saw this problem, I thought Y was obviously smaller than X,
simply because Y was the set of even natural numbers which meant that Y was a
subset of X. I know a lot of people would come to the same answer as I do,
however, unfortunately, it is wrong. Actually, the two above have the same
sizes, because they are both infinite, and even though you match the numbers of
in each sets, they can be well defined.
Another specific question I want to talk about is the first question in this week’s tutorial: Prove “∀f: N->R>=0, ∀g: N->R>=0, g ϵ Ω(f) => g^2 Ω (f^2)”. Personally I think this is a typical prove example because all you need to do is to follow the structures have been taught so far. Therefore, the first step is to assume the domain which is written like “ Assume f: N->R>=0, ∀g: N->R>=0”. Then, antecedent needed to be written down which is “assume g ϵΩ(f)”. By doing the draft sketch, we know that if we want to say “ g>= C1*f ó g2 >=C1^2*f^2 ó g2>=C2*g2”, we have to assume C2=C1^2, and B2 =B1, which is the key idea for proving the problem. And the rest of the proof is nothing too much except the regular proving steps.
Literally,
this is all I want to say about this week’s lecture and tutorial. Good luck to
my peers and me to the final CSC165 final exam.
Another specific question I want to talk about is the first question in this week’s tutorial: Prove “∀f: N->R>=0, ∀g: N->R>=0, g ϵ Ω(f) => g^2 Ω (f^2)”. Personally I think this is a typical prove example because all you need to do is to follow the structures have been taught so far. Therefore, the first step is to assume the domain which is written like “ Assume f: N->R>=0, ∀g: N->R>=0”. Then, antecedent needed to be written down which is “assume g ϵΩ(f)”. By doing the draft sketch, we know that if we want to say “ g>= C1*f ó g2 >=C1^2*f^2 ó g2>=C2*g2”, we have to assume C2=C1^2, and B2 =B1, which is the key idea for proving the problem. And the rest of the proof is nothing too much except the regular proving steps.
2014年11月20日星期四
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.
2014年11月7日星期五
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.
As a brief summary, understanding is the most
priority. But based on that, careful observation and considerate thinking are
the key points.
2014年11月3日星期一
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.
订阅:
博文 (Atom)