Week 13

The test wasn't too bad. The state question was very easy, and I kept looking at the transitions to make sure there wasn't a trick somewhere in there (like making the state invariant of q1 be x equiv 2%3 rather than 1%3). I couldn't find any tricks. The other questions were less straightforward. I almost forgot that I had to prove Language equivelancy both ways and I ended up rewriting my proof in the last 5-10 minutes.

All in all, I study the wrong things. I expected the test to have questions on the pumping lemma, turning NFSAs into DFSAs into regex and things of that nature.

Week 12

The assignment went by smoothly once again with the help of my group. Working in groups is great as everybody has different insights into the problems, so the thing I will get stuck on my partner has a quick solution to and vice versa. Despite this, I obviously need to practice proving Regex equivelancy and will make sure to review it before the test. I can create my own equivelant regular expressions and practice proving their equivelancy.

The lecture: AAAAHH! There's almost no notes on the bulletin board and I wasn't feeling great and had to miss class. The pumping lemma, from the lecture notes, is very easy and I grasped it quickly. My only question that arises is why there needs to be a u v and a w. Although its obvious there are uses for it, there are situations that it seems pointless. For example, the question of having a string with the same amount of 1s as 0s, it could easily be solved with just a v and a w. The u is just dead weight. Oh well, I'll do it the way im taught!

Now I need to read the textbook to find out what I missed in lecture!

Week 11

Epsilon transitions are very weird.  The way NFSAs are defined with the epsilon transitions is very strange and I need to review this to get a better grasp on it. Same thing goes for turning NFSAs into DFSAs. However, the cartesian product is very easy, although tedious. Listing states over and over again changing 1 tiny thing each time is not my definition of fun. Despite their usefulness I can see myself growing to dislike both NFSAs and the cartesian product. Time will tell.

Week 10

DFSAs. These are the coolest things ever. You can draw a regular expression evaluator. It's a simple idea put together very interestingly. There are quite a few things to remember; states, transitions, start state, etc. but they are pretty obvious. I have to remember not to forget to mention the start state and the end state. All in all DFSAs are cool, easy, and seemingly useful. :)

I liked the example of the "difficult" regex to construct and how I was able to have a solution very quickly (despite being told it was hard). However on review, my solution had a hole that I need to fix, which is why I did not put it on the bulletin board. That is the problem I will do the full Polya method of problem solving on. 

Week 9

The test was not extremely difficult but I was unprepared due to my lack of understanding about loop invariants. The question involving the loop was the most difficult for me only for the fact that I did not know how to include an invariant that will help me in my proof. It was easy to prove that the function terminated but my proof was definitely not in the pattern of what we were taught (and was probably wrong). The rest of the questions were easy.

Finally a change in the flavor of the material, the regular expressions are a wonderful break from induction (unless were going to use that for this too...). They seemed very confusing at first (especially the Kleene star but by the end of a lecture, they made sense.) The proof was very bizare but I am sure that with practice these things will become easy.

Week 8

I did not attend the lecture and after writing the test I wish I had. It was very difficult to figure out the proofs for functions with loops simply from the lecture notes. The concept of a loop invariant, although seemingly useful, does not differ from a postcondition in my mind?

The assignment went by very well even with my limited amount of time to work through and understand it. The partner system helped very much and I am upset I never utilized partners before. The questions were very similar to those done in the lecture and it was not difficult to extend those ideas to the assignment.

Week 7

Proving correctness of a program is an interesting concept. Rather than the way we have been taught to check our code (through test cases), we now define preconditions and postconditions to see if they work every time the program is recursively called. I wonder if this would be too complex of a proof for one of our 207 assignments in order to avoid writing test cases. The concept itself is very interesting, yet the proofs themselves don't seem to be. Oh well.

The problem set was very straightforward. Probably one of the easier ones so far but it's always the stupid silly mistakes that make me lose marks. The only difficulties I encountered are determining what is a sufficient for these (non-numerical) proofs. I find I have to define what something like

# Postcondition: revString(s) returns a string with
# the characters of s in reverse order.

What does reverse order mean? If I am the one deciding it, can I just say reverse order is defined as:

revString(s[1:]) + s[0]