End of a great course.

Well, as the semester comes to a close, the last day of classes completed, it is time to reflect on how this course has helped me change.

I had high expectations as to where I would be right now. I expected my theoretical/mathematical background to evolve exponentially, as the material would not only take me further, but bring back where I left off in CSC165 three years ago before I left for the life sciences. I feel that while I did evolve, realistically I realized I had set the bar too high. Let me point out that this has nothing to do with the course material or administration, it is merely a personal thing.

I struggled through aspects from the course, mainly induction. I found it difficult to visualize mathematical relationships and concepts in my head. However, when I sat down and thought it through for a while on paper, I was able to work it out. While this strategy worked on Assignments, during tests I took a critical hit.

My favourite topic of the course? FSAs. From what I have described above, it's obvious why. Drawing out machines using good 'ol fashioned paper and pencil allowed me to visualize the mechanics behind what our goal was. Not only that, but they rarely required proof, haha.

These FSAs helped me discover that I'm a visual learner, and need to have a paper and pen ready to map out what I'm working towards. This led me to the discovery that I'm disorganized, and that drawing things out on paper aided my focus. You may have noticed that my first Slog entires were a disorganized mess. I hope I have improved since then. I guess you can say that In addition to gaining knowledge of the course material, It was a victory on the personal front too, but not what I expected.

I have begun to study for the final, taking plenty of paper to write out my thoughts first before directly diving into a proof.
The worked problem examples given in the Slog handout are indeed helpful, and while I did not use them on this Slog, rest assured I am putting them to good use, haha.

It has been a long day, and an even longer semester. I mentioned that I was struggling with the material, but I sat down to review and I understand now what's going on. The topics in the course have got me excited for the continuation course - CSC263. I feel that I just need more practice to build up my speed and to help me recognize patterns easier.

Thank you for an amazing experience.

A3

Since it's the last day for the Slog, I assume it's ok to now post the entry I wrote a couple of weeks ago about A3. Also, I figure no one will find this anyways. The email said we couldn't post it on the bulletin board :p

I wanted to work through Question 3, something I had my doubts about.

The question was to prove that for any Regular Expression that does not include a kleene star (*), denotes a finite language. I felt that while the question seemed obvious, it was difficult to prove.
After spending a long time thinking of a decent way to prove it (procrastinating by working through problem 3), I had an idea. I won't give the direct proof, just the outline of what I did.

I devised a plan to literally break it down into smaller (finite) elements.

I thought that if a Regular Expression R is defined by structural induction, then there must be a way to break do break R down into smaller Regular Expressions such that:

R = (R_1)(R_2)...(R_n) for all n in the natural numbers n.

Now, if R did not include a kleene star, then obviously the smaller (R_n)s do not either.
Thus, since we are using our alphabet of /Sigma = {0,1}, each of those regular expressions (R_n) must be either: the empty expression, /epsilon, 0, 1, or (1 + 0).

Each of these regular expressions themselves denote a finite language with a length <= 1. Thus, R altogether must be of length <= n. This means that there is a finite length we can assign to strings denoted by the language R.

Thus, with our finite language /Sigma = {0, 1}, our worst case string for a regular expression of length n is that the string is of length n. Since we have two characters in our alphabet, the number of combinations of those two characters is 2^n.

Depending on the length of R, we can see a finite number of strings that R can denote, thus L(R) denotes a finite language.

The only way for R to denote an infinite language is for one of those smaller RegExes (R_n) to contain.. on let's say.. a kleene star.

Context Free Grammars

I find the entire concept interesting to say the least. There is actually a set of rules for a language that can denote a sandwich. I plan to head to subway with a large index card printed with rules on the front and point to it as I order. But the guy behind the counter could create some kind of infinite sandwich which will end up costing me a pretty penny.

Anyways, I did notice that the example with "a mat beside the dog and a cat saw the mat" was... was close enough to a perfect sentence. BUT, It does get really close to that lolspeak crap that everyone on the internet uses these days.

