Friday, November 14, 2014

Weeks 9 and 10 - Almost there!

After continuously working with Big-Oh statements about polynomials, its gotten pretty easy to prove them. That was up until logarithmic functions (rather than exponential) were introduced; when we had to prove things like 2n O(n2). In order to prove these statements, the use of limits and L' Hopital's Rule was need. I'd heard of this rule a number of times in calculus before, and luckily we re-learned it again in my MAT135 that same day. Basically it uses derivatives to help evaluate limits of indetermined forms such as 0/0 or ∞/∞. It is fairly simple. 
Moving back to the proof, if the limit evaluates to infinity, then we could easily prove the statement with the help of these tools. 

By now, having the definition of Big-O carved in my knowledge, the definition of big-Omega came more easily. The only difference was the inequality at the end changing direction. This all came as pretty straightforward until Friday's lecture rolled around, where Prof Heap had lost me on a much earlier stage than I'd hoped. This brief fall break and working on assignment 3 will hopefully aid in making it more comprehensible.

Tuesday, November 11, 2014

Week 7 and 8

These two weeks were focused on learning everything properly that were required to do the second assignment and test. The concept of disproving was stressed somewhat and was fairly simple to grasp. We went over the structure of proofs in more details (all the inferences) and then moved on to sorting strategies.  Another interesting exercise was given to once again help us practice understanding the problem, devising a plan, and carrying it out. This pennies problem required us to think of a sequence that would produce two piles of pennies using one of two ways {L,R}. The obvious first move was splitting the 64 into two piles of 32 so {L,L} {L,R} would work.

Next we were introduced to the Big Oh, and that's that part in this course where I'd never seen or heard of this, making me uncomfortable. After Google doing what it does best - save lives -  I was okay. When Prof Heap started talking about linear search, the worst case, its upper and lower bound, I wasn't following him entirely and am still a little unclear about it. Either way, doing some examples of these proofs with quadratic functions made life much more sensible. It wasn't until after when these sorting methods were introduced in my introduction to programming class that I finally fully understood what alien doings were going on.

Meanwhile, assignment 2 was driving me crazy. I had a couple of more assignments and tests due that same week making it such a perfect time to catch a cold! On top of that, I was struggling to sneak in a few hours of sleep here and there, desperately waiting for the week to end. Good news was that assignment helped me prepare for the test so too much time and effort wasn't consumed studying for it.