Week 9

This week we learned about exercises of big-Oh proofs, and  proof of big-Oh using limit techniques.We also had a term test which I felt I did well on because Assignment 2 had really prepared me for the test, as I had to study the material and practice my knowledge for the assignment. For the Big-Oh proof it's mostly about using the definition. So, picking a c large enough, based on the highest-order term's constant factor can sometimes work. Another tip that was given was to plug in   n = 1 in order to potentially get an appropriate c and B. I learned an interesting technique to find c when proving an Upper Bound. You start with the upper bound on the top and try to make it smaller, then you put what you try to prove (the lower bound)  on the bottom and try to make it larger. Then you find a c that connects both bounds. I learned about proof of big-Oh using limit techniques which I found somewhat confusing because of all the steps you have to make and then the fact that you have to connect this information you found to the definition of limits and big-oh. When looking back at the slides, I do see they give a strategic way to try to use limits in the proof; prove the limit ratio equals infinity using some math, then translate the limit into its definition with c and n', then relate this definition to the definition of big-Oh.

Week 8

This week we learned about counting steps, worst-case, and formal big Oh. We learned a formal definition of O(n^2) and we were presented with a useful example of "chicken size" being in O("turkey size") because after a Breakpoint the chicken will always grow and or be smaller than the turkey. I learned that when proving that a function is an element of O(n^2) you use the definition of O(n^2) and pick a c and a B. I find that the definitions we have learned in this course generally are useful in the proofs that relate to what they are defining. There is also a definition for the lower bound of a function where the formal definition switches a part of the upper bound equation by making what was f(n) <= cn^2 switch to f(n) >= cn^2. We learned more about counting steps and analyzing a sorting algorithm. I figured out the difference from last week of wost case scenario and time complexity, which was confusing me before. I also realized in the worse case scenario, where a while loop and iterations over a list are normally involved, that the letters are placed in regards to the size of a list that will be iterated over. I learned that the worst-case scenario with lower bound can be found by multiplying n/3 for each loop it goes through. As in each segment of a while loop it has.

Week 7

This week we learned about proof by cases,Sorting algorithm complexity, and the big-Oh. In proof by cases I learned when there are multiple options to approaching a proof it is helpful to split up the proof and prove the different cases. We looked at sorting algorithms such as merge sort and bubble sort and saw that merge was faster in 'running time'; "the number of steps that are taken by the algorithm" and we actually care about "how the number of steps grows as the size of input grows". We learned that running time is important to computer scientist because they like to be efficient. I learned that the most important term is the highest-order one, constant factors do not matter and that we count how many steps an algorithm takes. We learned about the asymptotic upper-bound notation of O(n) which means the function or equation does not grow faster than whatever is in the brackets of the O. I learned to count the time complexity, you count the number of lines of code that are executed. Although I am confused of where there letters come into the equation or how they got these equations for the running time, in the lecture slides.

Week 6

This week we learned about proofs of non-Boolean functions, proof of something false, and proof of limits. For the proof of non-Boolean, the example of floor x was used because it is a non-Boolean function. I found proofs involving floor x interesting as the definition for floor x could be manipulated in various cleaver ways which would help complete the proof. I learned that to prove something is false the easiest way is the negate the whole claim, then move the negation into the claim segment by segment. Then to prove this negated sentence that was changed. I learned that a big portion of solving proofs was to go through the claim I'm supposed to prove one step at a time.  The proof of limits was familiar to me as I had learned about epsilon and delta proofs in the past. The proof of limits was still a bit tricky but looking at it in terms of distance, the malleability, manipulation and dependency of epsilon, x's, and delta on each other was helpful. Again going through step by step of what I'm supposed to prove in the limit proof is also helpful, so picking a delta that allows the rest of the proof to be true made sense as well as manipulating certain lines and information when needed.

Week 5

This week we learned more about proof structures and using the basic knowledge of the contrapositive, contradiction, existence, and sequence and applying them to a proof.  I found the case of P -> Q to be interesting when applying it to n is odd -> n^2 is odd. I see the usefulness of applying the contrapositive of n^2 is not odd -> n is not odd for more general cases when the reverse of the directions is the easiest way to approach a proof. I also learned that contradictions were useful in approaching a proof when something seems obvious and so to assume the negation of the antecedent and see whether that is true or false. For existential  I learned that you have to find one example where the claim is true. Sequences confused me, at first the example proofs of sequences, the  symbols, and steps you had to take in the proof overwhelmed me but then I later looked at the slides and approached the example proof step by step and in great detail and it became clearer. I see that there are multiple approaches and techniques already established for proofs so you do not have to approach a proof completely from scratch. I also can see that proofs require a lot of trial and error. The week before we did A1 which I found was helpful in preparing for the test as it gave me practice questions and let me review the material so that I understood the course content more clearly when coming to the term test.

week 4

This week we learned about bi-implication, transivity, mixed quantifiers, and a bit about proofs. I found that bi-implication better helped me understand the use of the laws  (especially de-morgans ...) and efficient methods to re-organize the mathematical symbols and/or statements.  I found the tutorial this week really helpful and made me engage in the material which also helped with my understanding of the laws and how they were used. I found transivity interesting because it was like a chain that could be shortened easily. The picture with the 3 circles inside one another also helped with showing me in transivity, what element belongs to what. I learned that proofs involve a very logical way of thinking and it can be helpful to start a proof backwards. I also learned that there will be several structures to writing proofs. 

week 1 and 2

The first week of class started with an introduction, breaking down the name of the course; mathematical expressions and reasoning. An important component to this would be the mathematical expressions which can be communicated in several ways, using words and numbers, words and letters representing symbols and a pure symbolic representation of a problem. It was also mentioned that communication in general, such as, working in a team, analyzing problems, expressing problems, understanding problems etc. would be important in general and we would look at precise ways to communicate such as with proofs and in the computer. To add to communication, there was talk of precision; how you can either be precise or ambiguous when communicating. I found it interesting that you can be extremely precise by limiting the field that the information is relevant to, for example, math has specific terminology. I also learned that computers need extreme precision whereas humans can lean more towards the ambiguous side when communicating.  In the second week we learned more about quantifiers. I found it interesting with how specific you could be with simple words such as, "all", "every", "some", "there is" and that sentences and statements could be indicated as different by having a quantifier in it and could be either true or false. I didn't think of language as being this specific. I found the Venn diagrams helpful to visualize except I kept having issues with placing the x and o in the correct spot at first, when I went to tutorial and we went over the first exercise, I got a better grasp for how the circle and x was placed.