Journal 11 - Week 12

Friday   November. 28th   Sunny

This is gonna be the very end of our class. Wish you all get a good mark on final exam. By the way, the mark for assignment 2 has been posted. Let me talk about not just lectures and tutorial for this week. I want to list some tips for final exam here.

Firstly, we learned more deeply in countability and induction. Also, we got some tips for assignment 3. Professor help us do a brief review for final exam as well.

Secondly, I will not show some hard part or hard question here as usual since I want to say something about the final. There is no doubt that we need to carefully read the online slides and lecture notes. Also, we should understand our tutorial exercises, assignment questions and test questions. Some past exam has been posted. They are good materials help us go over the course but we should know that professor would not ask the same questions in our final.

Just a reminder that our final exam is on December 10th, 7:00-10:00pm. Please bring the aid sheet.

Thirdly, I read a journal for the final week wrote by a classmate. I was really moved by her words. 
The link of her slog is:
http://courseblog165.blogspot.ca/2014_12_01_archive.html
Hopefully you can read it too.

Lastly, our tutorial of this week is the last tutorial. Our TA taught us two sample questions about complicate functions. For now, what we are talking is not just f of n or g of n. We are talking about f of f(n) and g of g(n) instead. There is more possibility in these kind of questions.

This is the end of the journal.

Much appreciated for reading my journal.

See you next week :)

Journal 10 - Week 11

Friday   November. 21st   Sunny

Hi everyone. Hope you guys have a good rest during the Fall break. As we all know, we did not have class on Monday due to our Fall break, which means there was not too many contents covered in this week. Also, our tutorial for this week was cancelled. Thus, let me just talk about the rest two lectures.

Firstly, algorithm and contradictory program are two important contents of Week 11. Although algorithm is no more a new topic, we still got something new. On the other hand, the definition of computable and non computable functions are introduced. We talked a little bit about reductions and how we can use reduction into our proof as well.

I found a good slog posted by my classmate which talks about countability. 
The link is:

http://165choi.blogspot.ca/2014/11/inducin-it-and-lovin-it-more.html

He also summarized some methods for induction.

Secondly, I will talk about the hardest part this week and how I am trying to make it easier for myself. When we are proving a function to be uncomputable, we need another function (like halt as we did in class) to reduce them. We also need to write down some helper functions. This is hard for me to do at first. After I did a lot of exercises, I feel better now.

Thirdly, I chose one of the proof questions from assignment 3, which follows as below.

Q: Prove that the functions meaning_of_life below is not computable.

def meaning_of_life(f, I):

      “””

      Return True if f(I) returns 42, False otherwise.

      “””

Proof:

Assume that meaning_of_life is computable.   # for a contradiction

       def halt(f, i):

             def meaning_of_life(g, v):

                      """

                      Return True if g(v) returns 42, False otherwise.

                      """

             def f _prime(x):

                     f(i)

                     exec(“return” + 42)

             return meaning_of_life(f_prime, v)

       If f(i) halts, then f_prime(x) will execute the statement return 42, 

       so meaning_of_life(f_prime, v) returns True and halt(f, i) returns True.

       If f(i) does not halt, then f_prime(x) never executes return 42(no matter what                  value x has), so meaning_of_life(f_prime, v) returns False and halt(f, i) returns                  False.

Hence, there is no Python implementation of function meaning_of life.

Hence, the function meaning_of_life is not computable.

Lastly, again, our tutorial was cancelled, so I will not talk about the tutorial.

This is the end of the journal.

Much appreciated for reading my journal.

See you next week :)

Journal 9 - Week 10

Friday   November. 14th   Sunny

I got my mark for test 2 which is 30/30, another full mark. Thanks a lot to my TA and professor’s help. I will continue to show my effort until the end of course. In this journal, I will talk about both contents covered in our lectures and tutorial.

Firstly, as usual, I will introduce the materials from this week. Professor made an introduction to computability this week. We did more examples for big-O proofs for general functions. Also, we did some example questions related to big-Ω, which is similar as big-O but different from it.

Secondly, Let me talk about the tricky part about big-Ω. The definition of Ω looks pretty similar as that of O. However, they are different, especially if you draw some pictures to compare them. This concept challenged me, so I did a lot of exercises about big-Ω proof and feel much better for now.

Thirdly, I chose one of the proof questions in my exercise, which follows as below.

Q: Prove: ∃ c ∈ R⁺, ∃ B ∈ N, ∀ n ∈ N, n ≥ B ⇒ (6n³ - 4n² + 3n + 2) ≥ c(5n³ - n² + n + 1)

Proof:

Let c = 1. Then c ∈ R⁺.

Let B = 3. Then B ∈ N.

