Term tests are done!

I refrained from writing about term test 2  until now in case the questions are similar for both the morning and evening sections.

I got a little nervous when I flipped through the paper and discovered that there were only two questions for the test. Although that meant plenty of time, it could also have meant that each question was more challenging. With this in mind, I dug right into the first question. I first tried substituting every n in the unwinding equation with 2^k. But after a few unwinding, the equation soon looked very messy and complicated. So I reverted back to doing repeated substitution using n, keeping in mind that n is a power of 2. As I continued solving, the question reminded me of a tutorial question that involved sum of geometric series. Suddenly I was unsure of my approach to this question, because unlike the tutorial question where f(n) was n^2 (the time it takes to divide and recombine), the f(n) for this test question had a lower degree (I cannot remember exactly what it is). Therefore I was hesitant to use the sum of geometric series formula, thinking that perhaps there was a clearer way to do the question. However, since time was limited, and I could not see another immediate problem-solving approach, it was better to come up with an answer than nothing. Having an answer also helped me move on to the next part of the question, which was to prove that my answer was correct.

The second question was slightly easier to solve than the first in my opinion. We had recently handed in Assignment 2, so the questions on A2 were still fresh in mind. Since the second question had to be solved with the help of n-hat (the smallest power of 2 that is greater than or equal to n), I approached the question in the same way I did for A2.

Even though there were only two questions, I had just enough time to finish the test. Now I'm starting to worry about the level of difficulty of the final exam.

OMCOFS: a Fibonacci pattern

When I first scanned through assignment 2, I was somewhat afraid to dig into question 1. OMCOFS (a.k.a Odd Maximal Contiguous Ones Free Strings) seems complicated just by looking at its name. It sounds very scientific and high-level,  like something that would appear in science-fiction movies, something along the lines of UFO. But it turns out that these scary-looking binary strings are much more comfortable to deal with than UFOs. 

Since we have to develop a recurrence, I start the question by first listing some examples of OMCOFS with increasing lengths and trying to find a pattern. I do this by first writing down all the possible binary strings of a particular length, then pick out those ones that are OMCOFS. This is not hard to do for binary strings of lengths 0, 1, 2, 3, and 4. But it becomes more difficult for lengths of 5 or more. I know that there are 2^5 = 32 possible binary strings of length 5, but I can only list 31. I don't know which binary string I'm missing. In the end I had to turn to the wonderful, multi-purpose Python. With the help of a little Python program, I can finally get all the possible binary strings up to length 5 and pick out the OMCOFS.

n      number of OMCOFS      OMCOFS
0                   1                        empty string
1                   1                                0
2                   2                             00, 11
3                   3                       000, 110, 011
4                   5           0000, 1100, 0110, 0011, 1111
5                   8      00000, 11000, 01100, 00110, 11110,
                            00011, 11011, 01111

 

From the "number of OMCOFS column", it is obvious that the recurrence is related to the Fibonacci sequence, but with the numbers shifted upwards. Where the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5..., our recurrence starts with 1, 1, 2, 3, 5, 8... .

 

So we know that the recurrence is:

 

H(n) =    1                            if n < 2

               H(n-1) + H(n-2)    if n >= 2 

 

Now the question becomes: how do I explain why this recurrence correctly counts the number of OMCOFS of length n? It is not enough to just say I found it by looking at the pattern generated by the first few OMCOFS, and it will always be true. There has to be some pattern in the strings themselves such that the strings of length n-1 and n-2 somehow give rise to the strings of length n. But wait! This whole idea of strings sounds strikingly similar to something we did in lecture one day! As I furiously flipped through my past lecture notes, I came across the recurrence of "the number of binary strings without adjacent 0s". The idea is that, to obtain all the binary strings of length n without adjacent 0s, we append a 1 to the binary strings of length n-1 without adjacent 0s, and append a 10 to those of length n-2. With this idea in mind, I come back to our recurrence H(n). I discover that to obtain all the OMCOFS of length n, we just append a 0 to the OMCOFS of length n-1 and append a 11 to those of length n-2! The pattern is explicitly displayed by the OMCOFS I listed above, and it explains why, in numerically terms, we would have a Fibonacci pattern. The number of OMCOFS of length n is just the sum of the number of OMCOFS of length n-1 and n-2.

 

With the first obstacle cleared, I happily go on to unwind the recurrence. ^_^