Epsilon: The Magic Maker?

This week in lecture we explored regular expressions more closely. We are now constructing entire languages through building simple patterns and logic!

But one thing that caught my eye was that measly epsilon symbol that seems to break all the rules! I guess because we are now also studying NFSAs and not DFSAs that there are major differences between them that I will have to get used to, but epsilon still seems to just confuse things. Like, what tells the machine to take the epsilon transition? It seems like more of a probability class now that way prof Heap showed it to us! Haha. But really, I guess the correct way to look at these epsilon transitions is that we must examine all possibilities and paths given that these transitions may or may not occur, and through this we can devise if a string is accepted by the machine according to the language it represents.

I wish I could use epsilons to show my transitions to how I get answers on tests! HA... yea not funny.

Woo Fall Break! Sleep!

Fall break was nice and relaxing... finally I could sleep at a normal time and not worry too much about 236 assignments!

Anyways, we started into the automata and languages part of the course which I believe is the "final frontier" of 236. This is a pretty interesting concept and it ties nicely into our 207 class at this point since we just started studying regular expressions in Java.

An interesting example that Prof Heap went over was the pop machine one. How simple machines can be written using the concepts of "states" and transition states is really cool, and its just another way to look at programming. Elevators and other machines we use in our daily lives use computers use very limited CPU power and memory capacities and I understand why we try to write machines like this with very small amount of states.

Wait, what just happened?

So we wrote term test 2 on Monday and to be completely honest I felt as though I wasn't really ready to write it even after studying the entire weekend before for it. For some reason time complexity wasn't really making sense for me this year as it did last year in CSC165, perhaps its the way that we use induction now instead of purely direct proofs like last year?

A question on the midterm that I know I didn't do well on was very closely related to the second question on A2 which I think would be valuable to go through now:

For some context the part of the question that is relevant to time complexity question I had issues with was to show that the closed form for binary search was in the O(logn). Lets show that now...

A closed form of the recurrence function for Binary Search is: T(n) = logn + 1

To show that T ∈ Θ(logn) one can demonstrate 1) T ∈ O(logn) and 2) T ∈ Ω(logn).

Using the fact that T(n) has been proved to be a non-decreasing function I will use a Lemma discussed in lecture (http://www.cdf.toronto.edu/~heap/236/F12/Lectures/W6/thursday-annotated.pdf Page 6) that when n is not necessarily an integer power of 2 we have possible values of T(n) within a range of ň/2 < n ≤ ň. (Where ň represents 2⌈ logn ⌉, and n represents 2 logn).

So for part 1 I will show  T ∈ O(logn)

Claim T(n) ≤ clogn

T(n) ≤ T(ň) # Because we proved T is non-decreasing

        = lgň + 1 # Closed form of T 

        ≤ lg2n + 1 # Because n > ň/2 from above fact 

        = (lgn + log2) + 1 # By log rules

        = (lgn + 1) + 1

        = lgn + 2 

T(n) ≤ lgn + 2

Thus T ∈ O(lgn) with c = 1 & B = 1 (Breakpoint)

Now the second part 2

Claim T(n) ≥ clogn

T(n) ≥ T(ň/2) # Because we proved T is non-decreasing 

        ≥ log(ň/2) + 1 # Closed form of T

        = (logň – log2) + 1 # Log rules

        = logň – 1 + 1 

        = logň 

T(n) ≥ logn # Because ň is the ceiling of n (ň = 2⌈ logn ⌉ & n = 2logn )

Thus T ∈ Ω(logn) with c = 1 & B = 1 (Breakpoint)

Wow, now we're done

By showing that T is both in O(logn) & Ω (logn) then this implies T ∈ Θ(logn)!

I dunno why this simple kind of proof messed me up during the term test. I blaim it on the time constraint or maybe I was just having a bad day! haha

Golden Ratios... Golden Ratios Everywhere

Something I found very fascinating during my work on Assignment 2 was the usage of "Golden Ratios" in many different aspects of maths, finances, music, architecture... the list goes on! 

As mentioned in class deriving these ratios is not that hard at this day and age but according to many research documents the first usage of these ratios can be traced back to as early as Phidias of 490–430 BC!

I believe because our A2 is now past due I can discuss some methods I took to derive the golden ratio relationship with the question 1 of the assignment:

Open first glance with the OMCOFS I just started listing all the possibilities starting with the empty binary string of length 0 ("") and continued until a pattern was beginning to form in my head:

Length (n)	OMCOFS
0 1 2 3 4 …	{“”} = 1 {0} = 1 {00, 11} = 2 {000,011,110} = 3 {0000, 0011, 0110, 1100, 1111} = 5

It is clear from this list that something fishy is going on with the growth of OMCOFS as the binary string grows by 1 length. And after some careful observation I claimed that the growth is basically the Fibonacci sequence offset by 1. After the two first base cases it is clear to me that for example the binary string of length 4 is comprised of the amount of OMCOFS in the last 2 previous so H(2) + H(3) = H(4). Developing a recurrence after this point was pretty trivial and was basically the Fibonacci sequence with a different base case for n = 0: 


Now after this moment of triumph I began to have some issues unwinding the recurrence because for some reason when I was unwinding the recurrence began to EXPLODE with terms which I couldn't reduce enough to find a pattern to Fibonacci... only after some guidance by the wonderful Computer Science Aid Center TAs I was shown that perhaps we shouldn't unwind blindly and maybe try to unwind one of the recursive calls at the time... This was enough information for me to eventually wind enough and find the Fibonacci connection! 

Now that I unwound my recurrence and showed that there certainly is a closed form for the H(n) function which was Fibonacci sequence offset by 1 proving that it was basically a piece of cake since this was done both in class and done in lecture notes!!

Overall I had a much better experience with this assignment then the first, I felt more prepared for this one. I believe I just needed to be "warmed back up" into logic courses since the last time I did something like this was my first semester of University last year. This assignment, although only two questions, required abstract thinking ("All I need to mention is how abstract the definition of a OMCOF is! haha") and I believe this was very beneficial to my understanding of the course content.

Well thank you for sitting though my quick overview of my take on question 1 of Assignment 2, I sure hope that others share my same approach on it since I believe I was right.. maybe I was wrong? Who knows until the marks come out :P