Reflection on csc236

Since this is the end of term, I've decided to reflect on the course. I came out of csc165 enthusiastic about computer logic. Gladly, csc236 has not wane my enthusiasm. If it wasn't for the pervasiveness of some personal problems, I believe that I would have been doing better in this course. However, it was still my enthusiasm for computer logic that kept me on top of my studies (whereas in my other courses... not so good).

So some things demystified : proof with induction (iteration, recursion), proof of program correctness and formal languages. This course has shaped how I see proofs. It seems to me that almost everything can be proven with induction. Formal languages is proving strings. I can sort of see how this can be applied to computers (regex and DFSA). The variability of CGFs, along with a stochastic model (markov chain?) seems to be a good starting point for recreating human language, hence could be some sort of AI algorithm. I will probably investigate this further during the winter break.

I enjoyed csc236 and Danny as my prof. Hopefully I will see him again in other computer courses I am going to take. :)

Polya's problem

This was taken out of the CFG problems section of the textbook.

Problem : Prove that the following CDF generates the set of strings over {0.1} that have equally many 0s and 1s.
S -> 0S1S
S -> 1S0S
s -> E

1. Understanding the Problem:
We need to prove that the CDF gives a string with equal number of 1s and 0s.

2. Devise a Plan:
I'll probably have to use three cases, one for 0S1S, 1S0S and E. I'll also need to use induction (simple)

3. Carrying out the plan:
Base Case: If S -> E, then there are no 0s or 1s. That means that there are equal numbers of 1s and 0s.
Inductive Step: Assume that S is of equal number of 1s and 0s by IH.
Case 1S0S: Let the string be 1S0S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
Case 0S1S: Let the string be 0S1S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
By all cases listed above, this CDF produces the same number of 1s and 0s.

4. Looking Back:
I think this result makes sense. There lacks a structure, but the logic is still retained.

regex and FSA

We're doing regular expressions in both csc236 and csc207! One interesting point that prof Heap brought up was that (empty set)* = empty string. This is a very non-intuitive and interesting. And I LOVE the material in this week's lectures because it very visual. I'm very eager to find out how to prove one of these graphs...

after the test

The test on Thursday wasn't too difficult. However, I realized that I made a mistake in the last question, of which the loop iteration is supposed to prove that the variables were natural numbers so that I could use the principle of well ordering to say that there is a lower bound to the set. Instead, I proved that the values in the loop iteration was always descending, which shows that the set is monotonic. However, I forgot that the principle of well-ordering presupposes that the set is of natural numbers. I doubt I'll forget this for the exam now... =.=

Before the test

It's only 3 hours before the test! Last week's lecture on loop invariance was a bit hard for me to follow, but it was fairly intuitive. I think I understand the concepts, but just need to touch up on the set of skills to express the concepts. However, I find it hard not to just memorize these... -.-

Correctness of Code

This week we talked about the correctness of code. I thought that this was interesting in the sense that we are subconsciously using these algorithms to check our of code. In a sense, we are just training our mind to be like a debugger.
I also thought that the assignment was fair. Most of the questions are straightforward (except the ternary tree question). The second question was a challenge as well because I don't feel like I've grasp time complexity well.

It has been a while

I had almost forgotten about slogs for the last couple of weeks (oh no! there goes my slog mark). Anyways, to recap what we've done: closed form for recursive functions, structural induction, merge sort time-complexity and the master-theorem for divide and conquer. I need to look over last week's notes as I found the concepts sort of difficult to understand. Now that most of my midterms are over, I should be able to find time for this (and for catching up on my slog -.-).