UBC CPSC 421 Intro to Theory of Computing

CS 421, Theory of Computing is a course that EVERY computer science student should take.

Professor Nick Harvey is really one of the best researcher and instructor at UBC CS. His classes are very clear and his assignments are challenging and rewarding. You'll definitely learn a lot of useful material in his classes. The grading was also very generous. I took CS 421 in my sophomore year and got 100%.

Basically CS 421 consists of 3 parts.

In part I, you will learn several computing models such as DFA, NFA, CFG, Turing Machine. Then you'll learn computability, like what kind of problems are undecidable.

In part II, you'll learn complexity theory. Topics include Cook-Levin Theorem, NP-hardness proofs, coNP, randomized complexities such as ZPP,BPP,RP, coRP.

In part III, you'll learn some advanced topics in complexity theory. In 2012, CS 421 covered interactive proof systems, and in 2013 it covered communication complexity theory.

I would say take CS 421 as early as possible !!!


Difficulty: 3.5 / 5.0
Quality:    5.0 / 5.0