twothirtysix

CSC236 at a Glance

2008-12-05T19:17:00.000-08:00

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

2008-12-05T18:42:00.001-08:00

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

2008-12-04T19:41:00.000-08:00

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

2008-11-30T13:33:00.000-08:00

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

2008-11-28T13:48:00.000-08:00

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

2008-11-23T10:33:00.000-08:00

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

2008-11-15T21:25:00.000-08:00

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/

Problem Set & Assignment : The Aftermath

2008-10-31T11:25:00.000-07:00

Unfortunately, I couldn't do the LOG(refer to my last post) for the following reasons:
1) My computer had to be close.
2) I rather write than type.
3) Laziness.

Problem set #4 was pretty straightforward. My only problem approaching it was the flavor of induction. I used complete induction because it felt more safe based on its definition. I usually use complete induction when I can't get from P(n) to P(n+1). However, for this question we can get from P(n) to P(n+1). So my problem was with the fact that there were two base cases(Namely, P(0) and P(1)) where in the definition of simple induction we only verify P(0). So this is my random thought for proving this problem using simple induction:

*Prove P(n) for all n>=1 using the base case P(1)
*Verify P(0) manually
Since there is no natural number between 0 and 1 => P(n) for all n

So basically, my real question is if we can have more than 1 base case for simple induction?

Assignment #2:

#1 - We barely get questions like this. We have all the tools necessary. There's no complicated formal structure. It was a great puzzle and I have to say, although I don't think I got it right, I enjoyed doing it very much and I would happily loose marks for questions like this.
#3 - I enjoyed doing this question very much. Mainly because of the verbal explanation of G(n) which made total sense.
#4 - Very similar to lecture notes and as a result a straightforward question.

...and Happy Halloween!

Problem Sets & Assignments

2008-10-22T12:01:00.000-07:00

I missed two days of lectures. Being in the evening section makes it 6 lectures. First one due to sickness and second one due to high load of assignments and midterms. However, I managed to do problem set #3 very easily. I think not knowing what was going on in the lectures actually didn't mislead me to look for something similar to Fibonacci closed form.

I'm far behind and I'm going to dedicate the next two days studying lecture notes, and doing problem set #4 and assignment #2. My next post is going to be in log format showing my progress or rather confusion in these two days.

Term Test # 1

2008-10-10T22:05:00.000-07:00

Today we had our first term test. As expected, three proof questions. It was pretty fair and we had enough time.

For some reason, when doing proofs using induction I find my mind looking for a direct mathematical proof instead of an induction proof and I have to remind myself almost every ten seconds that remember that this is a proof using induction. It's as if my mind is working against me. Today, for two of the questions I got carried away looking for a way to "derive" the result instead of trying to "verify" it and spend almost 70% of my time doing so. But, fortunately I got back on track and was able to make it just in time.

And here's this week's lecfun taken from week 5, slide 3:

First Post

2008-10-02T14:29:00.000-07:00

I got my SLOG up and running. I know it doesn't sound much but I finally managed to get rid of that horrible looking toolbar at the top.

This week, I decided to investigate the relationship between Fibonacci sequence and the Golden Ratio. I first got interested in Golden Ratio, after I saw "Pi", an independent movie. I have to say out of all the relationships, the formula by Johannes Kepler got my attention the most. It is probably the simplest formula:

He wrote "as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost”*

And one more thing...
Fortunately a "fun" idea for my SLOG hit me today. Being more of a graphic designer than a writer, I'm going to finish my entries for the week by a "lecfun" section. It's a screenshot of lecture notes taken out of context. I hope everyone understands that this is ONLY for fun and I also hope to get the approval from Danny Heap.

*Kepler, Johannes (1966). A New Year Gift: On Hexagonal Snow. Oxford University Press, 92. ISBN 0198581203. Strena seu de Nive Sexangula (1611)

Tumblr

2008-09-30T12:16:00.000-07:00

I wish we could use tumblr instead of blogger like all other cool people.