A2 post 1

So I have quite a few posts piled up from wading through the enigma that was assignment 2, but I didn't want to post them until after the deadline had comfortably passed; being vague about your solution is never fun.
I encourage you to look through the full text to be able to easily follow along.

The definition of OMCOFs is phrased in quite a terse (though precise) way, but to put it simply there are no odd-length maximal substrings of just 1's.

I started by writing out this:

• H(0) = 1            {}
• H(1) = 1            {0}
• H(2) = 2            {00, 11}
• H(3) = 3            {000, 110, 011}
• H(4) = 5            {0000, 1100, 0110, 0011, 1111}
• H(5) = 8            {00000, 11000, 01100, 00110, 00011, 11110, 11011, 01111}

I immediately saw the recurrence was Fibonacci in nature and wrote it out. But...then we had to explain why it was correct. Suddenly, chaos.

I stared at this sequence for 3 hours straight. I drew trees, tables, lots of arrows; the page borders were filled to the brim with 0s and 1s. I was a mess, and thoughts about getting a late penalty were rampant in my mind. I just couldn't see it, and except for the fact that my deadline was coming up, I loved every minute of it.

I find nothing in maths or computer science can be as exciting as that process of discovery associated with an unfamiliar problem, and nothing as exhilarating as finally reaching that elusive solution.

After about 2.5 hours, something clicked. I realized the recurrence I was using only depended on the previous two values, so my intuition led me to believe perhaps the set construction would work the same. At this point I suspect many readers should be able to see the pattern, but for some reason it didn't jump out at me until half an hour later in a whoosh of inspiration...followed by half an hour of berating myself for not seeing something so simple. 

It was exactly like the postage stamps example we had done in class, the recursive aspect was just a dimension meant to throw you off. Just add a 0 to the set before and a 11 to the set before that! 

Revival and apologies

Wow...I've neglected this for two weeks as midterm season buckled down on me. I'd really taken too many courses so I've dropped a few, letting me focus on the important things, like this SLOG! I'm going to try and get daily posts in for a while to catch up on all the amazing things we've covered in this course. Stay tuned tomorrow, and hopefully every day after for this week.

Introduction

Hello world,

            My name is Gaurav Gupta, and I’m a 2^nd year CS major at the University of Toronto. One of our classes, namely csc236 (which is basically the second step as far as computational theory courses go), requires us to maintain a SLOG, which I still find a puzzling thing to do. I suppose my writing skills could use polishing up anyways. Before diving into the course content though, there are a few things I should mention. I’ve chosen to integrate my CS major with a specialist in Molecular Genetics; CS is a secondary field I only picked up during my first year, so if I chance upon any interesting connections to some of the research I’m doing I’ll be sure to mention it. Secondly, though I’m a pretty avid user of symbolic notation, I haven’t gotten the chance to pick up LaTex yet, so I’ll be figuring out how to portray proofs on the go. Lastly, if you’ve somehow ended up here having no clue what csc236, welcome! I’ll be assuming a basic knowledge of symbolic notation and proof techniques, but be sure to comment if something is unclear…which will probably happen frequently, I often find myself having difficulty expressing my intuitions during lecture.

-Gaurav Gupta