CSC236 - SLog

Outside the Wall

2008-12-05T10:40:00.003-06:00

"...we came in?"

I am leaving with a positive attitude.

Another theory course almost done and over. With 236 like 165, it was a great experience. The concepts covered were done well, with a great deal of subtle humour.

I feel that the exam, with the proper preparation, will go well, even though I have three exams in three days (CSC236 being on the final day).

I went in with a great attitude and so am leaving with one.

"Isn't this where..."

Polya Problem Solving

2008-12-02T14:08:00.003-06:00

0. THE PROBLEM A3:3

The language defined by L(R), where R is a regular expression that does not include a Kleene star, is a finite language.

1. UNDERSTANDING THE PROBLEM

Condition: the regular expression denoting L does not contain a Kleene star I need to show that if this condition is true then L is finite.

2. DEVISING A PLAN

This question is similar to one in the course notes. I will consult the course notes. It appears that some form of induction will be needed, structural induction.

3. CARRYING OUT THE PLAN

L(R), the language denoted by the regular expression R, which does not contain a Kleene star, is defined by structural induction on R:

Basis:
If R is a regular expression, by definition then either R = null or R = \epsilon or R = a, for some a \in \Sigma.

L(null) = null (the empty language, consisting of no strings)
L(\epsilon) = \epsilon (the language consisting of just the empty string)
For any a \in \Sigma, L(a) = {a} (the language consisting of the one-symbol
string a)

Induction Step:
If R is a regular expression without a kleene star then by definition either R = (S+T) or R = (ST) for some regular expressions S and T, where we can assume that L(S) and L(T) have been defined inductively and denote finite languages.

For these two cases we define L(R):
(i) L((S + T)) = L(S) \union L(T); and
(ii) L(ST) = L(S)*L(T)

Note that (i) is the union of two finite languages which by definition gives a finite sum, and (ii) is the concatenation of two two finite languages which by definition gives a finite product. Thus by the definition of L(R), it is a finite language.

4. Looking Back

Well I know intuitively that this statement is true. I feel that my solution presented,
represents that intuition in a well thought out logical manner.

Week Twelve

2008-11-27T16:33:00.002-06:00

Non-Regular Languages Pumping Lemma

Wow...this stuff gets complicated fast. This is one of the most difficult things we have covered.
Hopefully the exam will not contain too much of this.

Week Eleven

2008-11-20T13:20:00.000-06:00

A3

Well, A3 went rather well. It was not the most difficult assignment, dare I say the easiest.
I guess Danny went a little light on us, knowing that everything was crashing down around us.

NFSAs, Equivalence

I guess it was only a matter of time before induction was brought into this aspect of the class. It seems that whatever we do induction is either there or hiding around the corner. It's not that I mind, its just...tiresome I guess. NFSAs just seem to be just another extension to what we are doing, again nothing too difficult.

I actually really enjoy creating these "machines" and look forward to seeing them later on. I heard that CSC324 is programming these. I am enrolled in that for this coming winter semester.

Anyways, A3 not too bad as with NFSAs.

Week Ten

2008-11-15T08:34:00.000-06:00

Regexes, FSAs, Assignment 3, PS5

Regular expressions: they do not seem to bad. Just an extension of the idea of a formal language. It is weird that we are doing this at the same time in CSC207 as well. They are not bad there, so I cannot think that they will be too bad here. It seems that they have similar algebraic propreties as regular variables, I will just have to work out the priority rules for myself.

FSAs: Pictures for proofs! Like with regular expressions I am having a good grasp on this concept.
State invariants look like they might give some trouble.

PS5: I was able to write up a quick proof on this on Wednesday. I took it to the help center and fine tuned it there with two base cases. All in all the concepts for it were not difficult, and it was quick to do.

A3: I have not started it yet. I will probably be able to look at it after this Wednesday.

Week Nine

2008-11-08T10:36:00.002-06:00

Formal Languages

This section seems to have peculiarly fallen into place with an assignment in CSC207 where we are dealing with lots and lots of strings with different conditions.

I do not really know what to say about all of this. The concepts of it are not new; set theory and induction. I will have to wait and see how it goes. It does seem very interesting, and the course seems to be finally diverging from CSC165-esque material.

Week Eight

2008-11-01T10:31:00.002-05:00

Iterative Correctness:
It seems that the next step in program correctness is tricky.
I find difficulty coming up with loop invariants, and setting up my induction to work properly.
The only way I can do any of these problems is to logically think about what is happening and try to explain it. I will need to get help with these.

Week Seven

2008-10-25T10:20:00.000-05:00

First things first, Term Test 1:
During the test I thought that it had gone pretty well, however receiving it back and seeing my mark, that was not the case. It would appear that more work was needed to be done on my part. I do fairly well (above average) on the problem sets and assignments, it just seems that in a test situation I do not do very well. I need a lot of time to think a problem through and come up with a proper solution.

