Introduction to Theory of Computing

“Let me start off by telling you a fact without enough background to prove the fact”

Text: Introduction to the Theory of Computation by Michael Sipser

Prof:  Dr. Nick Harvey

Dr Nick Harvey is a very clear professor. He makes effective use of slides and slowly explains complex topics, making his lectures both interesting and easy to follow. For example, his explanation of the diagonalization argument was much clearer than any of the presentations on the same topic I have received in math classes. He also has a peculiar sense of humour and is a big soccer fan, so the class is interspersed with entertaining distractions.

---

Difficulty

The material starts with fairly simple with a bit of review from CPSC 121. It picks up a bit when you start performing reductions between problems from various complexity classes though there is a bit of recap from CPSC 320. The first midterm was straightforward, however, given its short length it was possible to not to do as well if one tripped on only one or two questions. The final was a bit harder, however, the previous exam was good preparation.  The homework included some questions that could be genuinely hard to understand. However, he gave generous hints as the deadline approached, and they were the type of questions that once you understood what the question was asking, the proof was often one of the first few obvious approaches that you would think of. Given that he dropped the lowest couple of homework, it’s no surprise that the overall average in the course was 80.

Key Concepts

Finite Automata and Regular Languages

Turing Machines

Non-determinism

Time complexity classes

Mapping Reductions

Probabilistic Turing Machines

Communication Complexity and Fooling sets

Hard Concepts

Context Free Languages: Can be hard sometimes to come up with CFG or PDA for a given context-free language

Probabilistic Turing Machines: Give rise to quite convoluted complexity classes.

NP-Hard reductions: Might require a bit of imagination to come up with the reductions, at times.

Fooling Sets and Covers: One can sometimes get fooled by these, make sure one recalls the definition of rectangles and what exactly needs to hold for a fooling set.

 

Conclusion

Fun course. Dr Nick Harvey can make the course appear deceptively simple at times, but you actually learned a lot of quite complex material.