Assignment 2 and allusions to Chomsky

Interestingly, in looking at the Assignment 2 questions and trying to learn about proving properties of binary strings, I stumbled upon the topic of "context-free grammars", which incidentally we are covering later in this course according to the schedule. I also learned they were originally described by Noam Chomsky, who I know about from his political writings. I very much admire Chomsky, and find the potential connection between formal languages in computer science and natural language very interesting!

Anyways, I'm admittedly having a bit of difficulty connecting the lecture material to the first question, and I hope that tonight's class will shed some light on that. The second question is more directly related to lecture material, and I can at least envision how to start. I'm happy the assignment is a bit shorter this time (or at least, appears to be; I might end up eating my words). Once I figure out how to solve questions like the first assignment problem, I'll probably write a post about it!

Post-Test, and starting "more practical" things

Well, we had our term test last week and I turned out to be pretty prepared for it, despite not feeling that way. The questions were all on structural and complete induction, so I didn't have trouble with the format, but two of them included recurrence relations which we didn't have a lot of practice with (other than talking about Fibonacci numbers relatively briefly in class). I was able to work them out and I think I did quite well, which is a good feeling!

The course seems to be changing flavour a bit now, and is starting to include reasoning about complexity of actual programs. I actually really like the purely theoretical proofs we've been doing -- it's fun to work them out, but it's also nice to do something which has a usefulness which is more immediate and apparent (even if it is, after all, still quite theoretical). It definitely has practical benefits, the first one coming to mind being comparing seemingly similar algorithms, which helps me stay motivated.

Anyways, this term has been a balancing act for me so far (a lot of commitments, school and otherwise), so it is good to get some positive feedback! I think my studying habits have been pretty reasonable for this course, but if I have trouble with the next assignment I might have to devote more time to it.

Preparation for 1st Term Test

Despite having a lot due on Friday, I was able to get through it all and finish the first assignment. My main issue turned out to be with the last question (the binary substring question); I did the proof almost entirely in English, and originally tried to prove it by starting at a smaller string and showing any combination of larger strings would have the same property, but after consultation with Dan this proved to be more difficult to do convincingly. I ended up going backwards; showing that if a given string has the property, the next smallest string ending with the same digit also has the property.

It was interesting for me to learn that proofs written entirely in a natural language are not only acceptable, but in some cases preferable to those heavily relying on mathematical notation. I can see why, too; writing in a natural language forces you to express your thinking very explicitly and can expose you to holes in your reasoning.

I've been mostly following the lectures, but I need to do some practice for the test coming up in two days. I plan to go through the lecture exercises and write some past tests as soon as possible!

Assignment 1, etc.

I thought it would be a good idea to finally create a blog for CSC236, so -- surprise! -- I did. I am currently still in the throes of Assignment 1, despite it being due at the end of the week. This is something I'd like to remedy as the term goes on (that is, complete the assignments several days in advance), but the fact that I'm taking 6 courses and that two of them also had assignments due this week made it difficult this time.

Question 1 wasn't too much trouble, and Question 2 I think I'm just missing something small for my induction step. For question 3, I recognized a method for "differentiating" the new element in a set as you go from size n to size n+1, but the algebra isn't working out for some reason (maybe a mechanical error?). Question 4 I've yet to really look at, but have a few ideas in mind as to how to tackle it.

I'm using LyX and am happy to have an excuse to use LaTeX again. I've always appreciated its aesthetic and the air of professionalism it lends to documents. If only I could find a good way to stop enumerated lists from starting over when I place some content in between their elements...