Week 12 - Halting Problems and Computability

This is hands down the most challenging concept of the course. The level of abstraction in this topic is way beyond anything else we have encountered so far. I have posted A LOT of questions on the forum about the halting function and reduction. (Side note: They should really consider substituting some of the marks for the slog entries with participation on the forum. I think I have posted enough content on Piazza to fill over 10 slogs!  Something to think about.)

I feel like we covered this topic too quickly, and moreover we jumped into overly complex examples of halt without first understanding the simpler ones. The examples in the course notes show functions with 1 or more parameters when we really should have started with functions that don't take any inputs at all.  Here is a snippet of code I posted on Piazza that I believe should have been the original proof for the non-existence of halt.

def halt(func):
    """Return True iff func() eventually halts. 

    Assume this exists.
    """


def unhaltable():
    """Loop infinitely if calling halt(unhaltable) returns True, i.e.
    unhaltable() halts. Return False otherwise."""

    if halt(unhaltable):
        while True:
            pass
    else:
        return False 

The above code provides a much simpler proof than the confused( ) function proof from the course notes. There are no extraneous parameters that complicate our understanding of the underlying concept. With this proof in hand we can then branch out to other functions that actually do take in arguments and then gradually develop more complex proofs from there. 

These extra parameters and functions that take in two functions as arguments caused me to focus too much on the python syntax side of things rather than the concept of halting. I spent several days deciphering the code and trying to program functions that take in two functions as inputs,  as well as seeing what happens when a function calls itself but with another function as its own input argument. I wanted to know whether the function passed in as an argument is ever reached or whether we just create a never ending recursive function. I even used a python visualizer to try and see what was going on.

Another area of confusion is that the conceptual halt function doesn't necessarily have to run the code of the function it receives.  It could instead just scan the code and analyze it to see if it halts.  Passing in a function along with another object input distorted this concept because I kept thinking that the function was just going to recurse forever. The challenges noted above are what prompted me to rewrite the confused() function from the course notes into something simpler like what is shown above.

 To sum up the semester I'm going to include a link to this student's Week 12 slog post. Truth be told, that comic he posted is probably what half the students in all of comp. sci. are thinking when they go through this course. I was sure to let him know in the comments section.
http://andrewgoupilcsc165.blogspot.ca/ 

Week 11 - Big-Theta and General Properties of Asymptotic Notation

So I heard from my CSC148 course that when computer scientists say a program runs in big-O of some function of n they generally mean that it is also in big- Θ of that function. My question is once we realize a program runs in say O(n²), do we even bother trying to show that it is also bounded above by n³ or bounded below by n when we can make that assessment by inspection? In other words, in practice do we typically worry about the other functions not in the same class or do we just prove that it is in big-O of something and leave it at that, until we can improve upon it.

I assume this is where the general properties for asymptotic notation come into play. Such as adding, and squaring a given function etc. and how they affect its relationship to its other bounds.  Thus we can very quickly say based on these properties that it performs better or worse than some other class of function without having to delve to much into the gritty details.

We had a similar question on Assignment 3 that resembles the concept of big-Θ. It asked us to show that there exists functions that do not bound each other above or below. And some people were suggesting that trigonometric functions such as sin(n) and cos(n) might work.  After thinking about that I came up with two flaws with using these functions.  Both sin(n) and cos(n) are functions that have a range in both the positive and negative reals. Thus these two functions violate the requirement that f(n) must only map onto 0 or the positive reals.  To prevent this, we could add a constant to raise the entire function above the x-axis but then why not just use a horizontal line?  Moreover, once you raise one trigonometric function entirely above the x-axis it then does behave like a horizontal line in that you can multiply it by some constant to bound the other trigonometric function above and below.  I went with a piecewise function, but even then the proof had many cases to show. Hopefully I caught them all.

 On a side note I was roaming around on some of the other slogs and stumbled upon this cool python implementation for the folding paper problem. This student also implemented something in graphical form which I thought was nice.
http://courseblog165.blogspot.ca/

Oh by they way, you can also run the code for my penny piles problem in the interpreter. Its kind of fun to find combinations of inputs that have really long sequences. Its been a while but I think (8, 99) and (16, 99) produce some neat outputs.  If you are really brave you can try (32, 9999)!

