Week 11

• This weeks post is going to be sort of short considering there was no class on Monday. So it may not be the longest one. So we have started doing algorithms and computability. This is really confusing to me really. I don't really understand how this has to do with like proofs a stuff yet but we'll see. I got into class and saw the halting problems being explained and I was like, "WHHAAAAAATTT!!". It's got its moments of clarity but I just don't get the premise of it.

• So we looked at the collatz code and Danny said that for years mathematicians had been stumped over how to show the code halts for every natural number n. He said they had been able to check that the code halts on very n to a particular point but cannot know yet if it halts for every input. Then we talked about computability and what we can call a finite set. First the set has to be 1 to 1, which means for every x value there should exist one y value. And the set has to onto which means each x must have at least one y value.

 

• Lastly, Assignment 3 is out and I'm getting on my grind for that. I'm pretty screwed for this one I think. but "Fingers Crossed".

Week 10

• So we are almost done with this half. And the plot thickens. So we have started going deeper into Big-Oh and Big- Omega. I learned that when dealing with Big-Oh you under-estimate the second function and overestimate the first function to try and find a relationship. That process will also help you find your c . We are meant to consider a c large enough to make the second function an upper bound for Big-oh, and then for Big-Omega we are meant to consider a c small enough to make the second function a lower bound. All pretty basic stuff I guess. My TA did a good job of explaining this topic I think, it was very well taught. Here's an Example of a question I solved

• I guess the trick is to first understand the graph and decide if its true or false. That's the hardest part for me. First I have to imagine the graph in my head and then decide if its true or false. then I always think about what exactly to write in the comments sometimes. I hope I get the basics soon enough though. No class next Monday so party weekend guys. 

Week 9

• This week we focused mainly on proving Big-Oh and Big-Omega bounds of polynomials. I have personally been working through a lot of proof statements these past few days, I see that we should use the definition when proving big-oh/big-omega statements in other words, relate your given expression to that of the Big-Oh or Big-Omega definitions.. Also, the constant c can be adjusted to meet our purposes. Also we learned to use limits in check if some functions are larger or smaller when the constants don’t affect .That is, divide one function by the other. If the graph 'approaches infinity', is a good indication that one function is growing extremely faster than the other. This is what the "breakpoint" B is used for. Usually, we pick the point B, and it narrows our proof down into worrying only about the part of the function the expression is completely true for.
• Although some proofs involving proving that functions are in  Big-Oh are challenging, they are nonetheless more simple than proofs showing that a function does not belong to the Big-Oh of another function. Because then we have to negate the definition of Big-Oh then find a counter-example "n" that breaks the expressions.
• we used L'Hopital's rule to show that the limit of 2^n/n^2 is infinity, which is of course greater than c. However, I was still a bit unclear about whether the function on the top is the bigger one or the function on the bottom is the bigger one? I like the Limits introduction Nonetheless, I think a little bit of calculus in the course would do some good. 
• Test Two this week. Probably didn't do too well, the practice questions made me underestimate the range of questions that they could give us causing me to just study simple proofs. Anyways I'm hoping I can make up for it in the Final Exam. "Fingers Crossed"  

Week 8

• We took a look into Big Oh this week. We identified the expression of Big Oh as finding a constant c, past a breakpoint B, where the graph of f(n) (can be any expression) is always less than c ( a constant) multiplied by g(n) ( can be any expression). Here is an example of a big Oh proof stated below:

Let c = ....... and B = ............

Then c ∈ R⁺and B ∈ N.

Assume n ∈ N. # in order to introduce ∀

       Assume n ≥ B'. # antecedent; B is an arbitrary natural number

            .

            .

            .

Then ∀ n ∈ N, n ≥ B ⇒ g(n) ≤ cf(n) # introduce ∀ and ⇒

Then ∃ c ∈ R⁺, ∃ B ∈ N, ∀ n ∈ N, n ≥ B ⇒ f(n) ≤ cg(n) # introduce ∃ for b and c

 

• Understanding the proof structure and the definition of Big-O is based on understanding the graph . Proving it requires more practice because it all depends on which statements we get. For instance, Big-O can be done with two functions and polynomials. The proof structures are similar. But to enhance our proof, it's crucial that we begin with scratch work before going on to write the proof.
  

  
•  Also we learnt about analysing algorithms, looking at worst and best case scenarios. Merge sort was in O(nlogn) where bubble sort was in O(n^2) . Looking forward to some more algorithms. Anyways test 2 is next week and I am not too sure about it but we'll see.

Week 7

1. So we took a look into sorting algorithms and  run-time complexity. Bubble sort and Merge sort . Then we checked how quickly the two sorts run. And whether the ran linearly or quadractically. We learned that linear is faster then quadratic. Also run time means how many steps are taken rather them how many seconds it takes to run.

1. First we count the number of steps without constant factors. only the highest-order term matters . We then learned about algorithm analysis and asymptotic notation. We were introduced to this concept with an example of bubble sorting and merge sorting. We checked which of the two aforementioned methods of sorting was the most effective by analyzing their respective algorithms .Algorithms are important because they determine the running time of a function .  We also learned about how we do not really care about the number of steps withing an algorithm, but about how the number of steps increases as the size of the input increases
2. Then we started talking about Big Oh .We start off by picking a positive real number, c, and a natural number, b, that will work. Then we assume that n is a generic natural number in order to introduce ∀. We assume the antecedent, n ≥ B. We saw the definition of big Oh.                  
   
   So basically we must pick a c past the breakpoint B such that f(n) was less than or equal a constant times g(n) or n-squared.

  



Week 6

1. No class on Monday WOOT!! WOOT!!. Thanksgiving baby. With the potatoes and the turkeys and the stuffing and the rasmfrasm. So we learned more about proofs this week using floors and absolute values in proofs. Also we saw functions that didn't returned Boolean and non-Boolean functions. when using floors we must first understand the definition of floors.
   
2. Y is an integer. And Y is less than or equal to X. So basically Y becomes the immediate less than integer , I guess. Why is this so, I don't know why yet but that is what we have learnt so far. This is all so new to me. Sometimes I feel like when we do some of the proofs in class we break a lot of mathematical laws. But we also don't kind of. Alright so how do we use the floors in proofs? "Hoew waz ze exem Maximillian",
3. The 1st term test is done with, so that's good, I didn't see the practice test until 30 minutes before the test so that's bad. I don't think I did very well in general a lot of rushing and attempting to erase what I did and starting over. I almost didn't do a whole question i think.

I learned that when you are doing proofs try and manipulate expressions closer to the form of the definitions of expressions. e.g. floor so





                  Assume ....# definition of floor and antecedent of question given

                      Assume .......# Generics

                          Then .............# Try and relate expression in relation to the definition of floor

                           .                    # e.g.  For all x in R ,[x] > x+ 1, this is false so disprove. Find a  

                           .                               Contradiction like [2.5] , according to the definition of floor its 2

                           .                                etc.

                           Then .........# conclude derived conclusion

                       Conclude ............# restate the previously assumed expressions

                  Conclude ..............................

Just a simple example of a proof involving floors and how one might deal with them.



Week 5

1. Week was tough. Test 1 and assignment 1 are over and its time to start studying all over again . "Got to love UofT". Test 1 was good and fair but I was not to prepared for it considering I didn't do all too well on it but finger crossed for test two.
2. I've been working on some of the proof structures and especially the commenting on each step is bugging me out. In class we did the question on There are 5 boxes in which there are in total 51 balls. Prove that there is a box with at least 11 balls in it. I understood the premise of the question. We used negation to prove it. we assumed that there was not a a box with at least 11 and tried to prove for ten. But if every box had at most ten Then the 5  boxes would have at most 51  being a contradiction.
3. Proof example:   from handout
   

   
4. Whenever we make an assumption we indent the next line, and once we have proven our conclusion, we can unindent and start restating the initial assumptions . Also we make comments next to most lines to explain our thought process and how it relates to the net sentence. For example, real numbers are closed under addition, subtraction, and multiplication and natural numbers are closed under addition and multiplication. Cool ain't it.
5. Anyways there's a new test and assignment coming up so we'll see how that goes. Hope fully i understand how the next topics come.