CSC236 at a Glance

I did not walk into this course with much enthusiasm given the fact that courses tend to get more strict and less fun when they are continuation of previous courses(In this case, CSC165). Induction flavors provided the basics for proving formal statements throughout this course. Then we learned about iterative and recursive programs. At first, proving programs correctness seemed unnecessary, but it proved me wrong since we can not always run our programs. Regular expressions introduced another way of presenting formal languages along with finite state automata. Overall, I am happy we skipped predicate logic, spent less time on formal structures and more time solving and proving mathematical puzzles.

Looking back at the first lectures

We started by looking at the different flavors of induction. Namely, simple and complete inductions. Complete induction proved very useful when encountering questions where we can't simply go from n to n+1. These combined with the Principle of Well-Ordering provide a very strong structure to prove formal statements.

Last Lecture: Pushdown Automata

Term test was fair but I don't think I did good on it. Maybe, I get to explain more about it after the morning section have written their test.

I liked the idea of PDA very much. At least, it opened the doors to understand the "remembering" property of FSAs and also provided a neat way to deal with non-regular languages.

Problem-Solving Episode

Here's my problem-solving episode using the approach suggested by Polya (http://www.math.utah.edu/~alfeld/math/polya.html). I decided to do this on Q3 of Assignment #2.

Consider a grasshopper that can hop up the stairs either 1 or 3 steps at a time. Let G(n) be the number of ways it can perform the climb when there are n stairs. For example, G(4) = 3, since the grasshopper can jump four stairs as either 1 + 1 + 1 + 1, or 1 + 3, or 3 + 1. Prove that for n >= 1, G(n) <= F(n), the nth Fibonacci number.

1. UNDERSTANDING THE PROBLEM

Let's look at some base cases:

G(1) = 1
G(2) = 1
G(3) = 2
G(4) = 3
G(5) = 4
G(6) = 6
G(7) = 9
G(8) = 13

2. DEVISING A PLAN

A grasshopper can hopup eaither 1 or 3 steps at a time. Therefore, he can reach nth stair using 1 1-hop from n-1th stair or using a 3-hop from n-3th stair. Therefore, the number of ways a grasshopper can climb up n stairs can be further subdivided into:

The number of ways he can climb up n-3 stairs + The number of ways he can climb up n-1 stairs

Therefore, for n >= 4:
G(n) = G(n-1) + G(n-3)
F(n) = F(n-1) + F(n-2),

Where F(n) is the nth Fibonacci number.

3. CARRYING OUT THE PLAN

Assume : n is an arbitrary natural number.
P(1) and ... and P(n-1) are true.

Base Case:
If n=1 then G(1) = 1 <= F(1) = 1
n=2 then G(2) = 1 <= F(2) = 1
n=3 then G(3) = 2 <= F(3) = 2

Induction Step:
Consider F(n) - G(n) = [F(n-1) + F(n-2)] - [G(n-1) + G(n-3)]
= [F(n-1) - G(n-1)] + [F(n-2) - G(n-3)]

We know F(n-1) - G(n-1) >= 0, by I.H.
F(n-2) - G(n-3) >= F(n-2) - G(n-2) , by def of G(n)
>= 0 , by I.H

Therefore, [F(n-1) - G(n-1)] + [F(n-2) - G(n-3)] >= 0
F(n) - G(n) >= 0
F(n) >= G(n)

4. LOOKING BACK

Therefore, we have proven forall n>=1 G(n) <= F(n).

Non-Regular Languages

We finally get to see what a non-regular language is. Let me first say that I'm surprised. The fact that this has to do with DFSA remembering states is a bit odd. However, the proof of pumping lemma makes sense . Proving that a language is non-regular uses the odd way the language is defined which in most cases seems pretty obvious and sort of "out of place". For example, "The language, L, of all binary strings of prime length regular" in which "prime" is just not fitting in.

Assignment 3

I've figured out what to do for most of the questions on this assignment.

The first question, is pretty straightforward. It wasn't going to be as easy if we didn't have the postcondition. But I am sure after tracing the code a few times, we could have figure that out also.

For the second question, I have found one counter example and I would assume proving the other three would follow the same general "IFF" procedure.
Edit: Well, I started proving the other three but I encountered problems proving them. As a result, I found 2 more counter examples which seems reasonable based on the fact that in computer science they don't make you do repetitive work.

Third question, I was a bit lost at the beginning but I think I am on the right track. Hopefully, I get to post my solution after the due date.

Forth question, I haven't looked at it YET because my partner is doing it. :]

Regular Expressions

Regular expressions proves to be very useful. For example, we can use the regular expression "\b[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}\b" to search for an email address*. Since I first learned about regular expressions in 207 I was not as confused although our approach in 207 seems to be different.

Proving that a regular expression denotes a language follows the [IF] and [ONLYIF] structure using concatenation on an arbitrary string. Since this is a prove, we already have the regular expression which makes concatenating much easier.

Term Test 2:
It was pretty easy. In fact, too easy. Too easy it makes me mad at myself for studying that horrible looking double-loop.

Problem Set #5:
Well, my first instinct was induction. It was, using it on what, which seemed a bit odd.

*http://www.regular-expressions.info/