Week 8 Slog:
This week's lecture consisted the formal definition of O and Ω, worst case analyses and problem solving session. The formal definition for O is "a function f(n) is in O(n^2) iff there exists c in positive real and natural number B such that for all natural numbers n, if n greater than or equal to B, then f(n) is less than or equal to c". At first, this definition was very difficult for me to understand because the idea of breaking point B seemed vague. Luckily, professor spent time talking about this term and used a very good example, which was the idea that 'a chicken grows slower than a turkey after a certain break point." Similarly, a function growing slower than cn^2 beyond a breaking point can be classified as O(n^2). Conversely, the idea of Ω is "beyond a breaking point, function f(n) will always be less than cn^k, where k is a natural number. I find these idea very interesting.
The next section of the lecture was very challenging as it combined coding problems and analyzing worst cases. Initially, the while loop in the examples function body was very difficult for me to understand since I do not often use while loops. Fortunately, my peers are experienced coders and they broke down the code step by step to me. Overall, I found calculating the worst case run time fairly challenging as it required strong code reading skills, yet I believe I would be able to solve these problems with practices.
Thursday, 30 October 2014
Thursday, 23 October 2014
SLOG Week 7
Week 7:
This week's lecture focused on writing proofs, which was similar to last weeks lecture. The first part of the lecture looked at proving by cases. From the lecture, I learnt to split my arguments into different cases and prove them independently. This enables me to cover all possibilities and I found such method to be very useful, especially when proving odd and even cases. By reviewing the proof structure learnt in the previous two lectures, I found it very easy to follow every step professor Zhang showed and I really felt my ability to prove statements improved in these few lectures. Then, we looked at proving statements involving predicates and symbols. This part of the lecture was very difficult to follow as I had trouble understanding predicates at first. To overcome the challenge, I asked professor during the break and clarified my confusion. I looked at the proof for "if n is divisible by 7, then n^2 is also divisible by 7", This time through, I was able to understand it fully.
The next part of the lecture consisted algorithm analysis and asymptotic notation. This part of the lecture was not related to the previous weeks hence I found it hard to follow the slides, in particular, the ways to separate better algorithms from good algorithms. Through the lecture, I learnt 3 important ideas/ concepts, which were "running time" means "the number of steps that are taken by the algorithm", "running time is independent of hardware" and "a good algorithm is determined by how the number of steps grows as the size of input increases". These definitions helped me understand the lecture well. Afterwards, we were introduced to the asymptotic notation O(f(n)). This notation helps computer scientists to see the order of the algorithm and how much its steps grow when data size increases. I find this part of the course very interesting as I have always been interested in making algorithms efficient and this field relates closely to my interest. Overall, I find this lecture very enjoyable.
This week's lecture focused on writing proofs, which was similar to last weeks lecture. The first part of the lecture looked at proving by cases. From the lecture, I learnt to split my arguments into different cases and prove them independently. This enables me to cover all possibilities and I found such method to be very useful, especially when proving odd and even cases. By reviewing the proof structure learnt in the previous two lectures, I found it very easy to follow every step professor Zhang showed and I really felt my ability to prove statements improved in these few lectures. Then, we looked at proving statements involving predicates and symbols. This part of the lecture was very difficult to follow as I had trouble understanding predicates at first. To overcome the challenge, I asked professor during the break and clarified my confusion. I looked at the proof for "if n is divisible by 7, then n^2 is also divisible by 7", This time through, I was able to understand it fully.
The next part of the lecture consisted algorithm analysis and asymptotic notation. This part of the lecture was not related to the previous weeks hence I found it hard to follow the slides, in particular, the ways to separate better algorithms from good algorithms. Through the lecture, I learnt 3 important ideas/ concepts, which were "running time" means "the number of steps that are taken by the algorithm", "running time is independent of hardware" and "a good algorithm is determined by how the number of steps grows as the size of input increases". These definitions helped me understand the lecture well. Afterwards, we were introduced to the asymptotic notation O(f(n)). This notation helps computer scientists to see the order of the algorithm and how much its steps grow when data size increases. I find this part of the course very interesting as I have always been interested in making algorithms efficient and this field relates closely to my interest. Overall, I find this lecture very enjoyable.
Thursday, 16 October 2014
Week 6
Week 6 Slog:
This week's lecture focuses on completing proofs with proof structure. The first part of the lecture focused on the new non boolian function "floor" and "ceiling". Initially, I found it very difficult to understand the proofs Prof Zhang showed us because I found it very difficult to create logical links between mathematical statements full of symbols. Yet, as the lecture goes on, I realized that the reason for such confusion was due to that fact that I was unfamiliar with the definitions. After spending the break rereading the definition of floor and ceiling function, I felt much more comfortable with understanding the proofs. Furthermore, to start a proof, I realized the importance of beginning from the basic definition because these are the only information we know from a mathematical statement. This was something I found very useful and can be applied in my mathematics courses.
The second part of the lecture focused on methods of disproving statements and proving sequences. From this part of the lecture, I understood the importance of learning logic statements as now I grasped the idea that to disprove something, we would just have to prove the negation of the statement true. We applied this technique to disproving statements about sequences and I was able to follow the proof completely since I spent time digesting the meaning of the statement given. The final part of the lecture was the most challenging aspect as we had to prove limits. Fortunately, I learnt the concept of delta and epsilon in MAT 137 which enabled me to focus on the prove structure mainly instead of the concept. Using the skills learnt from previous lectures, I was able to reproduce these proofs by going step by step slowly and state the quantifiers respectively. Noticing how we were starting to use the ideas learnt previously to prove practical problems, I felt very satisfied as I was able to make all the logical links together and write organized proofs.
This week's lecture focuses on completing proofs with proof structure. The first part of the lecture focused on the new non boolian function "floor" and "ceiling". Initially, I found it very difficult to understand the proofs Prof Zhang showed us because I found it very difficult to create logical links between mathematical statements full of symbols. Yet, as the lecture goes on, I realized that the reason for such confusion was due to that fact that I was unfamiliar with the definitions. After spending the break rereading the definition of floor and ceiling function, I felt much more comfortable with understanding the proofs. Furthermore, to start a proof, I realized the importance of beginning from the basic definition because these are the only information we know from a mathematical statement. This was something I found very useful and can be applied in my mathematics courses.
The second part of the lecture focused on methods of disproving statements and proving sequences. From this part of the lecture, I understood the importance of learning logic statements as now I grasped the idea that to disprove something, we would just have to prove the negation of the statement true. We applied this technique to disproving statements about sequences and I was able to follow the proof completely since I spent time digesting the meaning of the statement given. The final part of the lecture was the most challenging aspect as we had to prove limits. Fortunately, I learnt the concept of delta and epsilon in MAT 137 which enabled me to focus on the prove structure mainly instead of the concept. Using the skills learnt from previous lectures, I was able to reproduce these proofs by going step by step slowly and state the quantifiers respectively. Noticing how we were starting to use the ideas learnt previously to prove practical problems, I felt very satisfied as I was able to make all the logical links together and write organized proofs.
Wednesday, 8 October 2014
SLOG: Week 5
The fifth week of CSC165 was particularly challenging as it was the first time we have to perform what we have learnt in the previous weeks on a mid term test. The test focused mainly on logic in particular the usage of quantifiers, the use of negation to mathematical symbols, and how to interpret different logical statements. Since this was the first test in my university life, I was fairly nervous when I got in the lecture hall. Yet, knowing I have tried my best to prepare for the course materials, I was able to think clearly throughout the test and I managed to complete the exam. The lecture this week primarily targeted upon how to proof mathematical statements. Proving one mathematical statement requires a logical and coherent structure, and we were able to quickly realize this after the exam when prof Zhang humorously showed "If you did bad, then it is not bad", as he proved to us that even if we left all questions blank, we will only be 3% below average in terms of final grade.
The first half of the lecture looked at how to proof using contrapositive and contradiction. From the week before, we were given a statement to prove "for all natural numbers, if n is odd, then n^2 is odd". This proof can be conducted using direct proof, which is proving directly from left to right by using n = 2k+1 (property of odd). However, if the statement is "For all natural numbers, if n^2 is even, then n is even", writing a direct proof can be difficult since we have to take the square root of n. Knowing the fact that the contrapositive of a statement is just equivalence to the statement itself, we can write a much easier proof using countrapositive, since we can simply apply the proof we learnt last week, which is "if n is odd, then n^2 is odd." From this, we can overcome the challenge of complicated algebra and cases when we cannot simplify expressions. The next part of the lecture looks at the use of contradiction, which uses the logic that if the negation of a statement is false, then the statement must be true itself. Since these proof methods were logic we learnt in previous lecture, I found it enjoyable applying them to mathematical problems, in particular, the problem about there are finite amount of prime numbers. It was challenging at first to understand the proof completely as there were many logical steps which I had to follow. But I overcame the challenge by working alongside with my peers.
Finally, the second half of the lecture looked at proof for existence and about sequences. We have covered how to proof for existence before, which was simply find one example that satisfies the statement. However, proving about sequences was the hardest part of the lecture as we had to understand fully what a statement is implying. This required combining all we learnt in the past 4 weeks and chaining all symbols, order of quantifiers and implications together. Initially, I did not have any idea about how to start writing the proof. However, by reading the steps of the proof one by one slowly, I managed to chain the logical links together and understand fully how our prof was about to prove the statement fully. Ultimately, I hope the proof structures learnt in this course can be transferable to my studies in mathematics.
Finally, the second half of the lecture looked at proof for existence and about sequences. We have covered how to proof for existence before, which was simply find one example that satisfies the statement. However, proving about sequences was the hardest part of the lecture as we had to understand fully what a statement is implying. This required combining all we learnt in the past 4 weeks and chaining all symbols, order of quantifiers and implications together. Initially, I did not have any idea about how to start writing the proof. However, by reading the steps of the proof one by one slowly, I managed to chain the logical links together and understand fully how our prof was about to prove the statement fully. Ultimately, I hope the proof structures learnt in this course can be transferable to my studies in mathematics.
Thursday, 2 October 2014
Week 4 SLOG - Galex Wong
Week 4 SLOG:
This weeks lecture focused primarily on the Bi implications, transitivity, mix quantifiers and proofs. I found the first hour of the lecture very challenging as it required us to try show equivalence of different implications. I found it difficult initially as I was not very familiar with laws such as De Morgan law and proving bi implications required us to be able to perform boolian algebra. I overcame this by drawing a truth table for each case and slowly noticing a pattern for performing boolian algebra. For instance, P implies Q can be expressed as not P and Q. The next part of the lecture talked about transitivity. Since I have noticed how to rearrange boolian expressions, this part of the lecture became fairly easy. These concepts were something new I learnt this week.
The next part of the lecture showed me how important the order of quantifiers are in a statement. The examples "For every woman, there is a man who is her soul mate" and "There is a man, every woman is his soul mate" aided me to understand the difference between placing existential quantifier first and universal quantifier first. After these examples, professor Zhang presented a more mathematical example which I learnt in MAT137, the formal definition of limit. By going through mix quantifiers, I realized this helped me to understand the idea of limit even better since our lecture used graphical representations. Hence I found this lecture very helpful for my studies of math as well.
The final hour of the lecture focused on writing proofs. While I have experience proving mathematical statements in the past from studying discrete mathematics, I still found writing proofs for computer science challenging since it is more logic based instead of arithmetically based. For instance "(P => R1) and (P => R2) is equivalent to (P => (R1 and R2))". To overcome the problem, I have followed closely to Polya's problems solving scheme, which I found really helpful. Overall, I am fairly confident about the course material this week and I hope I will be prepared for the upcoming mid term exam!
This weeks lecture focused primarily on the Bi implications, transitivity, mix quantifiers and proofs. I found the first hour of the lecture very challenging as it required us to try show equivalence of different implications. I found it difficult initially as I was not very familiar with laws such as De Morgan law and proving bi implications required us to be able to perform boolian algebra. I overcame this by drawing a truth table for each case and slowly noticing a pattern for performing boolian algebra. For instance, P implies Q can be expressed as not P and Q. The next part of the lecture talked about transitivity. Since I have noticed how to rearrange boolian expressions, this part of the lecture became fairly easy. These concepts were something new I learnt this week.
The next part of the lecture showed me how important the order of quantifiers are in a statement. The examples "For every woman, there is a man who is her soul mate" and "There is a man, every woman is his soul mate" aided me to understand the difference between placing existential quantifier first and universal quantifier first. After these examples, professor Zhang presented a more mathematical example which I learnt in MAT137, the formal definition of limit. By going through mix quantifiers, I realized this helped me to understand the idea of limit even better since our lecture used graphical representations. Hence I found this lecture very helpful for my studies of math as well.
The final hour of the lecture focused on writing proofs. While I have experience proving mathematical statements in the past from studying discrete mathematics, I still found writing proofs for computer science challenging since it is more logic based instead of arithmetically based. For instance "(P => R1) and (P => R2) is equivalent to (P => (R1 and R2))". To overcome the problem, I have followed closely to Polya's problems solving scheme, which I found really helpful. Overall, I am fairly confident about the course material this week and I hope I will be prepared for the upcoming mid term exam!
Subscribe to:
Posts (Atom)