As the last term test came and gone, I felt compelled to blog my experience with the course and lecturer. I have never been the "theory-guy", but more like the "coding-guy". That's why I have enjoyed all the programming courses up until now, CSC108, 148 & 207 and I also did full time database programming for the last 4 years for my employer. My interpretation of theory has always been this one word, "math", which I admit, is not my strongest subject. But I think my experience in the past 2 terms undertaking PHL245 and CSC236 have changed that a bit. PHL245 focused more on predicate and sentential logic and drew my interest to theories for the first time. And I will now attempt to describe my thoughts on various topics covered by CSC236 this term.
The twins: Simple induction and Complete induction. They were like twins to me at first, I couldn't distinguish between them and didn't know how to choose the correct "flavor" of induction for the questions in hand. So I used mostly Simple induction and that caused me some trouble in test 1 where complete induction where needed for to prove the Fibonacci series. I lost style marks for using Simple induction format when the actual technique used was complete induction. After trying out many examples, I finally got the hang of it, I think.
PWO(Principle of Well-ordering): My lack of understanding of this principle and misunderstanding of the concept of the round-robin tennis game confused me for a whole week before Danny got through to me during one of his office hours. I would say this principle is handy but specific only to proving least element in a set.
Recursive functions: one of my favorite to write when I'm actually coding. So I understood the concept right away(I'm pretty sure so did rest of the class), and I think Danny took it to a higher level with programs such as RecBinSearch, who could forget.
Program correctness, pre-condition, post condition: I have always thought what the program does can be proved in a couple of sentences. But the course taught me by using the concept of pre- and post- condition, we can break a program down to its definition and prove its correctness . I first had trouble on proving the program terminates. But after reading examples in the book, I realized how the conditions when the program terminates help in conjunction with the postconditions to prove the program's correctness.
Formal-languages, RE and FSAs: I have to say my favorite part of the course. Not only were diagrams introduced, which I found entertaining, this section explores the linguistics of a programmer's favorite numbers, 0s and 1s. Which reminds of a joke. "There are only 10 kinds of people in this world, those who understands binary and those who doesn't." I got to prove first hand equivalence of languages and REs. And to create new languages and REs by binary string operations. I also enjoyed coming up with various DFSAs and NFSAs for various invariants. And then using Cartesian product to construct a combination of 2 FSAs.
Context-free grammars(CFG): from what I have read so far, this section explores the world of linguistics, better study this before the final exam. =p
Overall, this course along with a great lecturer in prof. Danny Heap who I owe a great big "Thank You", has showed me that theories in computing need not to be boring math and can be interesting once you learn the tricks and mastered the skills.
Last thing. Sorry Danny, but I'm still not a blogger. I don't know why but when I sit down in front of a screen and try to blog, complete sentences carrying my train of thoughts are just beyond me some of the time and it takes me literally hours to write out something useful. Maybe I should submit an actual diary next time you are teaching a course requiring sLOGs and I'm in it, lol
ps, every time I think of the words, theories of computation, I keep remembering how prof. Jim Clarke use to tell the story in CSC207 of the "earlier years", when all programms were developed on paper, then punch the appropriate holes on data cards and running them through THE COMPUTER. Every time I think of this, I keep picturing myself doing that and it brings me a smile to my face =)
No comments:
Post a Comment