Assignment 3

I am still wondering how to prove postcondition and termination.

In the question 4, I developed such program.

Function binSearch( x, A)

    b=0

    e = n – 1

    while ( b <= e )

    m = ( b + e ) // 2

    if (A[m] > x )

        e = m – 1

    else

        b = m + 1

return e

I tested it and got correct result base on professor’s example posted in piazza. But, I found it is very hard to prove loop invariant and postcondition. It is a little different of example of lecture. And professor did not show the entire proof.

If I modified code like this:

Function binSearch( x, A)

    b=0

e = n – 1

if ( x < A[0] )

    return -1

else if ( x >= A[n -1 ] )

    return n -1

else

        while ( b <= e )

        m = ( b + e ) // 2

        if (A[m] > x )

            e = m – 1

        else

            b = m + 1

    return e

This snippet seems to easier to prove one of postcondition that is -1<=p<=n-1. But, for my professional view, the former is more concise, the latter is more amateur.

Then, if I continued to make WHILE loop more bloated redundant, the proof would be easier and easier. As a professional developer, I could not accept such code like that. But….. how about my mark?

The solution has not been posted yet. I will check out professor’s answer. 

Chapter 2: Lemmas

When I did my assignment 3, I found some questions were about Chapter 2. I have not noticed this chapter. Professor held this chapter at eighth and ninth weeks. At that time, I thought those contents were come from chapter 3.

The chapter 2 talks about proving iterative and recursive codes. These codes in the textbook and lecture are very easy to understand. Actually, they are so easy that I don’t need to take any time to understand. But, the proof seems difficulty. When I proved questions of assignment, I wanted to quote Lemma 2.3, 2.4 and 2.6 for the same condition. I could use them directly. I had to use the method of proof of these Lemmas to prove the questions. Unlike the mathematics, these theorems and lemmas are shown in the textbook are samples only, they are not for quotation.

Am I wrong? 

Chapter 7: DFSA

I got test2 back at last class. I got very low mark. That was the penalty for that I though this course WAS easy. I have only one last chance at final. I am planning to take some days off to go over carefully.

Last week, we saw DFSA. Drawing circle and arrow to show automata. Actually, I did not catch the meaning of that in the class. At weekend, I read the notes first, but still, it was not easy to understand. (Or it could not be understood easily at my age!!). So, I have to read another book “Introduction to Languages and the Theory of Computation (by John Martin)”. I found the samples are described more clearly. That is good for me. 

Quiz

The course will be done in this month. I felt the material is a little harder. At least, I could not catch some points during the lecture. Of course, that is my problem. I should go over the notes before the class. The content of quizzes in these weeks is followed the lecture tightly. So, if I have not understood what the professor introduced in the class, I could not figure out how to solve the question, even if TA explains some knowledge first. So, I lost full mark of quiz. This is a little bit unfair. 

Term Test 2

The test 2 was gone. But, I did not do the good job. The questions are a little difficult to understand for me. So, I need to do more exercises in the last month.

As a part time student, I could not take office hour to ask my questions. So, an excellent textbook is very important. But, the course note is not enough to understand all material which is taught in class. For the first chapter, I read “how to prove it” as supplementary book. I have not yet found out any matched supplementary material for chapter 3.

Actually, the course note is not too bad. It only needs to add more examples and explanations. 

Chapter 3: assignement 2

In the assignment 2, we need to get close form of H(n) = H(n-1) + H(n-2) if n >2. Then based on the skill we are taught form lecture, we get H(n) = F(n + 1) by unwind. We already know the close form of Fibonacci.  So, we get final close form that combines both of H(n) = F(n+1) and Fibonacci close form.

In the book of “mcs” that is the textbook of CSC240. The author uses the method that is to prove Fibonacci to prove H(n). So, author gets a homogeneous linear form first: f(n) = a1f(n-1) + a2f(n-2) + …adf(n-d). Then get x = (1+sqr(5))/2. Quoting the theorem 21.31: if f(n) and g(n) are both solutions to a homogeneous linear recurrence, then h(n) = sf(n) + tg(n) is also a solution for all s and t of Real number, author get the same answer.

It looks that the former way is easier. But three authors of “mcs” are professors of MIT and researcher of Google. Why do they not to use that method to prove this? I has just a little bit of confusion.