Program correctness:
The concept of program correctness does not seem very difficult. I personally cannot see it ever being applied in the real world as is. What I mean is that in a job it will never be asked of the programmer to prove his program correct. However, I see that the concepts of it can be applied readily everyday. Just thinking about the preconditions and the post conditions of your program will keep you on the right track, and maybe help you find some bugs or problems.
Again this does not seem to be mathematically rigorous, but I am sure that it can get tricky

Week Five

2008-10-13T10:44:00.001-05:00

This week we did closed form of recursive functions.
To be honest I did not truly understand, and also did not seek to understand. That would be because of the term test on the Friday. So this week, I will have to take a closer look at all that was done last week.

So with that out of the way, to the Term Test.
I felt that it was very fair, and while not too difficult it was challenging. On two of the three questions, I only managed to get most of a proof written out, leaving out some of the crucial algebra steps. I did mention that they were left out due to time constraints, so I wait to see what my mark will be like.

Week Four

2008-10-05T14:12:00.004-05:00

Recursive Definitions

This week seemed to be dedicated towards recursive definitions.
I remember the first time I saw a recursive function, while it did seem natural it also had an unnatural feeling about it. The same still applies in this course. The only issue however is I find difficulties with expressing recursion mathematically.

In class when we were discussing some of the generic functions, then later the Fibunacci sequence, I was unable to visualize what was happening. The "unwinding" which is supposed to make things jump out, to me seems confusing. It also seems, not that these patterns are there, but we find them because we are looking for them.

Term Test One

Also this week, it was brought to the class' attention that the first term test will be held on Friday of next week. While I knew that this was the case, and even had it written in my calendar, I suppose that the mention of it just made it not just an event in the near future, but something important and soon. I am a little nervous about it. I was able to complete both problem sets, and the assignment, only with the help of classmates, TAs and course notes. As of now, I am not ready to write a test, but I do have a week to prepare. We will see what happens then I suppose.

Week Three

2008-09-27T08:52:00.004-05:00

The third week has finished. We continued on with more induction "flavours".

I enjoyed Friday's lecture, it was a nice change of pace. Instead of doing straight forward proofs, what happened was there were three examples of proofs, and each "proof" had something wrong with it.

Was simply not true, however if the conditions were altered by one, then it made the invalid proof valid.
A proof that a pair of hexagons will not have different amount of sides. I am still uneasy/unsure about the point of this proof, and what exactly was wrong with it. Must look into it.
A proof that any FBT has n-1 nodes then one with n-nodes is also an FBT. This proof, as with the first was simply not true. However with a few minor alterations, it turned into a valid proof applicable to any tree.

My only worries with the introduction of these types of problems is that they become valid test questions. Personally when I am writing a test and it says "Prove" I try my hardest to prove it, even if I think it may be untrue. I guess it is to further develop our analytical skills, and make judgments for ourselves.

So overall, a nice (more like frightening) twist in the course, and it should make things interesting.

Also, I still need to finish Assignment one, but I do have an outline proof for each problem, so it should not be too worrisome.

Week Two

2008-09-23T16:40:00.002-05:00

With an end to week two, came the first piece of work worth marks. I feel pretty confident on my proof for Problem Set one. At first the concept of Unit Digits kind of threw me off (with the help of the new proof style). At the end though I feel confident I did well, and I also feel confident with the course material thus far.

We mainly focused on proofs (or versions of them) that were done in CSC165, so far though progressively getting more difficult, nothing unbearable.

I look forward to working on PS2 and A1.

Week One

2008-09-15T20:53:00.000-05:00

With the start of a new school year comes new headaches. New courses, new expectations.

Looking back at my previous notes for CSC165, the work does not seem foreign, however it is definitely not fresh. As of writing this though, it has started to come back in moderate technicolor.

While I cannot imagine the expectations of the teaching staff this year, to make quite the drastic jump they did when moving from Secondary School to First Year, I do imagine a jump. The new expectations for this course (when compared to 165) seem to be a little more. The proof structure has been relaxed, allowing for more leeway and potentially bigger mistakes, by loosely using "assumed" knowledge, I see room for large errors. Hopefully I will not be one to be using the words, "obvious" and "trivial" in my proofs.

So to get into the course work covered thus far.

We have mainly been doing Principle of Simple Induction proofs. While not too difficult they are certainly not slight. Wrapping my head around proper base cases, that is base cases that are of use to the proof, seems to be most difficult. Other than that there have been no problems, and none that could come up, that cannot be handled by my self or with the help of ... the ... er ... "helpers".

I have actually been looking forward to this class over the summer. I am sure, like 165, it will surpass my expectations, and be a great experience.