Second assignment already

In my second post of the semester, I think it only makes sense to talk about the second assignment, which is due at the end of the week.

Although question one sounds intimidating at first, there really is a lot you can prove about Odd Maximal Contiguous Ones Free Strings. I figured the best way to really understand what the question was getting at was to actually look at valid OMCOFS of varying length and try to discern a pattern between the length of the string and how many OMCOFS can be found.

To make this simple and repeatable, I quickly wrote the following small set of python functions:
def enum(n, s):
    if(len(s)==n):
        return [s]
    else:
        return enum(n, s+'0')+ enum(n, s+'1')

def is_valid_omcof(s, count, index):
    if index == len(s):
        return count % 2 == 0
   
    elif (s[index] == '0' and count%2!=0):
        return False
    elif (s[index] == '0' and count%2==0):
        return is_valid_omcof(s, 0, index +1)
    else:
        return is_valid_omcof(s, count+1, index+1)
def count_omcofs(n):
    count = 0
    for i in enum(n, ''):
        if is_valid_omcof(i, 0, 0):
            print i
            count+=1
    return "count = "+ str(count)

Using these three functions, I can generate all the possible strings of length n, and check which one of them are valid OMCOFS. I started running it with different lengths and I found an interesting result about the listing process of omcofs. Programmatically:

list_omcofs(size) == ['0'+omcof  for omcof in list_omcofs(size-1)] +   

                                  ['11'+omcof  for omcof in list_omcofs(size-2)]

Reducing problems down to linearly easier problems is probably not that useful in terms of efficiency improvements but if it ever became desirable to express the list of omcofs of any length recursively as a combination of smaller length strings (e.g. due to a max size limit for list_omcofs() ), this would come in handy. 

About the course so far:

I like this course. The proofs we handle are intuitive and it feels as though reasoning my way through the ones we've had so far has paid off, which isn't always the case with UofT courses. For once, i feel a direct link between the quality and depth of the thought that goes into the assessments and my grade in them.

I'm not exactly sure how i feel about the Slogs so far, but I've read somewhere that keeping a blog can be an effective way to improve one's communication skills so I've definitely been curious. That said, I'm finally getting down to my first blog post. God knows, I've procrastinated it for long enough, but with the midterm done and the second assignment so far into the future, it seemed as though this was the only piece of work i could do for 236.

So all in all, i've enjoyed the lecture material so far and i look forward to starting newer topics in computational theory.