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/