The Unsolvable Problem

Note: This post covers Week 12 (There was no class during Week 11),

Since the most difficult concept always gets introduced in the last class before the exam, this week we explored the Halting problem. Essentially, we were asked to create a function halt that predicts whether or not a function would halt, or stop (a task we soon proved was impossible). I generally wouldn't complain that we had proved a problem impossible, intuitively that would mean that we wouldn't have to try to solve it. Unfortunately, for halting problems, we have to prove whether a function is computable or not by attempting to reduce it to a halt function (since halt is not computable, if a halt function can be written using a function f, that function is not computable).

Generalizing Big-Oh Proofs

Note: This post covers Week 10.

This was probably the most hefty lecture of the semester. We took big-Oh proofs, which tend to be somewhat to moderately difficult themselves, and learned how to prove general properties (ie: if f is in big-Oh of g, then g is in big-Omega of f). Basically we were given a statement (ie: f is in O(g)) which provided us with a constant and breaking point, and we had to figure out how to mould those variables to prove the consequent (ie: g is then in Ω(f)).

An interesting example (which was asked on A3) was to prove that for any two functions f and g, f is in O(g) or Ω(g). I originally tried to prove this but then realized that cyclic functions or a simplified Dirichlet function would prove this statement false. Hopefully with a bit more practice these proofs will come easier to me!

Big-Oh

Note: This post covers both Weeks 8 and 9.

Prof. Zhang introduced the formal definitions of big-Oh and big-Omega in Week 8. We learned how to do some simple proofs involving them which were daunting at first but exposed to be quite easy by overestimating (for big-Oh proofs) or underestimating (for big-Omega proofs) the function. I’m glad we’ve had so much practice with proofs, because these were fairly easy to do. The most important part for me was understanding the intuition behind the proofs, which was covered very well in lecture.

We started off week 9 with both a midterm and the A2 due date They were both probably the most challenging pieces of coursework that we’ve done so far. We had quite a few hints in the previous lecture though so they were both fair.

This week we went much more in depth into big-Oh proofs, going over examples of negation and limit-based proofs. We started with a regular proof, but discovered that we could not only overestimate the function, but also underestimate the bound which makes dealing with more complex proofs a bit simpler (but lets the profs ask us to do more complex proofs on tests…). We also learned negations (which were fairly intuitive) and yet again, a proof involving limits. If the ratio of the bound divided by the function approaches infinity as n approaches infinity, we can determine that the bound grows more rapidly than the function and therefore the function is in big-Oh of the bound. We used l’Hopitals rule to simplify the limits and then followed with a regular big-Oh proof. This was a fairly complex proof so much like my classmate Aqib writes here, I had to attend office hours to fully understand how to do it. I like these proofs now though because you don’t have to find appropriate constants or breakpoints, the fact that the variables exist to prove big-Oh are given by the limit.