Week XIII

Wow!! unbelievable! this is the last week of the term! I also have already experienced this last year but every time when I am on the last week, I feel like half nervous and half relax. Before mentioning about the test coming on Friday, I really like to thank to Prof Heap for teaching us. I had him last year for csc165, and I think I was pretty much satisfied with his teaching and marking. Hopefully I have a good luck at the exam too.

There is a test coming on Friday as I mentioned. I am very nervous especially for this test because I feel I am not that well prepared, but I will do best I can do. As prof Heap mentioned, the test will be focused and based on the chapter 7 of the textbook. I will go over the lecture notes and textbook as many as possible. DFSA is very important. Still, I do not understand its concept 100%. Thus my plan is to visit TAs, review, and ask friends.

Week XII

For This week I would like to share my 'Problem Solving Episode' for the assignment 3 #1. Although the question was hard, but I really enjoyed the question after all. The question is :

def quotRem(n,m) :
#Precondition: n,m are natural numbers
# m is not 0
r = n
q = 0
while (not (m > r)) :
r = r - m
q = q + 1
# Postcondition: n = qm + r and 0 <= r < m

1) UNDERSTANDING THE PROBLEM
Since this function is not tested by machine, like Wing IDE, the only way to understand this problem is by reading line by line and understand what's is going on each line. However this would not be enough to understand perfectly, so I am going to prove this using loop invariant to see if the precondition implies the postcondition. In order to do that, we need to know the number of iteration(s) and when the loop terminates.
2) DEVISING A PLAN
Since we figure out that the number of iteration is n = q_i*m + r_i and it terminates E_i = r_i in N,
now, according to the standard tool for proof, we need to find which tool we are going to use it for the proof. In this case, PSI would be most effective and suitable.
3) CARRYING OUT THE PLAN
So this is the proof we get finally:
P(i) : If the loop has i iterations, then n = q_i*m + r_i and E_i = r_i in N,
if the prcondition is true. forall i in N, P(i)

Base case:
If i = 0, then r_i=n q_i=0. Since n = q_i*m + r_i = 0 * m + n = n,
this satisfies the postcondition, and also E_i = r_i = n in N by precondition,
so P(0) is true.

Induction Step:
Assume i in N and that P(i) is true. Assume there is an (i+1)th iteration of the loop and that precondition holds. By line 4, r_(i+1) = r_i - m and by line 5, q_(i+1) = q_i + 1. Then, n = q_(i+1) * m + r_(i+1) = q_i * m + m + r_i - m = q_i * m + r_i. Also, by P(i), r_i in N that r_i >= 0 and r_i >= m (by loop cond) So r_i - m = r_(i+1) >= 0 which is in N.
Therefore, precondition implies postcondition ( P(i) => P(i+1) )
4) LOOKING BACK
Overall, we found that this question is not that complicated but we have expected too high level.
Too much thinking sometimes lead us somewhere with nowhere to go. We actually have referred the lecture notes. There was not a similar question but the idea was quite similar. So the lecture note saved us. I am still wondering about if the loop invariant question always require PSI or not.
I want to see what kind of question requires PCI to prove.

Week XI

The week is the last week for the problem set. And because this is the last one I expected a hard question on the problem set. But it wasn't actually. The question was : Prove that L, the set of binary strings of odd length, equals L(((0+1)(0+1))*(0+1)). Before trying to prove directly, I took a time to read lecture notes and discuss with my friends who were also doing this. I knew that the L will always have strings of odd length but I did not realize that I needed to prove this with two directions where set of binary strings of odd length is in L or L in the set of binary strings of odd length. (I visited TA's to comfirm the answer) I did not know why I need two directions but the TA showed me why. It sounded clear, reasonable and obvious.

The lecture was about NFSAs. Since I am very close to the end of the classes of this term, many assignments, tests are waiting for me. Because I need to cover them, honestly I really had not enough time to look up the lecture slides. The materials for this week seem to be very different from previous ones. I better go study for 236 too.

Week X

Firstly, the problem set was due on this week. The question seemed to be very insteresting because it sounded very obvious and because it was so obvious, I was quite confused on how to prove. This is one of common situations that everybody would agree with this that when there is something that it is so true, definite, and obvious, it might confuse you because it sounds very easy!. So, before trying to prove, I looked up the lecture notes first and refreshed my brain with all of the definitions. After, I wrote something and brought it to the TA centre to check if he agrees or not. I realized it was simple, not even induction needed.

due to busy days, I could not attend the lecture. I might look up some slide later to catch up.

Week IX

honestly I do not have much to say about this week because I was very sick and there was second mid term test. I tried to write the test but felt not well. But, I read some of lecture notes and tried to catch up other people too. I did not want to leave this things out for later, otherwise I would have too much work for third mid term as well as assignment.

Well, so my plan is to cover up leftovers that I have not read yet and bring some questions to TAs.

Week VIII

The second assignment was due on this Monday. Due to many assignments and midterms last week and also upcoming ones, honestly, I really could not have sufficient time to consider the questions. Even though we ran out of time, we could finish it. Perhaps, if there were no TAs during the time we were doing, there was no way to finish it. I really thank for TAs. The most of time our group spent on the first problem which was very confusing and seemed to be very unclear because all of my group members suggested different ideas each other. Thus, it was very hard to decide what it is supposed to be. But TA showed and helped us to catch up the concept that was totally different from ours. It was rather simplier idea - set up some definition of trees as :

T(n) = Total number of node n
T(L) = Total number of node in the left subtree
T(M) = Total number of node in the middle subtree
T(R) = Total number of node in the right subtree

and by using definitions, T(n) = T(L) * T(M) * T(R) ....

Other than that question, we divided up question into one each. So I quite regreted that I could not do other questions. Hopefully I have a luck on this assignment. For next week, read textbook and understand some concepts.

Week VII

The problem set seems very straight forward. It is just like the lecture note - Proving precondition => postcondition. I can see that without using induction, this problem would be solved by case by case, where case1 should be string less than 2 and the other case should be string greater than or equal to two. Since cases are set, proving part won't be that hard. I hope I get a good mark on this too.
I think Prof Heap very nice. Even though problem set worth max 2% each, he looks like he gives away marks from these and make us to practice and catch concepts of the theory. Well, I also hope the rest of the problem sets will be easy enough.

This week's lecture is about 'Program Correctness' The theory seems very straight forward but not too easy though. My weakest point is that I am very slow reading and understanding codes by myself without running it on computer. This is absolutely true that without fully understanding of codes, no program can be proven. So, before jumping into proving something, I need to read over and over the some code and speed up my understanding. Honestly, I have no much things talk about this topic.
I'll just go practice some of examples on lecture notes.