Run-time analysis, Assignment 3

Although the third assignment's deadline was generously extended, my group-partners and myself went through a number of issues trying to solve the problems.  Among the most difficult questions, in my opinion, was question 5, which asked to prove or disprove that for all functions f and g that take in natural numbers and return real ones, f is in Big-Oh of g, or f is in Big-Theta of g.  Intuition led us to disprove the statement, thus we went ahead and approached the negation of the statement to become:

"There exist functions f and g such that f is not in Big-Oh of g, and  f is not in Big-Theta of g."  Of course aside from everything else, coming up with individual equations which exactly satisfy the statement was a challenging step.  That is, the two functions f and g should grow in such a way that none of them bounds the other.

Our first approach was to construct sine and cosine functions in such a manner that they "oscillate" without ever bounding one another permanently.  Of course, the graph below shows that the idea was plausible however the actual implementation got so tricky with issues ranging from managing the Pi to manipulating variable n properly, that we decided to search for other ways.  

The solution, as it turns out, was not too complex: find two functions which grow in the form of the following, with f shown in blue and g shown in green.

(Courtesy of Google)

Taking two piece-wise functions as f and g, then proving the negation of the original statement was what we resorted to.  Two cases were taken to examine the effect of having odd or even natural numbers used in the process of disproving of Big-Oh and Big-Theta.

Problem-solving session: Polya's Method

This week, I have started revisiting past tutorial questions as a preparation for the final exam coming up in less than a month.  I noticed that I have had a few issues with problem-solving in the past, especially with problems that were introduced in the tutorial problem sets.  As a result, I was reminded of Polya's problem solving approach which aims to break down a problem into distinct steps as to facilitate the process of finding a solution.

I have chosen to use the principles suggested by Polya to solve the following tutorial problem which I initially found challenging.

Understand the problem

 The problem above seems to be about a special relationship between a set of integers: for all integers x and y, should x be less than or equal to y, then there must exist some integer z which is both greater than or equal to x, and less than or equal to y.

In other words, the integer z falls exactly between the integers x and y if the antecedent is valid.  The following number-line is a representation to facilitate the visualization of the problem. 

Let's say that our x in this case is 1, and y is 7, then according to the above statement, z can be any of the integers between and including 1 and 7.  Of course, this is just an example as the above should work for all x and y.

Devise a plan

The consequent of the statement gives us a clear hint.  Although z is in between the two integers x and y, it can also be one of the two integers.  That is to say, z can be x or y, or something in between.  What if we choose z to be equal to x?  x that is less than y would remain less than y, and at the same time x will be less than or equal z (in fact, x would equal z), and hence by transitive nature of the greater-than-or-equal sign, x ≤ z ≤ y.

Carry out plan

At this stage, I intend to directly prove the above claim using the plan devised earlier.

Assume x ∈ Z    # x is a generic integer

    Assume y ∈ Z  # y is a generic integer

         Assume x ≤ y   # assumed antecedent

                 Let z = x , then z ∈ Z  # x is an integer, then so is z

                 then z  ≤  y     # since x ≤  y

                 then x ≤  z  ≤  y     # transitive nature of  the ≤ sign

        Then x ≤ y ⇒ ∃x∈ Z, x ≤ z ≤ y   # assumed antecedent, got consequent

    Then ∀y ∈ Z,  x ≤ y ⇒ ∃x∈ Z, x ≤ z ≤ y

Then ∀x ∈ Z, ∀y ∈ Z,  x ≤ y ⇒ ∃x∈ Z, x ≤ z ≤ y

        

Look back

Direct proof the above statement worked without issues!  It is quite simple to see the connections once the Polya's principles are followed, mathematical rules are investigated thoroughly and different modes of the problem are investigated.  For example, had I not made the visual representation, I quite possibly would not have been able to properly visualize the problem.  This is related to another discipline I immensely enjoy which is cognitive science; the brain needs different cues to encode a problem and providing the visual aid along with perhaps auditory explanation of the problem can drastically facilitate the process.

I must admit that it takes me considerably longer to arrive at a solution when I do not separate my work into segments as Polya suggested.  This means that organization is the key to a successful problem-solving strategy

Proving old claims

After reading a post I had made at the beginning of the term, I noticed that I had made a promise to prove or disprove an every-day claim using mathematical logic learnt during all these weeks in this course.

The claim I have chosen to prove is "Someone who doesn't eat meat can survive."

Let's say...

• H(x): the set of all Humans.
• M(x): the set of Meat-eaters.
• V(x): the set of Survivors.

Claim:   x  H, ¬ M(x) ∧ V(x)

