Week #11

This week is the last second week before the class ends, plus there is a fall break with two days off on Monday and Tuesday, which makes me excited. Although this week doesn't cover too many things, what we learnt, again, makes me confused. I heard that this is the last chapter for this course, which i think is also the most difficult part. Basically, what we need to do is to prove non_computable function and computable function using reduction, which is something related to halting function. I still have no idea about it until I see the course note from course website. I can understand the example that was given and structure is clear to me. But that it, I don't think I can solve the same type of question by myself. I really hope that there will be more examples with solutions on this type so that I could have a deep understanding. The following question is the one appears on the course note, which I think is pretty typical. At least, I think we can figure out the structure of same type of questions after understanding this example.
I also check other students' slog like http://davidhanslog.blogspot.ca/to see if we have the same problem on halting problem.And yes! Many people are confused by this kind of problem.

The following is an example using induction:

Week #10

This week, the second term test result has come out, which frustrated me. I remember that when I first saw the test paper, there were only three prove questions and it seemed like i had done them before because it looked familiar. But actually, like the last test, I spent too much time on the first two questions and when I moved on to the last question, I realized that I didn't have enough time to finish. After the test, I heard that the second question is the most difficult and the last one is pretty easy. But what I did is just opposite because I get a full mark of proof on questions two but get 0 on question three.That looks ridiculous. The most regretful thing is that the question that I get 0 is the one that appears on assignment2 which is just due before the test. Although I use a more complicated way to solve it in assignment , I should have done it on the test.I felt like I could have enough time to finish it, then I was so careful to do first two that I forgot the time, which is the main problem. Also, I always think that what if I get more familiar for the stuff that is tested, this result may not happen to me.

It has already been two tests, and only one final left. I can't loose chance to get high mark next time, so I really need to look everything carefully and get familiar with the whole bunches of knowledge that I have learnt in this course.

problem solving:

 if we want to prove something equal, we have to show as following:

Week #9

This week, we began to learn Big O and Big Omega and how to prove or disprove it. This part is pretty interesting, which, I think, is my favorite part in this course. The way we did the prove of Big O and Big Omega is quite different from that we did for other questions. Maybe that's why I like it:)
Although what we learnt this week is kind of easy to me, we have the second assignment that is due on Monday. Some them are pretty easy and we practice lots of time. But others seem not easy to solve like the following question.
∀ x ∈ ℝ, ∀ e ∈ ℝ!, ∃ d ∈ ℝ!, ∀ w ∈ ℝ, |x−w| < d ⇒ | x − w | < e
Here is the way I did:

    

Every time I see there are too many variables in a question, I feel confused and don't know which way should I do it first. However, there is something interesting hidden in this question, which is that this statement is actually a definition of continuous function. Since the graph of floor is obviously not a continuous function, we can say that this statement is False and we need to disprove it, which eventually gives me some ideas to solve the next question that looks similar to this one.
∃ x ∈ ℝ, ∀ e ∈ ℝ!, ∃ d ∈ ℝ!, ∀ w ∈ ℝ, |x−w| < d ⇒ | x − w | < e

Here is the way I did:

Week #8

This is the 8th week and we learn about counting steps using worst case.Basically, what it asks us to do is just counting how many times a line should run in python, which eventually has something related to the course csc108. Overall, this part is not so hard though as long as we understand the meaning of the code which is necessary to know in csc108. What's more, professor also talks a little bit about Big O. At first, I was really confused because there are too many variables in the definition. But later, after we did the prove stuff, I gradually figure out what does it mean and the definition seems pretty clear to me.

There will be a second term test next week, which mainly tests us how to prove based on what we learnt these weeks. I personally have more confidence on this test than on the previous one partly because I did very well on tutorials and the example test that was given to us is pretty easy. But still, I need to do much work to review just in case that there was any knowledge that I didn't cover before.I hope I can get a higher mark on it.

Problem solving:(counting steps)

week # 7

It's been seven weeks since this semester started, which means we are already in half way through the whole term. Every time I look at the stuff learned before, I feel like that the time in university goes so fast. This week, we are still continuing on proofs but more complicated than before, which is to prove by cases. This kind of proof is not hard but we have to separate it into several cases and prove every case in order to make a good proof. What's more, I think the most useful part during this week is to introduce some rules, which can also be seen as the conclusion of some basic and necessary rules of proof.
Elimination:
conjunction elimination: If you know A ^ B, you can conclude A separately (or B separately).
existential instantiation: If you know that there exists k in X, P(k), then you can certainly pick an element with that property, let k' in X, P(k').
disjunction elimination: If you know A or B, the additional information :A allows you to conclude B.
implication elimination: If you know A implies B, the additional information A allows you to conclude B. On the other hand, the additional information :B allows you to conclude :A.
universal elimination: If you know for all x in X, P(x ), the additional information a in X allows you to conclude P(a).
Introduction:
implication introduction:If you assume A and, under that assumption, B follows, than you can conclude A implies B.
universal introduction: If you assume that a is a generic element of D and, under that assumption, derive P(a), then you can conclude for all a in D, P(a).
existential introduction: If you show x in X and you show P(x ), then you can conclude not x in X, P(x ).
conjunction introduction: If you know A and you know B, then you can conclude A ^ B.
disjunction introduction: If you know A you can conclude A or B.
The most difficult part this week, which I think is the worst case by introducing two functions which are the upper bound O(U) and the lower bound. The formal definition was pretty complicated and confused when I first saw it. However, after understanding the actual meaning of them, it is much clearer to me. The issue is that I can understand it when I'm looking at the definition but can hardly write it down by myself. Therefore, it is probably a good idea by practicing related problems in order to get familiar with it.

week # 6

We have a long weekend  as Monday is a thanksgiving day, so we only have two lectures  and no tutorials this week. Personally I think the work in this week is much easier than that in previous weeks. And we are continuing on proof of different types of problems including the proof of non-boolean functions and limits as well as the proof of something false. Since we've already learned how to write the outline of a good proof on last week, it's not  as confused as I thought at the time in which I learned proving in MAT137. It's really helpful for me when the professor taught us the proof about limits with an example of asking us to proof the definition of the functions which is exactly the same as what I learned during MAT137 lectures. In fact, I've been frustrated and confused about those kind of questions for a long time and eventually, I chose to totally memorize them instead of understanding them. However, I got really excited when I saw this proof in165 lecture on Friday using the different way of thinking but the same solution. As a result,  I'm not as confused as before, and I even wanna go back to do all the questions that I didn't get one more time using the method I was learned in 165.

The following graph is a typical graph to illustrate the definition of limit:

week #5

Good news in this week was that I didn't lose mark on my quiz, but bad news was that we just had a test which is my first term test in university and more importantly I didn't even finish it. I focused on the first two questions which spent me lots of time and I didn't realize that the time passed so quickly. As a result, I had little time to think about the last question, which again, made me frustrated after the test. I think the most possible reason of this situation is that I'm not so familiar with those knowledge so that I'm afraid to make mistakes on them which at last waste me a lot of time. I'm on the way back and I have to catch up with other classmates and then keep pace with them. That's my foremost goal of 165 now. Thankfully, this week's work is to proof some fundamental questions, which means that I'm able to spend more time focusing on reviewing previous knowledge through my notes and lecture slides on course webpage.

Problem solving: