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.