FSA's

The course just took a big turn from talking about program correctness to a new direction and introducing us to FSA's. I liked proving correctness of programs because it was material we have been exposed to 165 last year and it was more familiar to us. We knew what pre-conditions and loop invariants were and it was very easy for us to follow the lectures and understand what was going on. I felt like the course was becoming more manageable in terms of doing minimal work outside of class. But now that the course has moved into talking about finite state automata, it's a new challenge to understand the lectures completely on first exposure. But so far form what I'm seeing, FSA's are pretty cool. Looking at the transition functions δ*(q, s) they do incorporate some neat computer science since the transition from some state q will depend on the alphabets of s so the call will be recursive till s is an element of the alphabet and not a string. At this point there is a state to transition to and to start from on the back going back down the call stack. So they do allow computer scientists to model some complex problems that are too tricky to work out on paper which is subjected to mistakes. Also I really like the diagrams in this section of the course, the diagrams are "worth a thousand words" and really help me understand quickly the content we are learning. Hope things continue to make sense in the coming lectures.

Program Correctness - Termination

The way we have gone about proving termination was a little interesting since we have used the principle of well ordering. I've never thought we would actually use this and it definitely helps in my understanding of well -ordering since at first I couldn't really think of a nice example where well-ordering is absolutely clear and makes intuitive sense. For example proving termination of an iterative binary search program meant that we had to show the difference between the last element's index and the first element's index in the array/sub-array was a decreasing finite set and so it must have a smallest element. Indeed it is true that when F >= L can only happen if F = L happens first since either F or L changes in each loop iteration decreasing by 1 (never both changing). And so F = L implies L - F = 0 where 0 is the smallest element in a natural numbers set. And we know L - F is always decreasing by one as was shown in lecture so that Li+1 - Fi+1 < Li - Fi where i is the ith iteration of the loop assuming i + 1 iterations happen (in other words either F or L decrease by one in each iteration and so L - F continually decreases). So since Li -Fi is a decreasing sequence of natural numbers (since L and F were natural numbers and decreasing either by 1 each iteration keeps them as natural numbers) then it must have the smallest element 0 and so the loop will terminate. It's neat to see induction playing a role in everything we are doing now and seeing this it seems to be a very fundamental computer science concept. I guess we'll be seeing again in 263!

Test tomorrow!

After doing A2, it forced me to look over the relevant notes and sections in the book and gave me a good understanding of what we've been doing in class. I found question 1 on A2 to be quite long as we first need to analyse some binary strings and find a pattern for OMCOFs, establish a recursive definition, explain why it's true, then unwind it using repeated substitution and express it in terms of the golden ration (Phi and Phi hat), and then finally using complete induction prove the close form is correct. That is a lot of work and I'm hoping on the test the questions won't be this long and be more reasonable like the length of test 1. Test 1 had 2 very easy brief questions (1 and 3) and question 2 was the longer one as it needed some well written explanations for what was going on inside the induction step. I feel like A2 Q1 format will be simulated in an easier way in the midterm since in A1 we had a question similar to our test 1 Q2. I am really hoping it will be easier since question 1 didn't take 1/3 of 50 minutes to solve, it took much longer than that plus the time it took to reread the proof and correct it. At least now with exposure to the type of questions in A2 it is fair game on the test! 

So to prepare for this test I must review the tutorial problems by doing all the questions and checking my answers with the solutions and then search for some past midterm questions to get even more practice. It sounds like a lot, but I must also read the lecture notes on correctness of recursive algorithms since it might be on the test. I did miss the lecture when we started covering this so I will defiantly skim the 2nd chapter of the book since the lectures really require you to be there to understand the notes posted up.

So tutorial problems + past test questions + reading on the new unit will hopefully get me ready for tomorrow's midterm.