conclusion

This is the last week of 236. Some classmates feel that this course is very easy. I don’t think so. This course is the most difficult one I have taken. Base on my programming experience, I feel some courses most students consider as tough, like 209, are not famous as their reputation. But I lack some theory fundamentals of computer. I had not learned any theory of computer before. I should learn some by myself. (Actually no theory skills need to be used during my work) That is the reason why I come back to school at this age. 236 is one of challenging courses for me, another one is mathematics. 

We are going to take final next week. Due to my poor term test 2, I had to go over the materials carefully for getting better mark.

About Blog

This is the first curse to require us write down a blog. I have not token higher level courses. Maybe there is another one asks us to do the same thing. I don’t know. Is that challenging? For me, No. I am keeping my personal blog since 2005. In my personal blog, I wrote articles for questions of interview, my opinion of programming, and some updated processing of the book I am translating. But, I have never thought about putting down my feeling about course. That should be a good idea to extend the topic of my blog. I will figure out a new category during the holiday break.

I do not write their blog by weekly. Sometimes I prepared the tests or quizzes, so I had to postpone updating my blog. But most time I could not remember to do this until some classmates asked “do you write your blog recently?” when we were chatting. So, everyone who always forgets to keep blog should set their clock alert to “wake up wake up, you have blog to write.”

Chapter 7: Regular Expression

The last part of this course is about regular expression. I have being used regular expression for a long time.  The material of lecture introduced is easy for sample. They include 0 and 1 only. (Oh, I am wrong, empty and null are included.)In practice, regular expression involves all characters and signs, like email address, http links or formatted numbers. So, the content we learned looks no useful. Maybe there is higher level course that expends this basic skill to introduce more complicated samples like we meet in the work.

So far, I do not know the usage of automata in the live. I remember I started to use regular expression at beginning of this century with some programming language(JAVA or C#??). Base on my opinion, regular expression and automata were developed with language development. So, we use regular expression to match search. Is it the unique application for regular expression?   

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. 

Recurrence problem

When I read some books, i found solving Towers of Hanoi problem let me understand the whole process of proof.

Everyone knew Hanoi problem. So the recursive solution has three stages.
Stage1:  Move the top n-1 disks from the first post to the first post to the second using the solution for n -1 disks. This can be done in Tn-1 steps.
Stage2: Move the largest disk from the first top to the third post. This takes just 1 step.
Stage3: Move the n - 1 disks from the second post to the third post, again using the solution for n - 1 disk. This can also be done in Tn-1 steps.

This algorithm shows that Tn, the minimum number of steps required to move n disks to a different post, is at most Tn-1 + 1 + Tn-1 = 2Tn-1 + 1.

So we can find a recurrence.

T1 = 1
Tn = 2Tn-1 + 1  for n >= 2

So we can use this recurrence to compute any number of terms in the sequence:
T1 =1
T2 = 2T1 + 1 = 3
T3 = 2T2 + 1 = 7
T4 = 2T3 + 1 = 15
...

Let us prove this Claim

the proof is by induction on n. The induction hypothesis is that Tn = 2^n - 1. This is true for n = 1 because T1 = 1 = 2^1 -1.
Assume that Tn -1 = 2^(n-1) -1 in order to prove that Tn = 2^n -1. Where n >= 2
Tn = 2Tn-1 + 1 = 2(2^(n-1) - 1 ) + 1 = 2^n -1

The first equality is the recurrence equation, the second follows from the induction assumption, and the last step is simplification.

Chapter 1: Complete Induction

Sometimes, I cannot understand the meaning of Complete Induction.  I always confuse how to use it. I have an example here which gets from “How to prove it”.

Sample: Suppose n is an integer larger than 1 and n is prime. Then P(n): 2^n -1 is prime.

We can see

n = 2, 2^n – 1 = 3

n = 3, 2^n – 1 = 7

n = 5, 2^n – 1 = 31

Then, the next prime number 7 is in N. The expression holds for every prime number less than 7. So, from complete induction, P(7)  holds. Similarly, the expression holds too for next prime number 11. Such that, I get conclusion that P(n) holds for every prime number. As a matter of fact, everyone knows this predict is not correct. But I cannot figure out where is wrong with my proof.

The definition of Complete Induction is described for all natural numbers. In this sample, I do not use 4 and 6 in the proof because they are not prime number. Does this not obey the rule of Complete Induction? I do not think so.  At ton of proofs, we define the base case which is from bigger numbers than 1. That means the domain of variable may not include all natural numbers.

Chapter 0: sample

Let’s start my first blog of csc236.

In the chapter 0 Preliminaries of Notes (“Notes” below), the author defines “Partial Order” is “if R is antisymmetric and transitive”. At first, I thought the definition is wrong because this definition of this term in the “How to prove it” (“How” below) is “if R is reflexive, transitive, and antisymmetric”. As if the definition in Notes is missing reflexive. From definition 4.4.1 of “How”, R is said to be antisymmetric if x in A and y in A then xRy and yRx implies x = y. Base on that, xRy and yRx are correct if antisymmetric holds. That could to say that antisymmetric includes reflexive, I guess.

The reason of confusion is the sample R3 in the Notes. R3={(a,b): a and b are persons and a is an ancestor of b}. Notes explains that R3 is a partial order. Form definition of reflexive, we can image from R3: I and I are persons and I am ancestor of I. Oh, I become my daddy, or I am my son, so I am I. Does it sound weird? Of course, there is not any defect in the logic. But, I do not think this sample could help us to understand the term. So, this sample is used in the notes is not reasonable.

This is my personal opinion.