A simple example: Internets, Intarnets, Interweb, Intarweb, lol internet etc.

S-> CABC
A -> Inter | Intar | Inner
B -> web | net | webs | nets | tube | tubes
C -> lol | ""

Oh man, now I feel retarded. I was about to post a more complex example but my IQ dropped dangerously into the zone reserved for Microsoft Fanboys and /b/tards.

Anyways, another thought. If you had a room full of monkeys and Context free Grammars, eventually they would produce the works of shakespeare.


edit: also waiting for approval to submit A3 related posts I have stored up.
edit2: looking at what I wrote a couple of days later, I realize I may have done something wrong.

Regular Expressions

I am finding this section of the course to be the most satisfying. I find RE's are a material I can grasp a little easier and thus am enjoying writing the problem sets. I even looked over the assignment and it seems to be easier than A2 or A1. Normally when I begin an assignment, I print it out and mark in red my thoughts and ideas before seriously attacking the problems. A3 is a sea of red to my eyes.

Or it could be that I received my A2 mark and it was decent, boosting my morale. Or the fact that I somehow managed to get a perfect score on a problem set for once, a pretty decent achievement for someone with a logic deficiency.

Lately I've been trying to develop applications for the iPhone platform. A regular expression checker came to mind. Then the entire idea of writing software specifically for UofT students came next. Software to aid csc students. I like where this is going. There's no better way to understand the material I'm being taught than through application.

Or maybe I'm dreaming too hard.

Epic Fail.

Well, Assignment 2 and Midterm 2 have come and gone. Overall, I found them both fair.

...Although I should have spotted earlier that one of the functions in question one was the Fibonacci sequence. I remembered as I was doing question 2, but somehow forgot it by the time I got to question three. Note to self: write all epiphanies down immediately.

Knowing that it was a fibonacci could have made it easier to prove. Instead I wrote T(n) down on the leftside and 2F(n+1) -1 on the rightside and tried to unwind them both. I know I'm doing something wrong there. Perhaps I still don't understand the final goal, I need to do more proofs as practice. Me attempting to unwind (always a slow process to me) took the majority of the test and I stupidly didn't leave enough time for the other questions. Perhaps just enough time, I did finish them, but that doesn't mean they're correct. I know I can do it (I managed to do it on Assignment 2). Speed is my major issue. I will work on that for Test 3 and the final.

Entry 2

I've been so busy recently that I've forgotten to update this page in the past few weeks. That will change, I've set my google calendar to remind me. Anyways, a few thoughts about what has happened so far.

Term test 1 came and went. I think my performance could have been better. While I feel a little more confident in my proofs, I think I don't have the speed to complete them efficiently with the clock ticking. I have started to do more proofs on the side from the book to gain a little bit more experience in order to lower the time it takes to write them. I also plan (after my next midterm on thursday) to go back to my CSC165 notes which I took 3 years ago to go over the techniques once again.

I have also realized that it is my poor math skills are also a hindrance when it comes to finding the connections in proofs. I have brought out my old calculus book and plan to use it as I go through any future proofs.

Bring on Assignment 2!

First Entry September 30, 2008

So far, I honestly don't have any topics to post about. It could be the high fever I'm currently experiencing, which could also affect what I"m writing here as well.

We have covered the flavours of induction, yet my mind draws a blank when I try to come up with any opinions on them. However on the topic of proofs, I think I realized why I'm terrible at them.

I noticed that I never seem to ask the question, "Why?" or "How?". If someone told me that I could make a certain postage out of a strange denomination of two stamps, I would believe them. I wouldn't second guess it. I'd just ask to myself, "why would you go through all the trouble of using those stamps when you can just use one stamp with the full denomination?". Or I'd be really lazy and just use the stamps in combination to form a postage that is higher than what I'm supposed to be paying.

Apparently, I do this with everything, and it's something I need to unlearn. Because of this, I have a hard time forming the logic behind these proofs. Perhaps if I took the time and patience to ask more questions about how things around me function, and if I use this course as a tool to practice my proofs, I can develop a more logical mindset.