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.

Problem Set 3

Finding the closed form for the given function was tricky. Unwinding it in the conventional sense didn’t quite lead to the closed form. The crucial steps towards finding the closed form were done after unwinding and recognizing the patter in the un-winded terms. After unwinding and simplifying, I realized that each term was a multiple of 3. More specifically, the ratio between two consecutive term is 3. Thus the expansion was that of a geometric series. Thus to find the closed from of G(n), I had to use the geometric series formula, and plug in the ratio and the first term in the series. After finding the closed form of G(n), proving it using simple induction was pretty straightforward.

First Assignment

The most challenging question of the first assignment would have to be question 4. I didn’t know how to approach the question to begin with. But after wrestling with it for awhile and getting help on it, the question started to make sense to me. Proving the contradiction was a bit tricky, because we had to choose the well ordering principle. I had to prove that there exists a smallest numerator for a quotient representing the golden ratio. This led to the required contradiction proving that the golden ratio is an irrational number, which I used to answer the last part of the question: proving 5^1/2 is irrational.

Second Problem Set

The first part of the problem set where we had to prove that for n > N, n postage can be made with 5-cent and 11-cent stamps was pretty straight forward, since we did a similar question during lecture. Proving the second part of that question was a bit more difficult than I initially thought.

I wrote a small java app to figure out what was the smallest n that the postage can be made consecutively after. The magic number we were looking for was 39. Proving that 39=11x +5y has no solution on the natural number line was a little trouble at first. I was trying to come up with an elaborate proof, but later realized a simple simple proof would suffice. I went to the TA office hour and he mentioned that all that the proof requires are some cases to illustrate that 39=11x +5y has no natural number solutions.

I formulated the proof focusing on 11x, because it has fewer cases than 5y.