Week 10 - Limits and Non-Polynomial Functions

I get the feeling that logical notation has a hidden contempt for calculus and limits.  Prof. Heap is always saying that limits don't quite express the true nature of a function as some variable approaches infinity. He's of the opinion that numbers can never really approach infinity but instead they just get "very large" or "move farther way" from some value such as the origin. We also have our own expressions for limits that are always 3 or 4 times as long as the calculus version and I find that it adds an unnecessary complexity to a proof.

Take for example the limit as n approaches infinity for  2ⁿ / n².  By calculus we can easily show that this approaches infinity.  Then by inspection we can quickly say that a function of 2ⁿ is guaranteed to surpass n² as n gets large thus n² is in O(2ⁿ) and 2ⁿ is in Ω(n²).  The proof using calculus, would probably be about 2 lines.  But the proof using logical notation and the structures of this course is approximately 5 to 6 times as long which really impedes our understanding of the underlying concept of the relationship between two functions. The meaning of big-O and big-Ω are hidden behind this excessive notation.

I know limits themselves have a similar precise definition, but they also have a higher level notation that quickly expresses the long term behavior of a function. Personally, I've had difficulty with limit proofs since the beginning of the course. To help I've reviewed several of the limit chapters from my old calculus text book and I've also tried drawing diagrams showing the delta and epsilon boundaries.  But when the function changes it can easily throw you off and put you right back at square one where you need to reinterpret the strict definition of the limit. I plan on spending a greater portion of time with limits of various types such as ones that approach infinity, zero and some other value and for various functions as well.  Hopefully there are some good examples in the course notes that I can practice on.

Here is someone who shares the same confusion with limit proofs.
http://slogcsc165.blogspot.ca/2014/11/week-11-recap-from-previous-weeks.html?showComment=1417548152625#c1153904731624398479

Week 9 Big-O and Big-Omega of Polynomials and Other Functions

Following up from my last post, I'm finally coming around to the idea that extraneous terms and constants that are not of the highest power in a polynomial are irrelevant.  In the long run, the highest power always wins and thus we need not worry about a slightly higher breakpoint.
With so many different types of classifications it definitely makes sense to use this simplified notation.

One thing I still don't quite see the use for is the lower bound big-Ω.  I understand that we are trying to establish the lower bound for the worst case, but if we extend this to the expected runtime for a random set of inputs, shouldn't we also include the input cases where the runtime is better than the worst case?  Thus rendering Big-Theta somewhat meaningless. Or is this another instance where we sweep things under the rug because they don't amount to anything significant, much like the coefficients, constants, and lower powered terms I mentioned earlier.

Its also interesting to see that the same function can be used to bound above and below. I guess this is another result have having the broad definition for big-O and big-Ω.

We covered similar topics in CSC148 where we very broadly classified various functions using the following asymptotic notations.  I have ordered them approximately from smallest to largest:
O(1) = constant time does not depend on the size of an input
O(k) = linear time based on some input value k
O(h) = linear time with the size or height of an internal data structure
O(logn) = logarithmic runtime typically encountered when traversing heaps
O(n) = linear runtime proportional to size n
O(nd) = runtime that is proportional to both the size of an input and the number of digits of the items of an input (radix sort)
O(nlogn) = runtime of mergesort typically
O(mn) = runtime is proportional to the size of two different inputs
O(n²) = quadratic runtime such as with insertion sort or selection sort
O(2ⁿ) = the worst of all the ones we've touched on

Overall, I am feeling good about working with asymptotic notation.  The concept seems intuitive at least for polynomial functions. Generally, it helps to have a graphing calculator handy so you can see the odd behavior for each function near the origin and for when n gets really large. I find that graphing the functions lets you develop that sixth sense for breakpoints and coefficients.  So far the trickiest part is making sure you choose the right coefficient c, and that you keep track of the minimum value for the breakpoint B. If there are constants involved for big-O then usually B is some value >= 1.  Also, c is usually >= 1 for big-O and < 1 for big-Ω.

Looking at some of the other slogs here is one that adds a nice touch using some of the lecture slides. I think this student also agrees that picking the right B and the right c for a proof is important. I let them know in the comments section of their blog.
http://ace165.blogspot.ca/2014/11/week-10-big-proof.html