Final Week – Reflections

The course seems to have sped by so fast, but I feel I have learned so much in the duration of this course. Before this course I wasn’t comfortable with induction to say the least, but after professor Heap’s illustration of induction in all this varieties I feel confident I can tackle any proofs in general. I admire his flare and enthusiasm for the course, even though it was a long 3 hour evening lecture. He was always prepared and attended to each student’s difficulties. He was also available after office hours for any late questions that came up. I hope he’s my professor for future courses.

All the csc236 TAs at the help center were a great help. I was always there for each problem set and assignment. I was always greeted in and taken care of. They were very informative and made sure I understood the underlying concepts. With their help I was able to complete the course work and gain a new perspective on the course material.

Problem Solving Episode – Polya style

Although the majority of my blog postings deal with a problem solving episode, here is one written using Polya’s approach. I will write problem set 4 using this approach, only because it’s not mentioned on my blog yet.

1. UNDERSTANDING THE PROBLEM

My csc207 Python knowledge helped me understand the code. Specifically how substrings work in Python. The code was not too complicated. The pre-condition was that the string s must be Python string. The post-condition was that the function revString return the characters in s in reverse order. The body of the code involved a recursive call to revString. It simply truncates the first character and concatenates it to the end of the string at each recursive call. When the loop terminates, the order of the characters in the original string would be reversed.

2. DEVISING A PLAN

Before devising a proof for this code, I had to consult the lecture slides and course notes and find similar correctness proof examples. To prove the correctness of this code, I had to consider cases. The code has two conditional executions. If the length of the string is less than 2 or otherwise. Within the first case (length less that 2), there are two sub-cases: when the length is 0 and when it’s 1. These cases are essentially the base cases of the proof by complete induction. In the induction step, I would proof the case when the length is greater than 2. It is here I would make use of the induction hypothesis, that is P (pre-condition implies post-condition) holds true for length =0 to length = n -1.

3. CARRYING OUT THE PLAN

I began with the assumption that the size of the string is a natural number n. I defined the predicate P to be that pre-condition implies post-condition of revString for all size n. Finally I assumed that P holds for length=0 to length = n-1.

Then I completed the base cases. If the length of the string is 0 (empty string), then the code simply returns an empty string. Thus P holds when n =0. If the length is 1, then the code returns back the string, since the reverse of a single character is itself. Thus P holds for n=1.

The final part was the induction step. This is the case where the length is greater than 2. My argument here was that by line 2 of the code: return revString(s[1:]) + s[0] , we know that the length of s[1:] is n – 1, since it slices the original string starting from the second character. Also we assumed in the IH that P(n-1) holds true. Line 2 return a string of length n, since s[1:] is n – 1 and s[0] is 1. Thus P(n) holds true. That is, pre-condition implies post-condition for length n and consequently for all natural numbers n.

4. LOOKING BACK

Reviewing the above proof, I felt satisfied that it adequately proved the correctness of revString. I suppose there are more elegant ways of proving this code, but I’m quite content with my approach. It seems simple and straightforward.

Problem Set 6

This problem set involved proving an implication (if-then statement). We had to prove that if a language L consists of odd length binary strings, then it can be denoted by ((0+1)(0+1))*(0+1). I used the idea of inclusion for both directions. That is if T is the set of all odd length binary strings, then an element belonging to T must also belong to L(((0+1)(0+1))*(0+1)). To prove this direction, I started off with an odd length binary string and constructed the regular expression that would denote it, step by step. In the end I was left with the expression ((0+1)(0+1))*(0+1)), thus proving the implication in one direction. The other direction is proving that if an element belongs to L(((0+1)(0+1))*(0+1)), then it must belong to T. To prove this direction I broke the regular expression into its even and odd components, and showed that the concatenation of both components yields an odd length binary string. This prove seemed to be pretty lengthy but it was straightforward.

Problem Set 5

Although this problem set seemed trivial at first, it took me sometime to express the proof formally. The theorem was: If language L has a finite number of strings, then there is some regular expression that denotes L. Any finite set of language can be expressed by a regular expression using the union or concatenation operator. As long the theorem can be proven using one of these operators, then it would be true for all cases. I used induction on the number of strings in an arbitrary language to prove the theorem. Let the language L be {l1, l2, l3, l4}. This language can be denoted by the RE, R= l1+l2+l3+l4. If a new string (l5) is added to L, then it could be denoted by R= l1+l2+l3+l4+l5, thus proving that any language of finite length can be denoted by a regular expression.

Assignment 3 Question 3

In this question we (group effort) had to proof that a regular expression that doesn’t include the Kleene star would denote a finite language. The way we understood this question was that, if we include the Kleene star in our regular expression then we would have infinite repetitions of a pattern, thus consequently not a finite language. We set out to proof by simple induction that Kleene star leads to an infinite language. But this approach didn’t seem promising when we got to describing languages and alphabets. Thus we abandoned this approach and set out to proof that if the Kleene star was excluded, we would have a finite language. More specifically, if we only had union and concatenation available to our regular expression, then we would only be able to match languages consisting of finite number of strings. This approach was more plausible and was easier to carry out. We used complete induction on the sets of language, and show that the concatenation of two unions yielded a finite language.

Second Test

The Second test was a disaster for me. I got the morning session and the office hour mixed up and ended up showing up for the test 20 minutes past the start. I was stressing out of my mind. I managed to answer two of the three questions. I did well on the test than I anticipated, I actually passed. Professor Heap was very understanding and fair towards my situation. Thank you Professor.

Second Assignment

The first question on this assignment seemed complicated at first because it involved a combinatorial explosion. The trick in solving this question was to find a pattern and generalize it for all number of nodes. I made sure I understood the question thoroughly before I proceeded to solve it. I started out by drawing ternary trees from the root node. I expanded each combination of nodes and noticed the pattern as the number of nodes increased. I realized that the distribution of the nodes among the three sub-trees behaved like combination without replacement. Thus I devised a summation formula that yielded the total number of non-equivalent ternary trees given n nodes. The number of nodes available for each sub-tree is the total number of nodes minus that used by the previous sub-trees at that specific height. I tried the formula on different number of nodes and convinced myself that it works for all n.