Omega, Theta, HALT!

I'm going to start this post with the halting problem even though it's the last thing we learnt, since it is by far the hardest thing I've faced this semester. Tracing through the halting problem wasn't too difficult, but figuring out how to reduce a given function to the halting problem is what I found specially challenging.
It took me a couple videos in addition to the lecture to really understand the logic behind the halting problem:
https://www.youtube.com/watch?v=fsE1bFWXlJQ
https://www.youtube.com/watch?v=macM_MtS_w4

Thank God for Numberphile.
Even after the assignment for which we simply duplicated the steps from the course notes to suit our needs, I'm still a bit stuck on how to reduce functions to the halting problem to prove incomputability.

On the other hand, I couldn't be more comfortable with big-oh,omega, and theta. I feel the assignments have been the greatest help in truly grasping concepts by forcing us to work through somewhat challenging problems. Having an assignment due before each major evaluation has greatly contributed to my success on the midterms so far, and hope this is a trend that will continue on to my exam.

Counting steps, and lots of Oh's

This has been by far the most confusing part of the course. Only after a few lectures, tutorials and a couple help center sessions do I finally sort of understand this counting steps thing. I mean it's simple enough with one while loop. But when there's multiple ones within each other, the second loop being dependant on the first loop, things start getting out of control.

 

I don't remember the last time it took me this much time to wrap my brain around something. Maybe when they released tripe chocolate oreos.

From big-Oh we went to big-Omega, which after understanding big-Oh wasn't too hard to grasp. Least steps, Most steps... simple enough. The concepts are pretty simple to understand, it's just the actual counting of the steps in a written algorithm that's a pain to figure out. Hopefully I get better with practice.

Doing big-Oh with polynomials felt a LOT more natural. Hope to see more of these types of questions in the future :

It felt logical and mathematical and less physically straining than counting the steps in an algorithm.

I sure hope we don't have to count steps of an algorithm in our evaluations. Who am i kidding, I'm sure we'll have to count steps of an algorithm in our evaluations.