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
No comments:
Post a Comment