Theory of Computation
A
AY24/25 S1
You are the computer. Be the computer.
This course is about building logical machines that can solve problems. In particular, the main focus is to build a machine that tells us whether a string should be accepted or rejected. For example, we may want to accept strings with an equal number of a's and b's, where this set of strings is called a language. For this, we need one of many machines you will learn throughout the course.
The simplest is a Finite Automaton, which functions like a state diagram. It reads a string letter by letter, moving through the different states based on predefined state transitions. We can then know whether to accept the string based on which state the machine lands on after reading all the letters. These machines are pretty weak, as the strings they can accept must be able to be represented as a regular expression like ab*a.
That's why we have more powerful machines like context free grammars (which generates the language via a tree-like structure) and pushdown automata (which store memory in a stack).
Finally, the most advanced machine is the Turing Machine, which can theoretically solve any problem.
I'd say there are 3 kinds of questions. The first kind is about creating these machines given a certain language. Define how they work, and give a brief proof that they work.
The second kind is about proving whether a certain language is regular, context-free, decidable, etc. There's quite a number of different techniques to do this, so lots of exposure to questions will help greatly here. Get ready to get your lemma pumped, if you know what I mean.
The third kind is very theoretical, as it talks about hypotheticals. For example, what if we had a machine that could solve the halting problem? What would happen? These types of questions are the hardest, as they require a lot of inspiration and creativity. You need to really cook to get this within the time crunch. So best to avoid answering them.
This brings us to workload. Actually moderate, as you have to do and submit your tutorial online every week. Marked by effort, so don't worry too much. What does matter is the tutorial itself, where Prof will ask you to write your answer on the board. No avoiding this, as 10% of your grade is tutorial participation. And the Prof is brutal too, and will make you feel stupid. It's actually quite effective, as it encourages you to put in effort to your tutorials. So don't be scared of him. He's actually a nice guy.
For assessments, there is CA1, CA2, and the finals, so it's actually a lot to revise. The best thing is that the questions are hard, yet the Prof marks them leniently. That, to me, is the best combo, as most of the time, you will get a pleasant surprise when you get back your papers. As long as Prof thinks you know what you're talking about, he'll give you benefit-of-the-doubt marks. Goated marking style.
Loading comments...