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.

Considering Complexity

I hated it in CSC165, and I still hate it here. I understand that the time complexity of an algorithm is one of the most important things in computer science for obvious reasons, but I still have trouble with it. In any case, I've been reading my old CSC165 notes over and over again and ditto the course notes, along with a lot of poring over the relevant parts of the course notes. I'll have this in hand eventually, and if not, well at least it seems to be much less a focus of the course than in CSC165.

Midterm Madness

Well, the midterm was this morning, and it didn't go too badly I think. The first question about the Fibonacci sequence was a breeze, almost suspiciously so, but unless I've really gotten bad at reading trick questions then that was fine. The second question, I realized 15 minutes after the test, I pulled some real bull algebra on, so I know I screwed that up, but at least the structure is there, so here's hoping for part marks.

The third question about sets was something more interesting! I stared at it for a good 15 minutes or so, having gotten as far as writing down that all sets have 2^n subsets and that each following set's subsets were those of the previous + subsets containing the element n. With two minutes left on the clock, I had a revelation (though it might have been wrong, I felt pretty good writing it down and remain confident it was a valid proof). By complete induction and partitioning S into S_1 and S_2, where S_1 is S less all the subsets containing {n}, and S_2 is S less all the subsets without {n}, you get two subsets of equal size, and better yet, you know S_1 is just the set of subsets of S:{1,..,n-1} and thus by the I.H. has 3 * 2^n-3 subsets. S_2 being the same size means it will have the same number of valid subsets, so the total will end up being 3*2^n-3 + 3*2^n-3 = 3*(2^n-3 + 2^n-3) = 3*(2^n-2)

Exactly what was needed. That was a fun proof.

I still feel pretty stupid about the algebra in question 2 though, because for some idiotic reason I wrote down 3^n+1 = 3^n + 3^n instead of 3^n + 3^n + 3^n or 3*3^n. Hopefully there'll be some mercy, because I think I did end up pseudo-legitimately showing that 3^n + 3^n > 2*(n+1)^3, so it follows 3^n + 3^n + 3^n could only be larger as well. Oh well, all in all it could've definitely gone a lot worse.

Now with that midterm out of the way and nothing due immediately after the weekend, time to enjoy the long weekend and go party before thanksgiving.

Regarding Recursion

I've always found recursion to be my favourite subject, and this has yet to change. Recursive functions always seem to end up more efficient than the vanilla / iterative alternative, and most of all just seem incredibly elegant to me. Proving recursive functions seems to have a natural flow to it similar to the functions themselves.

Whoever originally came up with the idea of automatically reducing a problem down to near-nothingness to solve the most complicated of things must have been a real genius.

A1

Well, A1 was due last night -and in retrospect it wasn't THAT bad.

The first question was a breeze, and everything to do with phi made sense after a couple of hours spent sitting and thinking, so no worries. But that lunch menu thing killed me. I ended up writing more of an essay than a proof.

Oh well, at least everything else seemed in order and correct. And, worst comes to worst, it could only be worth 6%.

That said, at least I get the feeling I'm starting to have more of a grasp on the material than CSC165, where at the end of the day, the symbology could still be a problem. Knowing how to go about a proof one way or another from start to finish seems to be getting that much easier, which I guess could just be from time spent exposed to the material but in any case it feels like real progress.

Onwards now to correctness and next Friday's test!

I think I may have to stop by Prof. Heap's office at some point for a break-down of the proper proof for #2, I must have botched that.