Slog for Week 12

Since we did not have lecture last week because of the reading week, this week's lecture and tutorial was the last one in this semester. For the last lecture, I learned about countability and Induction. But the professor just skimmed through induction part, which means he did not explain much details for induction, therefore I do not have much ideas about induction I learned.

For countability, when the professor Larry first asked us about what do we think the size of all even numbers and all natural numbers, of course, I thought the size of all natural numbers would be greater than the size of all even numbers, but actually the result was the same. Of course, this made me surprised, since it is obvious that the size of even number is only half of size of all natural numbers. However, soon I understood why those two are same: because of satisfaction of three characteristics. Since f is a well-defined function, '1-1', and 'onto', the two function is said to be same, therefore the size of natural numbers and even numbers can be said as the same.

But the part of combination of computability and countability, I hardly get the ideas what is going on there, so I think I need to read the lecture slide and course notes over and over until I understand it. Also the induction, even though I totally understood the proof of domino falls, I do not know how it can be used in the proof of some questions like a question in our assignment. But I hope this kind of problems I may see on the next semester in CSC240.

This was what I learned in this week, and all I need to do now is reviewing the whole chapters, especially what I learned in the beginning of this course(since I forgot many of them), and then practicing them by doing past exams in the University of Toronto website.

Slog for Week 10

For this week, we learned about the big omega proof and the big oh proofs for general functions. Since big-Omega proofs were mostly similar to big-oh proofs, therefore proving big-omega was not hard as we first learned about proofs of big-oh. Professor's summary about under-estimation and over-estimation really help me to follow the step: for under-estimation, removing positive terms or multiplying negative terms while removing negative terms or multiplying positive terms for over-estimation. But we never changed the highest degree.

During the lecture, I felt uncomfortable about finding the values of C and B, but I have become confident to choosing the values of C and B after the tutorial I had on Thursday because TA explains detailed steps to find the values and proof structures too. Moreover his teaching of various ways to approaching method helped me to think and prove in right way which is an appropriate method to the problem.

For the general statements about big-Oh, similar to proofs of big-Oh and big-Omega, I still confused to choose the values of B and C because now I have big-Oh and big-Omega in just one statement. I do not know when I need to use max(B, B') and choose B' = B something like that.

I believe I feel more comfortable as I solve many problem sets, and read course notes. Also next Tutorial would help me to figure out how to choose the appropriate values of B and C.

Slog for Week9

For this week, we had term test 2, which was about 3 proofs question. Since all three questions were pretty similar to the assignments, and the proofs the professor Larry Zhang explained during the lecture, I think this was not that hard. But I still feel uncomfortable with the question 2 in the term test2, which was about the mixture of definition of limit and definition of floor function. I think it would be better to go to the office hour after I received the test back to make sure the question 2.

For the lecture, the professor went over the proofs of big oh: the proof of big oh without constant value, the proof of big oh with constant value, and the proof using limit definition. He explained how to pick the value of c and b, which I mostly feel difficulties although I still don't feel comfortable about it. Especially on the part of disproving, I do not understand why he picked the value of n as maximum of the ceiling function of '3c' and B. Since I find the same difficulty again and again, I feel I must go to the office hour to perfectly solve the difficulty I have: picking the value(I don't know why sometimes we need to pick the maximum or minimum of two given values, while sometimes we just picked one specific value.)

Moreover, we learned L'Hopital's rule for non-polynomials big-oh proof. Because I have already known this rule from the calculus, this part was quite understandable. However I feel I need lots of practices to become familiar to big-oh proofs, and should go for office hour to get the help.

Slog for week 8

For this week, the professor Larry Zhang explained the formal definitions of  O and big omega and analyses of two algorithms. Since O and big omega are the concepts he explained last week, the definition was easy to understand: O(n) means the set of function that grows no faster than n, big omega(n) means the set of function that grows no slower than n. Therefore when we look at the graphs of f(n), then the graph of O(n) is upper-bounded while big omega(n) is lower-bounded.

Moreover, the second half of the lecture was about analyze a sorting algorithm, and proving the worst case of insertion sort. The professor divided the python function into three parts, then counted the number of steps needed in order to run the function. And this number of steps are written as sigma notation: this part was surprising because I never expected python function can be represented to sigma notation form.

But the part of picking the reasonable values is still pretty hard, and also determining whether the statement is true or not is hard. I know it can be solved if I solve the many questions as possible so that get familiar to the various kinds of questions.

Slog for Week 7

For Week 7, the professor Larry Zhang went over more proofs, disproofs, and the new concept, algorithm. For the part of proofs and disproofs, I feel like they are a little more detailed contents from last week, so do not feel very difficult. Also in the Tutorials, we did same problem sets again, so that I feel comfortable with how to find specific number or notation.

For the other part of lecture, the lecture about algorithm, although I have no idea at all when I first heard it, but I suddenly understood what is algorithm by watching the running time visual program, which the professor showed. The fact constant factor do not matter from the running time was surprised even though it is only for the highest-order term matters. 

Except them, we just learned two new notation called asymptotic notation, and how to count the steps in the linear search, which I am really familiar with because of my experience from CSC108.

Slog for Week 6

For this week, we got back the term test 1 result. I was surprised with the high average but since it means that everyone is working hard, I feel like I need to work more hard too.
From the result of test 1, I was able to know which part I am weak of: the part which is required to prove whether the original statement is true or the negation of it is true. Although I figured out I was weak of that part before the test, hence I really focused on that part, I still could not get the way to solve the problem.
Since I realize that it is not possible to figure it out myself, I would go to office hour on next week.

For the lecture on this week, it was advanced version of the last lecture. When we only did how to make a structure of proof last week, this week we started to construct the real proof with estimating the exact value. I understood most of the parts, but still confused with some parts of proof, for example in a backward search, how the sign of <= changes to <. I am going to read the course notes first to help my understanding first, then I will use the office hour next week with the question from the term test 1.

Slog for Week 5

    In this week, I had a term test one based on week 1 to week 4. To prepare the test, I reviewed the whole lecture slides, course notes, the professor Larry Zhang covered, and several past tests. Therefore the term test 1 was not that bad since the questions were similar with the past test, which is uploaded in course website. While question one in the test was pretty easy, question two was pretty challenging since it was the part I struggled with the most. I still feel uncomfortable with the problems that ask about which statement is true and which one is false between the original statement and its negation.

    If I could prepare that part more, it would be better I think. For the next term test, I will prepare and study whole parts without struggles. 

    For the lecture in this week, the professor went over the topic of proof. Especially the proof by contradiction and contrapositive. For me, this week's lecture was quite understandable since questions and explanations were straightforward enough, and not complicated yet. However if we go over more, and learn the direct proof, I know it will be more challenging. 

    Therefore, I am going to pre-read the course notes before the lecture, and work on the corresponding problems from the websites.