In these two weeks, my professor taught us more concepts related to proofs and even the concept of Big-Oh. Firstly, he showed us how to make sure that a claim is true or false before proving so. He also introduced us to some rules of inferences and how they work, some of which we had already covered in detail. These inferences are:
1. Conjunction elimination, where A Ù B, conclude A or B separately
2. Existential instantiation, where $keX, P(k), pick an element with this property, and let k'eX, P(k')
3. Disjunction elimination, where A Ú B, ØA can conclude B
4. Implication elimination, where A Þ B, A can conclude B and ØB can conclude ØA
5. Universal elimination, where "xeX, P(x), aeX can conclude P(a)
6. Implication introduction, where A Þ B
7. Universal introduction, where "aeD, P(a)
8. Existential introduction, where $xeX, P(x)
9. Conjunction introduction, where A Ù B (if you know A and B)
10. Disjunction introduction, where A Ú B (if you know A)
Furthermore, my professor also mentioned something about sorting algorithms and speed. If I remember correctly, he mentioned that the speed does not depend on the input and hardware the algorithm is running on. He also conducted a "penny piles" activity last Friday, where we were given a situation in which a number of pennies are in either of two drawers. We had to sort them in even numbers according to which drawer they were in. This activity seemed complicated at first, but I slowly came to understand it and had fun doing it, even though I couldn't get the final answer.
Some more concepts that my professor covered in lecture was the running speed of algorithms, and that they could be measured by counting how many steps it takes to reach the output. So basically:
1. Conjunction elimination, where A Ù B, conclude A or B separately
2. Existential instantiation, where $keX, P(k), pick an element with this property, and let k'eX, P(k')
3. Disjunction elimination, where A Ú B, ØA can conclude B
4. Implication elimination, where A Þ B, A can conclude B and ØB can conclude ØA
5. Universal elimination, where "xeX, P(x), aeX can conclude P(a)
6. Implication introduction, where A Þ B
7. Universal introduction, where "aeD, P(a)
8. Existential introduction, where $xeX, P(x)
9. Conjunction introduction, where A Ù B (if you know A and B)
10. Disjunction introduction, where A Ú B (if you know A)
Furthermore, my professor also mentioned something about sorting algorithms and speed. If I remember correctly, he mentioned that the speed does not depend on the input and hardware the algorithm is running on. He also conducted a "penny piles" activity last Friday, where we were given a situation in which a number of pennies are in either of two drawers. We had to sort them in even numbers according to which drawer they were in. This activity seemed complicated at first, but I slowly came to understand it and had fun doing it, even though I couldn't get the final answer.
Some more concepts that my professor covered in lecture was the running speed of algorithms, and that they could be measured by counting how many steps it takes to reach the output. So basically:
length of algorithms = no. of steps
My professor also showed us how to establish formulas for the number of steps taken to complete a function based on an input. The class also learnt that there are two worst cases: the upper bound and the lower bound. The upper bound means that the program will take no more than a certain number of steps to complete the program. The lower bound means that the program's worst case contains at least a certain number of steps. Upper bound is denoted by: WP e O(U), and lower bound is denoted by: WP e Ω(L). O is for oh, and Ω is for omega, U is for upper bound, and L is for lower bound. Additionally, we learnt the concept of bounding a sort so that WP e O(n to the power of 2) is proven, for example.
As mentioned before, we also learnt the concept of Big Oh of n to the power of 2. This function means that all quadratic functions are roughly the same speed and that the natural numbers are the input and non-negative real numbers are the output. Lastly, we were shown how to prove WP e O(n to the power of 2) and WP e Ω(n to the power of 2).
Overall, the concepts for the first week were relatively easy for me to understand, but the second week's concepts were substantially more challenging. I understood part of it, but if I were given another problem related to it, I would most likely not be able to solve it or write a proof for it. I know that it takes time to understand and absorb the concept of Big Oh, so this is why I am reading over my lecture notes to understand it better. Additionally, if I were to be given an expression and asked to prove it, I would have some difficulty doing so. This proves that I need to work on application of my learnt concepts. By far, this course has continued to be challenging and I know that one can't succeed without practice and hard work. To overcome this difficulty, I aim to continue to read my lecture notes over and over again, do certain lecture problems without looking, and seek help if in doubt.
No comments:
Post a Comment