Let x = Jinny                    # Jinny is my friend who is a vegan
   Then x  H                   # She's also human
        Then ¬ M(x)            # She doesn't eat meat
        But len(x) this year > len(x) last year  # She is taller now
        Then x grows          # There must be something else that gives her protein  
        Then x finds another food source  # She doesn't starve!
        Then x eats
        Then x breathes  # She can't move mouth muscles to chew without respiration; Oxygen in! 
        Then x has energy  # From the law stating that Respiration = Energy + CO2 + H20
        Then x can move    # Einstein's Law of Conservation of  Energy; it has to go somewhere!
        Then x can run away from danger  # Energy well-used, Jinny
        Then x can survive                         # Gloria Gaynor
        Then V(x)        
        Then ¬ M(x) ∧ V(x)           
Then  x  H, ¬ M(x) ∧ V(x)   # And, proven! You can indeed survive if you don't eat meat.



* As a side-note, I really enjoyed reading the post "Week 10 (Problem Solving)" by http://bgancsc165.blogspot.ca/ who eloquently explains how to prove that 5n^4 - 3n^2 + 1 is in
O(6n^5 - 4n^2 + 2n ). This was a tutorial question that I personally did not know how to solve until I read the post.  Highly recommended!

Secret relationships? L'Hopital's Rule and Big-Oh

It was refreshing to see something familiar during this week's lecture: L'Hospital Rule.  As fascinated as I am with calculus, seeing L'Hopital's Rule used with Big-Oh didn't quite make sense at all... How are they even related?

Suppose there are two functions f and g.  If the ratio f(n) / g(n) approaches infinitely, then the function f(n) grows faster than g(n).  The following graph is a good representation:

But how is this related to Big-Oh, or limits for that matter?

Proving Big-Oh can prove (no pun intended) to be tricky at times and therefore an alternative method is required.

Proving that the ratio mentioned previously approaches infinity means that that f is in Big-Oh of g, as function f grows faster than g!

There is a secret connection between the definition of Big-Oh and that of limits; relating the two definitions in terms of symbols can prove a Big-Oh statements.

This is where L'Hopital's rule comes into play.  Finding the limit of the ratio as it approaches infinity may be more easily done by taking the limit of ration of derivatives of the functions.

There are no restrictions to the number of times you can take the derivatives to reach the result that truly approaches infinity.

A Big Family: Big-Oh, Big-Omega, Big-Theta

I was surprised during our lecture this week because of how much I enjoyed analyzing different run-times.  I have had a very brief introduction to related ideas in a previous course however I never cared much for the densely-theoretical approach emphasized by the concept.  Run-time analysis, now I understand, requires a meticulous, calculative nature which [now] makes analyzing different algorithms an enjoyable, deeply stimulating experience.

In short, time-complexity analysis is the abstract, mathematical approach of determining the running-time of an algorithm as its input size changes. There a number of categories that algorithms can fall under, depending on their aforementioned running times: Big-Oh, Big-Omega, Big-theta [among others not covered in this course].  

Each of the latter has certain properties showing us to the growth rate of an algorithm.

1. Big-Oh.  Example: f ϵ O(g).  This, "function f is in Big-Oh of g," means that function f grows no faster than function g.  In other words, g is upper-binding
2. Big-Omega.  Example: f ϵ Ω (g).  This, "function f is in Big-Omega of g," means that function f grows no slower than function g.  In other words, f is lower-biding.
3. Big-Theta.  Example: f ϵ Θ (g).  This, "function f is in Big-theta of g," means that function f grows as fast as function g.

This is definitely fascinating as not only an estimate is devised of the efficiency of a program, different programs can be compared and contrasted to find the one with most optimum performance.  Computer science fascinates me!

Limits [to my patience]

This past week I've had real trouble with this course. Last lecture, we went more in-depth with proofs, and I won't lie, it is getting quite complicated.  Just when I felt confident about my 'proving' abilities, we were introduced to every CSC165 student's worst nightmare: proofs about limits.  

Up until yesterday, I was at loss.  Why is everything in Greek alphabets?  How does that compare to previously learnt material regarding calculus limits?  These and more questions overwhelmed my consciousness.
I finally gathered up the courage to go to the Help Centre yesterday.  I am definitely glad I did because assignment 2 has just been posted and most of the problems involve the concept.

For a problem of the sort,





I found that it is easiest to try and plot a graph.

(Courtesy of Professor Zhang)

Among the hardest things I found with limits is devising a plan to find the most appropriate δ that goes in terms of ε.  In other words, the goal is to have every possible δ ≤ ε.  As with everything else in this course, once the concept is clear, the actual proof becomes a little easier to fill out.

Achievement Unlocked: Test Results

I just got back my test results! I'm so proud: I did much better than expected.  I decided to document this since I am in such a great mood at the moment and it might help me in the future once things start to get discouraging.

The questions on the test were very similar to the ones that were covered in class and past tests.  At one point during my preparations, I almost completely ignored a note the professor had mentioned that I had documented in my notes because I found it too difficult to grasp.  I now appreciate my intuition for resolving the fear of failure and trying to understand the concept: that same concept, involving the use of functions in the form of any and all along with their negations in Python code, encompassed more than 60% of the test!

After resolving my issues with this concept I can in all honesty say that I found the tutorial questions much more challenging than those on the test.  I suppose hard work really does pay off!