Assume n ∈ N.

       Assume n ≥ B.

              Then 6n³ - 3n² + 2n + 1 ≥ 6n³ - 3n².   # since n ∈ N

              Then 6n³ - 3n² + 2n + 1 ≥ 6∙3³ - 3∙3²   # since n ≥ B = 3

                                                         ≥ 6∙3³ - 3³

                                                         ≥ (6 - 1)∙3³

                                                         ≥ 5∙3³

                                                         ≥ 5n³   # since n ≥ B = 3

              Then (6n³ - 3n² + 2n + 1) - n² + n + 1 ≥ 5n³ - n² + n + 1   # add - n² + n + 1 to                                                                                                                            # both sides

              Then 6n³ - 4n² + 3n + 2 ≥ 5n³ - n² + n + 1

                                                         ≥ c(5n³ - n² + n + 1)   # since c = 1

       Then n ≥ B ⇒ (6n³ - 4n² + 3n + 2) ≥ c(5n³ - n² + n + 1)

Then ∀ n ∈ N, n ≥ B ⇒ (6n³ - 4n² + 3n + 2) ≥ c(5n³ - n² + n + 1)

Then ∃ c ∈ R⁺, ∃ B ∈ N, ∀ n ∈ N, n ≥ B ⇒ (6n³ - 4n² + 3n + 2) ≥ c(5n³ - n² + n + 1)

Lastly, our tutorial of this week focused on the big-O proof structures. Something deserves to be mentioned is that some of my classmates asked me how we can directly find the relationship between f(n) and g(n). I think we cannot just “look” and “guess” to set up the inequality between f and g. What we should do is to notice the degree of each n, and pay attention to constant in f and g. Using simple algebra to make it from a simple inequality to the complicate one step by step.

This is the end of the journal.

Much appreciated for reading my journal.

See you next week :)

Journal 8 - Week 9

Friday   November.7th   Sunny

This week is special again, since we had our term test 2. Also, solutions for assignment 2 have been posted. Carefully reading those solutions would be a good review. In this journal, I will talk about both contents covered in our lectures tutorial for week 9.

Firstly, as usual, I will introduce the materials which are new to us from this week. Due to test 2, we just have two lectures this week. Professor showed some exercises of big-Oh proofs and introduce how to prove big-Oh using limit techniques as well.

Secondly, I will talk about the hardest part this week and how I am trying to make it easier for myself. Of course that the combination of limit and big-Oh is a difficult topic, but I think it is also interesting. As a mathematics student, I was really happy I could use L’hopital in a computer science course since I was familiar with that. I did some exercise for reviewing application of L’hopital and feel great.

Thirdly, I would not show a to prove as what I usually did, but show a specific example about how to apply L’Hopital. This is because I know how important this application is.

   lim  n²   =    lim           2n        =        lim              2                =  0

 ^n→ ∞ 2^{n      n→} ∞   2ⁿ × ln2        ^n→ ∞  2ⁿ × ln2 × ln2           

I understand many of you are not in Mathematics program. I found a slog wrote by my classmate which help you guys review concepts for limit. Here is the link:
http://zhexinlai.blogspot.ca/2014/11/why.html

Lastly, our tutorial of this week helped us do calculation about algorithm. What I think is pretty important is that, we should record each time according to the specific question. I mentioned this here since even if a same function, the worst-case and the best-case would get totally different answer.

This is the end of the journal.

Much appreciated for reading my journal.

See you next week :)

Journal 7 - Week 8

Friday   October. 31st   Sunny

Hi everyone. Just a reminder that Assignment 2 is due next Monday. Also. term test 2 is in the next week. Don’t be worry about the busy coming week. Hopefully my journal could be a good review for everyone to prepare for test 2. 

Firstly, I will talk about something new to us in week 8. Formal definitions of O and Ω have been explained to us this week. Let me specify these two definitions here because they are very important. They follows as below.

A function f(n) is in O(n²) if and only if ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ f(n) ≤ c∙n²

A function f(n) is in Ω(n²) if and only if ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ f(n) ≥ c∙n²

We need to notice that the difference between O and Ω is that O is an upper bound and Ω is a lower bound. They are not easy to remember but we can do more exercise to get more familiar with them. Also, we can write them on our aid sheet during the tests and exam. 

I found a very interesting slog wrote by my classmates which talks about big-oh.
The link is as below:
http://165choi.blogspot.ca/2014/11/my-knowledge-is-getting-big-oh.html
If you still get stuck with the big-oh. Hopefully our slogs can help you.

On the other hand, we discussed worst-case analyses of two algorithms. This means we are starting to analysis more deeply with course contents, not just symbolization and proof, but how it works and why it works. 

Secondly, I will talk about the hardest part this week and how I am trying to make it easier for myself. Big-oh is about functions, which is harder than numbers and sequences which we learned before, since numbers will change by functions. This new concept challenged me, so I did a lot of exercises about big-oh of n² and feel much better for now.

Thirdly, I chose one of the proof questions in my exercise, which follows as below.

Q: Prove: ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

It is obvious that we need the definition of big-oh.

A graph could make the relationship between f(n) and g(n) more clear.

Proof:

Let c = 1. Then c∈R⁺.

Let B = 6. Then B∈N.

