However, it has been proven that I can never do a whole assignment without getting so mad at myself. This time was even worse than the previous one.
I spent 9 hours on Saturday on question 1 of the second assignment. At the end of the day (or rather the start of Sunday), I was convinced that I had the solution for it. I then stayed up another hour to type it in, which took something like 5 pages. I was really proud of my work! Little did I know!
Of course, it would have been too convenient for my solution that I spent 9 hours trying to figure out to be correct! While talking with a couple friends about this exercise, I realized that I was not including some strings in the set of OMCOFS that I should have been including.
I was only looking at consecutive 1s within the strings, so I was including strings like 11000 or 11110 but missing strings like 11011, where there is one or more 0s in between the 1s.
It is so funny how something like this happens every time. I have a folder on my computer that is called "probably useless" and in that folder I save stuff like the result of my 9 hour work on Saturday: stuff that ended up being not what the assignment was asking, but at the same time, too "cool" to just delete ( I also have a beautiful file in there with my own version of an exercise from my stats assignment and the number of those files only keeps increasing ). Some day I will look back on it and laugh.
Now however, in order to make that file in the weirdest possible way useless, I'm blogging about it (better than nothing!). So this is what I came up with on Saturday ( I can't blame anyone for not reading the whole thing ) ...
I
notice the following:
Firstly,
no matter what the length of the set of binary strings in question
is, the string that consists only of 0s will always be one of the
OMCOFS (note 1).
Secondly,
in every OMCOFS s1, we want to have an even number of contiguous 1s.
In other words, we want to have the substring '11' and the substring
'1111' and so on, provided that the length of those substrings is
less than or equal to the length of s1. Call the length of s1 n.
Then, the expression floor(n/2) gives us the number of those substrings that
will fit in s1. For example if floor(n/2) is 1, then only the substring '11'
will fit, if it is 3, then the substrings '11' , '1111' and '111111'
will fit (the 3 first substrings that contain only 1s and have even
length) and so on (note 2).
Now
lets see how we can construct the OMCOFS of length 5 from the OMCOFS
of length 4.
First
of all, in the OMCOFS of length 5, we will have the string '00000'
for sure (from note 1).
Also,
since floor(5/2) is 2, the substrings '11' and '1111' will show up in the
OMCOFS (from note 2). But the OMCOFS of 4 also have substrings '11'
(since floor(4/2) is also 2). If we write the OMCOFS of length 4 that contain
'11' in the following order: 1100, 0110, 0011 (the first one starts
with the contiguous ones and then the 1s get shifted to the right),
then we can get the OMCOFS of length 5 that contain '11' by adding a
0 to the end of each one and to the beginning of the last.
So
1100 gives us 11000,
and
0110 gives us 01100
and
0011 gives us 00110 and 00011.
Now,
if we write the OMCOFS of length 4 that contain '1111' in the same
order as before, we can get the OMCOFS of length 5 that contain
'1111' in the same way.
There
is only one of those in this case, namely the string 1111, so we will
treat it as if it is the last one (i.e. we will add a 0 in the front
and the end of that string). So we get the strings 11110 and 01111
of length 5.
So
the set of OMCOFS of length 5 are { 00000, 11000, 01100, 00110,
00011, 11110, 01111 }.
Then,
if we know the OMCOFS of length n (where n is a natural number
greater than 0), we can construct the OMCOFS of length (n + 1) in
the following way :
- Add 0s to each OMCOFS of length n that contains the substring '11' in the way demonstrated above. Do the same for OMCOFS of length n that contain substring '1111' and then '11111' and keep going as long as the substring of 1s has length less than or equal to n.
- In the case where there is a substring of 1s that fits in strings of length (n + 1) but not in strings of length n, add this substring to the set of OMCOFS of length (n + 1) without adding any 0s to it (call this " case * ").The reason we are adding it is that since the substring fits in length (n + 1) but not in length n, it must be the case that that substring has length greater than n but not greater than (n + 1), so it must have length exactly (n + 1). It also must be true that floor(n/2) < floor((n+1)/2) (from note 2), which can only happen if that n is odd and (n + 1) is even.But if (n + 1) is an even substring of 1s and it has length (n + 1), then we want to include this to the set of OMCOFS.For example, the string '111111' is not in the OMCOFS of length 5, since its length is greater than 5, but it has to be in the OMCOFS of length 6.
- Finally, add to the set of OMCOFS the binary string of length (n + 1) that contains only 0s (note 1).
Define
H(n): number of OMCOFS in the set of binary strings of length n.
Case
1 : if n is even and (n + 1) is odd, then floor(n/2) = floor((n+1)/2) so the even substrings of
1s that fit in strings of length n are exactly the same as those that
fit in length (n + 1).
The
number of strings of length (n + 1) that contain '11' will be equal
to the number of those of length n that contain '11' plus 1 (since
to the last one we are adding a 0 both to the front and to the end).
The same will hold for the number of strings that contain '1111' and
so on (in total, it will hold for floor(n/2) such cases) (note 2).
So,
H(n + 1) = H(n) +floor(n/2)
(since
we are adding 1 floor(n/2) times).
This
can also be written as H(n + 1) = H(n) + floor((n+1)/2) ,since floor(n/2) = floor((n+1)/2) in this case.
Case
2: If n is odd and (n + 1) is even, then we have case *.
In
this case, as before, to get H(n + 1), we have to add floor(n/2) to H(n) for the
substrings of 1s that fit in both and we have to add 1 more for the
string that fits in length (n + 1) but not in n. So we will have H(n
+ 1) = H(n) +floor(n/2)+ 1.
Also,
we know that floor((n+1)/2)= floor(n/2) + 1 since we know that floor(n/2) < floor((n+1)/2) is true in case * and that n
and n + 1 are consecutive natural numbers.
So
H(n + 1) = H(n) + floor((n+1)/2)in this case.
So
in both cases, the recurrence is : H(n + 1) = H(n) + floor((n+1)/2) or, equivalently,
H(n) = H(n – 1) + floor(n/2).
For your own good, I am going to skip the two pages of unwinding a sigma of floors. But the closed formula that I got is the following:
H(n)
= (n^2+ 3) / 4, if n is odd
or
H(n) = (n^2+ 4 ) / 4, if n is even
The worst part is that this time I do not even have the excuse of working too late at night. I spent practically the whole day doing this. All day today (especially while solving the exercise all over again and realizing that it comes down to something so close to the Fibonacci series, which we have already unwound in tutorial!!) I was trying so hard to convince myself that I got more practice by making that mistake and that this is a good thing. I failed miserably.
I promise myself right now that next time I will double check my formula a bajilion times before I get too carried away with it.
I really hope I do not end up writing a similar blog post to this while doing assignment 3!
