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.