My English prof always told me to use an interesting title

One more class remains in this semester, and, coincidentally, the last CSC236 test will be written on the same day. I'm somewhat worried about it, especially since there are no previous tests to study from. The professor assures us that they wouldn't be much of a lifesaver, so I'm just going to cram using the course notes tonight.

Since the end is so near (and the due date for the SLOG is tomorrow), this will likely be my last entry in this journal. I'd like to take this opportunity to thank professor Heap for being an excellent instructor. I definitely consider the knowledge gained to be a huge asset in my CSC toolbelt. CSC236 is the perfect example of how technological aids can benefit the learning process. My friends' description of CSC236 being a boring, unfair, and unsatisfying course has proven to be false. I'm sure their experience with the course would have been much different if it had been taught by proffessor Heap. I hope to have more courses with him in future semesters.

Good luck on your exams and have a good holiday break!

Cartesian product

I have really learned to appreciate the problem sets. They are excellent practice for the material in class, the assignments, and the tests. I almost wish there were more of them, but I understand that it would increase the workload for the marker (and having the problem sets returned to us with feedback, quickly, is highly appreciated).

I'm certainly finding that this course is better structured than CSC165, especially when it comes to the tutorial part. In 165, we had to find partners and spend an hour working on a problem. The problems were often left unsolved and student attendance dropped significantly towards the end of the semester. The approach used in CSC236 certainly yields much better results.

One topic I wish there was more focus on is Cartesian products. It would have been especially helpful for assignment 3. Although there is some coverage of it in the course notes, I'm having a tough time applying the same methods when working on the assignment.

Regular expressions

Although I've ran into regular expressions before, I have never looked at them quite like this. In Perl, I used to use regex to parse strings. Although in class we're dealing with things that seem different (transition functions, start states, etc... are all concepts I've never dealt with before), the end result is the same. It's just a different approach -- one that yields itself to proofs naturally.

I've played around with regex testers before (such as the one in eclipse), however I've never seen anything quite like the visual DFSA builders shown in class.

Problem set 5 was slightly difficult. I could see two ways of solving it. The first was the utilize the concept of length or magnitude. For example, if there is a language of k strings, then there is a regular expression that denotes that language. The alternative approach was to use some form of structural induction. The latter seemed more natural to me, however I have not had much practice with it, so I'm afraid it wasn't perfectly correct. I submitted both approaches, and I am anxiously awaiting to see the markers comments.

Problem Solving Episode

Since the topic of the week has my full attention (as I mentioned in the previous post), I've decided to make my SLOG's problem solving episode on this week's problem set (#4). The problem is as follows:

Prove that the python function revString(s) is correct with respect to
its precondition/postcondition, or else provide a string that
satisfies the precondition, but for which the postcondition fails.

# Precondition: s is a python String
# Postcondition: revString(s) returns a string with
# the characters of s in reverse order.
def revString(s) :
if len(s) < 2 : return s
else : return revString(s[1:]) + s[0]

My initial attempt at this problem involved the use of simple induction. I ran into a number of uncertainties about how to solve this problem, so instead of handing it in on Friday, I decided to go to Friday's lecture, extract as much as I can from that lecture to help me with the problem, and then hand it in on Monday. Sure enough, the examples covered in Friday's lecture clarified most of the uncertainties I had before.

My first dilemma was whether to use simple or complete induction to solve this problem. I believe this was the first problem that I wrote where I had to prove a recursive function by utilizing the length of the argument to that function (string s). The examples covered in class used strong induction, however they depended on multiple previous cases (P(n-1) and P(n-2)), while this problem only depends on P(n-1). Regardless, I could see how I could fit this problem into the template of complete induction so I went ahead:

P(n): If n = len(s), the precondition implies the post condition.

Claim: \forall n \in N, P(n)

This is where I ran into another technicality -- whether to place the assumption statement for complete induction before or after the base cases. After a quick chat with one of the TAs in the undergraduate help center I decided to write the base cases before the assumption statement:

Case n = 0:
Then the condition on line 1 succeeds and we return s. Since the length of the string s is 0, s must be the empty string, and the reverse of the empty string is just the empty string. So P(0) is true.

Case n = 1:
Then the condition on line 1 succeeds and we return s. Since the length of the string s is 1, s must contain only 1 character, and the reverse of a single character is just the single character. So P(1) is true.

I used only 2 base cases because we are dealing with natural numbers (0, 1, 2, 3...), and the code has an If statement which encapsulates any number less than 2. Which leaves us with only two possibilities: 0 and 1.

And here is the previously mentioned assumption statement, followed by the rest of the proof (which I chose to write as just another case for the remaining natural numbers):

Assume n \in N, P(0) ^ P(1) ^ ... ^ P(n - 1)

Case n > 1:
Then the condition on line 1 does not succeed and we proceed to line 2. Line 2 returns a string comprised of two parts:
- The reverse of the string s excluding the first character (we know this is true by our induction hypothesis -- P(n-1) is the case when the length of the string s is excluding the first character, so n -1).
- The first character of s (which must be the last character to be returned since it is the first character of s)
Combined, the two parts return the reverse of the string s. Then P(n) is true.

So \forall n \in N, P(0) ^ P(1) ^ ... ^ P(n - 1) => P(n)
So \forall n \in N, P(n)

Problem Set 4 / Week 7

We have finally reached the point of the course where we analyze (prove) program correctness. Although it's nothing more than a natural progression from the proofs that we have done previously, it does bring me some joy to be working with actual code (not just algorithms). This is largely because I'm specializing in Software Engineering, so I anticipate that I will be working with actual code throughout my career. I am, however, aware that all code is just algorithms in disguise (that disguise being syntax, and possibly context).

Although we have only spent one class on program correctness, I have already completed problem set 4, which required us to prove that a program (python function to be precise) is correct. I did wish that we have had a few more examples from the class notes to guide us. I am aware aware that the deadline for the problem set was extended to Monday, so I will probably hold off and see what I can take away from Friday's class. I also intend to stop by the U of T bookstore tomorrow to see if they have any more of the course books available for purchase (it couldn't hurt to have some extra examples on hand to study from).

