week 11 -- a3

Well, after just having finished a3 (literally), I'm feeling good about regular expressions and finite state automata. I didn't find any of the material too difficult and found the assignment (fairly) straightforward. Most of the definitions and proofs in regular expression are defined using structural induction, which I feel that I am already familiar with.

Question 4 on the assignment did pose me a bit of trouble. I initially took the approach of analyzing entire strings that were multiples of 5, trying to find a pattern, which I felt would help me nail down which states a corresponding machine might take. In going to TA office hours, I found out that this was the wrong approach. I found it was better to look at each individual symbol as it was being inputted into the machine, where a 0 would multiply that number by 2 and a 1 would multiply that number by 2 and then add 1. To find the machine I then just looked at the last digit (in base 10) and made 10 states accordingly.

week 10

I am currently working on assignment 3 and am not finding it too difficult (although I've retracted that statement in the past on previous assignments). There doesn't seem to be any questions that are very abstract and that would require many hours of laboring (ahem, a2 question 1). Or maybe I am just becoming more comfortable with induction proofs (hopefully!).

I've studied the course notes for regular expressions quite a bit now and find them to be fairly intuitive. We've already encountered a few questions in the course involving strings, but I suppose now it is simply more formal, together with different sets of alphabets.

For problem set 5, it asked to prove that for a finite set of strings there would be a regular expression that would denote the respective language. For my answer I first showed that it would be defined over some finite alphabet and then showed that by definition there would then be a regular expression to denote that alphabet. Now thinking back, it may have been good to give more details about the first step of the proof and actually show by induction that there would be a finite alphabet.

week 9

After writing the test this past week, I feel I did fairly well. I believe my biggest stumbling block at the moment is converting a proposed solution into formal notation. I feel I can grasp the content of the material fairly well, I just do not feel very comfortable with the precision and detail given by my answers. I think that with time that I may gain confidence in the format of my answers.

One example that surprised me was the one given on the past tests. It was a problem that involved a 'zigzag' function and asked to prove that if the precondition holds, then the program terminates. My answer did not use induction and seemed fairly informal when compared to the model solution, which had three claims, one of which was proven through induction. I am beginning to see mathematics as more of a language, so hopefully, as with any other languages, the more I speak it the more fluent I will become.

week 8

I'm currently getting ready for test 2 and waiting for the solutions for assignment 2.  I feel that I did fairly well on assignment 2.  Question 2 had me slightly confused at moments, as I overcomplicated things.  In the course notes, for the mergesort example, they make the assumption that n is a power of 2 in order to get rid of the floors and ceilings.  I hadn't realized that this assumption was only necessary for that purpose, but had thought (for some strange reason) that is was necessary in order to obtain the closed form, and that it would apply to the assignment question.  As I found out in the TA office hours, this wasn't necessary.  I believe the correct solution only calls for a closed form found through repeated substitution and then reduction with a floor of log7n.  The last question in the assignment, on correctness, was very similiar to what we learned in lecture and in the course notes.  I believe the only difference was that we had to show that m was between b and e, where m = sqrt(b*e)

For the test, I plan on practicing some of the extra problems in the course notes and reviewing the assignment.  Hopefully, there won't be any extra tricky problems in the test that ask for some sort of complicated assumptions.  From what I've seen so far, correctness doesn't look to be too difficult.  I'll review what's in the course notes and lecture notes.