Assume n∈N.

       Assume n ≥ B.

              Then 5n⁴ - 3n² + 1 < 5n⁴ + 1

                                               ≤ 5n⁴ + n⁴ 

                                                = 6n⁴ 

                                               ≤ n⁵  ≤ 2n⁵ 

                                               ≤ 6n⁵ - 4n⁵ 

                                               ≤ 6n⁵ - 4n³ ≤ 6n⁵ - 4n³ + 2n

       Then n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

Then ∀n∈N, n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

Then ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

Lastly, our tutorial of this week focused on proof by cases. One of the questions I have clearly explained in my last journal, which talked about proof by cases a lot. I think it is useful so I would not duplicate that topic.

This is the end of the journal.

Much appreciated for reading my journal.

See you next week :)

Journal 6 - Week 7

Friday   October. 24th   Windy

Hi everyone. Most of us have got our mark for assignment 1. The average is very high. Well done! Meanwhile, assignment 2 has been posted. Let’s show more effort. In this journal, I will talk about both contents covered in our lectures and tutorial for week 7.

Firstly, as usual, I will introduce what we have learned this week. Professor taught us proof by cases and then review all the other proofs we have talked about before. Also, we starts a new topic which is “algorithms”. For those who are taking of have already taken CSC148H1 would be quite familiar with algorithms.

Secondly, I will talk about the hardest part this week and how I am trying to make it easier for myself. I think proof by cases is a challenge for me. It is not as straightforward as the methods we learned before. For example, if we are not sure the number we are using is even or odd, at this time, we need to prove in each case. I usually forget to divide them into two cases. To deal with this problem, I did a lot of exercises about proof by cases and feel much better for now.

Thirdly, I chose one of the proof questions in my exercise, which follows as below. Since I have talked about the cases when we can not decide if a number is even or odd, I want to introduce another type of proof by cases question.

Q: Prove: ∀x, y∈R, x⁴ + x³y - xy³ - y⁴ = 0 ⇒ x = y ∨ x = - y

Proof:

Assume x, y ∈ R.

       Assume x⁴ + x³y - xy³ - y⁴ = 0.

              Then x³(x + y) - y³(x + y) = 0

              Then (x + y)(x³ - y³) = 0

              Case 1: Assume x + y = 0.

                     Then x = y ∨ x = -y

              Case 2: Assume x³ - y³ = 0.

                     Then x³ = y³

                     Then x = y ∨ x = -y

              In both cases, x = y ∨ x = -y

       Then x⁴ + x³y - xy³ - y⁴ = 0 ⇒ x = y ∨ x = - y

Then ∀x, y∈R, x⁴ + x³y - xy³ - y⁴ = 0 ⇒ x = y ∨ x = - y

Lastly, our tutorial of this week help us do the complete proof, not just proof structure any more. One of the most interesting one is question 1/(b). In this question, both of the antecedent and conclusion are existential statements, which means when we make an assumption for the antecedent, what we actually assume is an existential statement, not just a number. This is a trick point we need to pay attention on test.

This is  the end of the journal.

Much appreciated for reading my journal.

See you next week :)

Journal 5 - Week 6

Friday   October. 17th   Sunny

This week, I have got my mark for test 1 and it is 38/38. Much appreciated for my TA and professor’s help. I will continue to show my effort. Due to thanksgiving day, our tutorial for this week was cancelled, so I would just talk about contents covered in our lectures in this journal.

Firstly, as usual, I will introduce something new to us in this week. We learned more typical examples for proofs. They are proof about non-boolean functions, proof something false, and proof about limits. All of them are interesting because they have relationships with mathematics. As I have said, I am a Mathematics student, so this really attracts me a lot.

A brief but pretty good slog about proofs which was posted by my classmate:
http://csc165progress.blogspot.ca/2014/10/a-short-week-in-review-more-proofs-and.html

Secondly, I will talk about the most challenged topic for me this week and how I am trying to make it easier. We always pay attention to how to “prove” a statement. However, starting from this week, we will not just “prove” but also “disprove”. For those false statement, we need to negate the whole sentence, and then prove this negation. This new method for proof is kind of difficult for me, so I did a lot of exercises about proof something false and feel much better for now.

Thirdly, I chose one of the proof questions in my exercise, which follows as below.

Q: Prove or disprove: ∃x∈R, ∀y∈R, y > x.

I will not use graph this time, since obviously we need to disprove it.

Let’s negate the whole statement first.

¬(∃x∈R, ∀y∈R, y > x)

⇔ ∀x∈R, ∃y∈R, y ≤ x

Now we can prove the negation.

Proof:

Assume x∈R.

       Let y = x = -1.

       Then y∈R.   # since x, -1 ∈ R, R closed under addition

       Then x - 1 ≤ x

       Then y ≤ x

       Then ∃y∈R, y ≤ x

Then ∀x∈R, ∃y∈R, y ≤ x

We have done!

Again, no tutorial this week, so this is the end of the journal.

Much appreciated for reading my journal.

See you next week :)