So long and good night.

Aside from all the interesting (inductions, ternary trees, and FSAs) and uninteresting (master theorem and proofs of equivalences of principle of simple induction, strong induction, and well-ordering) materials I learned in this course, if there is one more thing I should take away from this fantastic course CSC236, it is that I should never cram for the course slog. Unlike what someone said on his/her slog: “If anyone post large amount at one time, probability the posts will copied from somewhere else or just some crap words that make nonsense.” (pardon me for the awful grammar), what I wrote in I my slog really is my original and genuine thoughts of the course. I crammed for the slog partially because I am not the most diligent person in the world and I do enjoy a little sense of urgency. Like I said in my first-ever slog written in September, I really enjoyed this course, largely due to Professor Heap’s competent teaching skills. This is in no way an act of ass-kissing as finding examples of incompetent professors is like finding sleeping students in their classes. I have learned a lot from this course and I look forward to future computational logic courses.

DFSA should be on Oprah's Favorite Things List.

Just to clarify, I don’t watch Oprah’s show. No, not a single episode.

I absolutely love Deterministic Finite State Automatas. It is amazing to me how a small machine can denote an infinite language. Professor Heap’s software demonstration of DFSA further raised my interests in DFSA.

Here is one DFSA I drew:

A DFSA that accetps a string with sub-string "1011".

(F(o(r(m(a(l))))) (L(a(n(g(u(a(g(e))))))))

All the definitions and concepts of formal languages make sense to me except for one: Kleene star. I did not follow at all every example involving kleene stars during the lecture, which was really frustrating. It is, nonetheless, not a hard concept to understand. The intricate part is that the kleene star of any language includes the empty string. For example, the kleene star of an EMPTY language is the empty string. This may seem a little bizarre at first, but a little glance at the definition of kleene star sure will clear any confusions. As a result, ((0+1)(0+1))*(0+1) denotes all binary strings of odd length and 1*0(1*01*0)* denotes all strings with odd number of zeros ending with a zero.

Term Test Two and two term tests.

It was hard to review for CSC236 when the first term test for MAT237 was approaching. Luckily, the second term test for CSC236 took place almost 14 hours after the brutal MAT237 term test. I read through all the past slides about program correctness and the divide-and-conquer technique. It surprised me that my performance of the second term wasn’t as bad as I expected. Lord has mercy upon my soul!

Recursive and iterative correctness of functions.

Since inductions and recursive functions can both be expressed recursively, it is reasonable to prove the recursive correctness of a function using induction techniques. Iterative correctness, however, is much harder to prove. We have to first come up with loop invariants. We then have to prove the invariants are true using simple induction and the partial correctness of a function comes as a corollary. Finally, we have to prove that the loop terminates using principle of well-ordering.

Here is a problem I used to practise the recursive correctness of a function.

def maxnum(L):
"""Return the largest number from non-empty list of numbers L """
1. if len(L) == 1 : return L[0]
2. if L[0] > maxnum(L[1:]) : return L[0]
3. return maxnum(L[1:])

Prove P(1):Since n = 1, the list L is of length 1. This satisfies the condition len(L) == 1 at line 1 in the function maxnum(L). Thus, maxnum(L) returns L[0], which is the first and only number in the list. As a result, maxnum(L) returns the largest number in L when L has the length 1. Therefore, P(1) is true.

Prove \forall n \in N\{0}, P(n) \implies P(n+1):

Assume n \in N\{0} and assume that P(n) is correct. Then for any list L of length n, maxnum(L) returns the largest number in L. Assume L' is any list of length n+1, meaning it contains n+1 elements. Then L'[1:] is a list of length n and maxnum(L'[1:]) returns the largest number in L'[1:] by assumption.Then L'[0] > maxnum(L'[1:]) or L'[0] <= maxnum(L'[1:]).

Case 1: assume L'[0] > maxnum(L'[1:]). Then the condition at line 2 in maxnum(L) is satisfied. Then maxnum(L) returns L'[0], which is the largest number in L'since L'[0] > maxnum(L'[1:]) means that L'[0] is greater than any number in L'[1:], which implies that L'[0] is the largest number in L'.

Case 2: assume L'[0] <= maxnum(L'[1:]). Then the condition at line 1 and line 2 in maxnum(L) both dissatisfied. Then line 3 in maxnum(L) is executed and (L) returns maxnum(L'[1:]), which is the largest number in L'since L'[0] <= maxnum(L'[1:]) means that maxnum(L'[1:]) is greater than or equal to L[0], which implies that maxnum(L'[1:]) represents the largest value in L'.
Then maxnum(L) returns the largest number in L'. Then for any list L' of length n+1, maxnum(L') returns the largest number in L'. So P(n+1) is true. P(n) \implies P(n+1). \forall n \in N\{0}, P(n) \implies P(n+1)

Since P(1) \and \forall n \in N\{0}, P(n) \implies P(n+1) is true, we can conclude, by PSI, that \forall n \in N\{0}, P(n).

Problem Solving Exercise :

Penny Piles Exercise:

The PDF version of the problem can be found here: http://www.megaupload.com/?d=2ZM1BL0K

1) Understand the Problem

This dazzling question that involves pennies and drawers can be easily simplified as dividing 64 (or any even number) by half and produing a certain number by adding quotients.

2) Devise a Plan
First try to 48 as indicated in the question. If that's possible, try some other numbers to see if they are possible to produce. Record the numbers that have been sucessfull produced to see if there is any pattern.

3) Carry out the Plan
48 can be obtained by performing the following steps:

Furthurmore, by furthur developing the above diagram, we have:

As we can readily see from the above nicely-laid-out diagram, every number from 0 to 64 can be represented by moving half of the pennies from one drawer to another. The underlying reason for this is that any positive integer can be represented as additions of several 2^n, where n \in N. For example, 115 = 2^6 + 2^5 + 2^4 + 2^1 + 2^0.

4) Conclusion

Hence, as long as the number of pennies in the left drawer can be represented as 2^n, n \in N, we can always produce any number of pennies in the range of [0, 2^n] by swapping half of the pennies from one drawer to the other.

The complexity of the complexity of merge sort.

Here I thought unwinding techniques was somewhat uneasy to absorb, far came the complexity of merge sort. There are essentially four steps involved in the quest of finding the complexity of merge sort.

Step 1: We have to unwind the inductive formula with special cases to come up with a non-inductive formula.

Step 2: We then using strong induction to prove that the non-inductive formula is correct for all the special cases.

Step 3: We prove the monotonicity of the inductive formula.

Step 4: We merge the monotonicity and the non-inductive formula to prove the complexity of merge sort.

This four steps are the core components of the master theorem for divide-and-conquer. I don’t particular enjoy rigorous proofs, but I find the idea of dividing a bigger and more complex problem into smaller and manageable problems enchanting.