Test #1 Impressions

I was somewhat surprised by how difficult I found test #1 to be. I had spent a considerable amount of time studying for it, and, after looking at the tests from years past, I though I was in good shape. When it came time to write this year's test, I found myself critically strapped for time. I don't think I adequately finished any of the 3 questions, and I didn't even include the IH for the last one.

I guess the lesson is that it's not enough for one be able to answer the questions -- one must also be able to answer them quickly. Part of the fault probably lies in the fact that I usually tend to use fairly elaborate and lengthy explanations. I always try to avoid terse arguments to mitigate any risk of lost marks. I'm looking forward towards receiving my problem sets and assignments back, to see if I can find a formula that allows for shorter arguments without loss of any critical statements.

I have a lot of catching up to do

Everything had been fine up until today's class. Since day 1, I was following along with the prof, understanding about 80-90% of everything he said (which is pretty high for me). Today, however, we touched on several topics that might as well have been presented in a foreign language:

- time complexity analysis
- proofs using logarithms
- big "o" and big "omega" proofs

Albeit these are concepts I've stumbled upon before, I have never fully understood them. As such, most of today's discussion went completely over my head. I feel like I have a huge wall coming up ahead of me for the next week, as I try to find resources and materials on these topics so I can try to understand them for upcoming classes. What worries me the most is that I might not be fully versed in time for the test next week.

Assignment 1 was fairly reasonable. I had previously seen the question on sums of angles within a figure within a circle, so it wasn't too difficult to prove. I actually found the menu problem somewhat fun, as it felt like I was trying to solve some kind of puzzle by coming up with a solution that worked. The phi proof stumped me completely, but a TA made sense of it all. In hindsight, the tips posted by the professor made complete sense, however they really didn't seem to help when I first looked at them.