Week 9!
This weeks lecture is very mathematically orientated as we started looking at proofs of big-Oh using limit techniques. The first half of the lecture focused on proving Big Oh using its pure definition. Using proof structures and techniques we have learnt previously, I found it fairly easy to grasp the idea of a direct big Oh proof because I simply have to follow the quantifiers and pick a c and B that works. The harder part of a direct proof of big Oh comes when we have more complicated polynomials with various degrees. For instance, I found the prove for 7n^6 - 5n^4 + 2n^3 in O(6n^8 - 4n^5 + n^2) quite challenging as we had to deal with a lot of inequalities. Making a wise choice of c in these proofs are also very challenging. I finally understood the logic behind when I look at the actual proof as I saw how professor tries to overestimate the function f(x) and underestimate the function in O. Next, we looked at disproving big Oh by proving a statement's negation. This part was fairly straightforward and I was able to digest the proofs fully.
The second half of the lecture looked at non polynomial proofs, which was when the lecture gets very mathematical. Yet, I found it particularly enjoyable when I saw a relation between the definition of big Oh and the definition of limit when a function tends to infinity as I never noticed such correlation. We looked at the example 2^n in O(n^2) and the proof was completed after applying l'opital's rule and picking n as max (n', B) as both definition can be satisfied. Ultimately, I learnt a lot in this lecture and I enjoyed it very much.
Thursday 6 November 2014
Thursday 30 October 2014
Week 8 Slog
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.
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 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!
Thursday 25 September 2014
Week 3 Slog - Galex Wong
Week 3 SLOG
The third week of CSC165 got very challenging because it required clear concept about logic and mathematical expressions, which are the essential foundations of the course. The lecture this week covered a lot of materials, this included the use of conjunctions. disjunctions, negations. truth tables and finally manipulation laws. Although the lectures in the beginning two weeks introduced and covered some of the first 3 topics, this week's lecture was much more in depth and mathematical. At first, I found it very challenging to quickly adapt to the mathematical statements Prof Zhang presented. For example, if R(x): Car x is red and F(x): Car x is a Ferrari, using R(x) or F(x) is already sufficient to present "Car x is red or a Ferrari. Fortunately, the lecture used a lot of pictures of different cars to present the case and I was able to quickly understand specifically how the predicates worked. After lecturing on about conjunction and disjunction, Prof Zhang told an amusing joke:
"A logician’s wife is having a baby. The doctor immediately hands the newborn to the dad.
His wife asks impatiently: “So, is it a boy or a girl?”
The logician replies: “Yes.” "
The third week of CSC165 got very challenging because it required clear concept about logic and mathematical expressions, which are the essential foundations of the course. The lecture this week covered a lot of materials, this included the use of conjunctions. disjunctions, negations. truth tables and finally manipulation laws. Although the lectures in the beginning two weeks introduced and covered some of the first 3 topics, this week's lecture was much more in depth and mathematical. At first, I found it very challenging to quickly adapt to the mathematical statements Prof Zhang presented. For example, if R(x): Car x is red and F(x): Car x is a Ferrari, using R(x) or F(x) is already sufficient to present "Car x is red or a Ferrari. Fortunately, the lecture used a lot of pictures of different cars to present the case and I was able to quickly understand specifically how the predicates worked. After lecturing on about conjunction and disjunction, Prof Zhang told an amusing joke:
"A logician’s wife is having a baby. The doctor immediately hands the newborn to the dad.
His wife asks impatiently: “So, is it a boy or a girl?”
The logician replies: “Yes.” "
Not only did I enjoyed this part of the class most, I found it really helpful when incorporating humor into the lecture as I was able to quickly understand fully how disjunction works (satisfying either of the conditions will make the statement true).
The next part of the lecture moved to negating predicates and quantifiers. At first, my understanding for negation was not very solid as I still didn't understand why the negation for "for all" is "there exist". Furthermore, I found negating "and" and "or" statements difficult. Yet, by going through the exercises shown on the slides and working with my peers, I was able to overcome my problems by visualizing Venn diagrams.
The final part of the lecture covered truth tables and laws formed through the use of truth tables. While at first I thought Venn diagrams can help us visualize all conditions, Prof Zhang showed the flaw of such technique by displaying how the visualization method fails when the number of predicates increases. Hence, constructing truth tables were necessary for computer scientists. As a student who enjoys mathematics, I find it very enjoyable when professor showed us how we can come up with logical proofs with the assist of truth tables, such as De Morgan's Law. I hope through this lecture I will be able to identify other laws and solve various complex mathematical problems in the future.
Subscribe to:
Posts (Atom)