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. 

Slog for Week 4

    In week 4, the professor Larry Zhang went over bi-implication, transitivity, and mixed quantifiers. At the beginning of the lecture, he began the lecture with explanation of why p => q equals to ㄱp  or q: because two statement have the same truth table. His explanation made me understood since I had not understood why those statements are equivalent. By knowing the concept, I have become to be flexible in many other questions related to it. Now I am familiar with De Morgan's Law, implication law, and so on.

   Also before I listened the lecture on Tuesday, I was not sure why the order of universal quantification and existential quantification makes difference, but now I have the idea why switching x and y, which are quantified, makes different statements. For example, the statements of 'For every women, there is a man who is her soul mate,' and 'There is a man, every woman is his soul mate.' have exactly different meaning by only switching the place of x and y. 

  Even though I understand most of lecture, there was the part I can hardly understood. In mixed quantifiers, the professor went over two mathematical examples, but I could not follow since I have no idea from the beginning of the example. I expected to get the ideas of similar questions from the tutorial, but we just did problems about bi-implication that I already had plenty of ideas.

   I might going to try to find the similar examples from the past tests that the professor put on the lecture slide, and to be able to solve them with many practices. 

 

Slog for Week 3

    For this week, the professor Larry Zhang went over the concepts of conjunction, disjunction, negation, and truth tables. Actually the parts of conjunction and disjunction were not that hard since it is easy to transfer from English language to symbols. I only need to be careful when the difference of uses of conjunction 'and', between the meanings of 'the actual and 'union'. Except these, nothing was difficult.
    Contrast to conjunction and disjunction, negation was hard for me. For example, I have no idea how and why the symbol of 'and' changes to the symbol of 'implies to'. I was trying to understand it by looking and finding in course notes, and websites, but I still do not get the concept at all. I believed I probably get some help on this concepts in tutorials, which I had today, but sadly it makes me more confused.
    In order to understand the negation part, I believe I need to go office hour on next week, which might be solve my problems. Moreover I think only understanding lecture slides is not enough, so that I need to find the problems relating to lecture from the website that I can work on.

Slog for Week 1 and Week 2

    For Week 1 and Week 2, the professor Larry Zhang went over the concepts of precision, problem solving and quantifiers, sentences, statements, predicates, and implications. Generally the lecture in Week 1 was not that difficult, because the way to solving problems and quantifiers such as universal quantification and existential quantification are the concepts I already used to it from my mathematical experience.
    However, the lecture I had in this week was not easy as the lecture in Week 1. Even though the part of 'quantifiers as claims about sets' was quite understandable since most of quantifiers are shown in Mathematic quite often, predicates and implications were terribly confusing concepts that were brand new for me. Firstly, I could not understand why does the example sentence, "x is a prerequisite of y" become to P(x,y). Secondly, I struggled to finding P and Q in the everyday language sentences, which the professor went over during lecture 2.3. First half of sentences were not that difficult although rest of them were really confusing. For example, from the sentence, "I will go only if you insist," I do not get why 'I will go' is P but not Q. In my way, I considered 'you insist' as Q because 'If you insist, then I will go' seems right rather than 'If I will go, then you insist.' Lastly, in equivalence, it was challenged to get the concepts the meanings of signs => (which means P only if Q ) and <= (which means P if Q).
    In order to overcome these difficulties, I have read the course notes that are relevant to content of lecture slides, and search additional information related to concepts throughout the internet, of course using reliable sources from university websites such as lecture notes from other universities. Also I found more examples of each concepts, especially predicates and implications, which are the hardest part I am struggling to.
    From the lectures of Week 1 and Week 2, I now decide to read the lecture notes prior to each lecture, and print the lecture slides before the lecture too. Listening lecture with some background knowledge from lecture notes might be helpful to understand the materials better, so that I will definitely do that from next week.