Finale

Term test three was today, and my mood is nothing less than jubilant. For the first time, I'm pretty sure everything went well! :D The first question on the DFSA was a breeze, though I'm glad I didn't start with it. After a few minutes of staring at it, it didn't make any sense, so I moved on, but with Prof. Heap's announced corrections it was, well... easy. I'm 90% sure I handled both the questions with the regex and language just fine, after lots of study of the posted solutions. Most of all though, I'm glad I went to ask Prof. Heap about Q4 from A3, since that gave me a proper understanding of the Cartesian product and how to use it, which is probably why Q1 was so doable.

Well, the course is drawing to a close, and on the whole it's been one of the more educational and enriching ones I've ever taken. I never realized until now what a powerful tool induction is, and I think I'll be leaving this course with a good grasp on logical proofs, more so than just on the structure (which is the feeling I got after CSC165). The relatively brief coverage of FSAs has given me a taste for them, and I'm quite looking forward to CSC363. Now just to put up with one week of hellish studying and a lousy exam schedule, and then time for next semester's load-out of all-CSC courses, including CSC300. Thanks Professor Heap for a great course!

A3 and Week 12

Well, we handed in A3 on Monday, and I think it went fairly well. The first three questions were familiar enough, and I'm really quite sure we got them right. I'm glad I went to Prof. Heap's office to ask about Q3 though, wouldn't have thought to use structural induction - though it is a neat application, and makes sense. Question four is what I'm really worried about. It was a bit of a rush towards the due date and I think the answer we ended up submitting was uh... sketchy. The invariants are there, at least, though no matter what we just couldn't find a pattern indicating multiples of five in binary numbers, so I'm worried.

Oh well.

As an addendum, the pumping lemma is pretty neat, and I suppose it's necessary to have some sort of handle on non-regular languages.

More on FSAs

Well, the course is drawing to a close, and it's been a pretty good experience, but more on that in the next couple of weeks.

The Cartesian product is a pretty neat device, and the functionality of combining machines that perform individual tasks is awesome, since as far as I can tell using it one can make an FSA for more or less anything at all.

That said, I'm sort of having trouble dealing with them when it comes to actually designing an automaton that uses them. Visualizing a machine that's a combination of two of them is tricky, but I'm sure with a lot of course note reading and looking at Q4 of A3 I'll be fine.

Incidentally, this is the first time I've found the course notes to really be the best resource available.

With respect to regexes...

I certainly didn't expect to encounter these in this course!

After A2 of CSC207, I've taken a liking to regexes, and the idea of treating them as string-generators rather than string-finders is pretty neat. Languages are an interesting idea, though, and the idea of performing operations on regexes is novel and interesting.

DFSAs are way cooler though!

Making completely arbitrary machines that can perform pretty much any conceivable task on a binary number is awesome, and I've been doing some reading up on them and Turing machines and this is where it seems the really hardcore theory starts.

Thoughts on Term Test Two (And the aggressive application of alliteration)

Well, the second term test was this morning.

All in all, it didn't go too badly. I'm unforunately pretty sure I messed up the first question involving recursion - I just wasn't quite thinking clearly and have the sinking feeling that I pulled some "Assume A therefore A" stuff back there, seeing as I never actually used the definition properly... I think. In any case, the question about proving the correctness of that function with integer division was fine, and I'm quite sure I got that one right (I've got a handle on proving correctness in general now, I think. Iterative functions at least). Though I think I might not have explicitly stated any invariant, everything's there (maybe a bit buried in that wall of text). The string reversal one seemed alright too, so all in all a test that didn't go too badly.

That's another story from all this business with the OLM not supporting Unicode text. I messaged Prof. Heap about it and I hope it won't be a problem turning it in now, since getting a zero on something as big as an assignment would be pretty harsh.

On A2

Well, assignment two was due last week, and for a change I worked in a group. I found that that made things a LOT easier - not particularly by divvying up work or anything, but by having people to bounce your ideas off and vice versa. "Hey dude, skim this and tell me if it makes sense" are some of the best words to say and hear, because it's easy to fall into a pit of desperation and just write some pseudo-logic bull as the deadline draws closer. The first question was a real doozy, and I'm glad I went to both Prof. Heap's office hours and the T.A. office hours later in the day. Prof. Heap's explanation of considering it a sort of two-dimensional sum REALLY broke the ice for that question, and while finding and testing a formula took a while (and boy was it an ugly one, with those two sums and like three variables), I'm confident it was correct. Cue two hours of trying to figure out how in God's name to prove that hideous thing, before stopping by the T.A. (whose name I never got, seeing as we went there for one quick question). Apparently, proving it more with an essay showing the process of the derivation of the formula (which was fundamentally recursive/inductive) was most of the proof, which got us going on the road before writing out a proper proof by complete induction. What a question! Question two was kind of rough, but comparatively a breeze. Three wasn't anything to worry about, really, and while four was fairly lengthy it was quite similar to other proofs we'd seen before so it wasn't really a stretch. That's all of assignment two then; all in all a busy, long process but a rewarding one.

Other than that, my mind now turns to the upcoming midterm, considering that Profs. Clarke and Gries have shown mercy and extended the 207 A2 to next Monday, it's my exclusive focus for this week. If the first one and the CSC165 midterms are any indicator, they shouldn't be too rough so long as you do the assignments and problem sets correctly and carefully. Regardless, time to bust out the book during the remainder of this Sunday and the coming week.

Concerning Correctness

Well, we've been handling correctness lately. It's always been kind of neat to me, representing sort of a meshing and intersection of the worlds of purely theoretical and logical thought with normal code. At first, I still couldn't really appreciate the necessity of proving the correctness of code, but over the last little while I've come to realize that it generally makes the bizarre cases something should be handling a lot more apparent just by writing it out in the context of a proof, as opposed to some IDE. In any case, I've found it generally not too rough, though I have had a bit of trouble rationalizing the need for loop invariants to myself, when it seems they're usually something like n is always a natural number, which *seems* self-evident, but I imagine it's necessary when trying to prove more complicated code.