CPSC 421/501 (Introduction to Theory of Computing)


Introductory course on automata theory, computability theory, and complexity theory.



Prof. Nicholas Harvey, Office: X851, Email: nickhar@cs.ubc.ca

TA: Sharan Rajesh Vaswani, Email: sharanv@cs.ubc.ca


Webpage: http://www.cs.ubc.ca/~nickhar/F13



·         M. Sipser, Introduction to the Theory of Computation. 3rd edition preferred, 2nd edition also OK.

·         Frequently Asked Question: Is the textbook mandatory for this course?

o   Short answer: Yes.

o   Long answer: Yes. This is a superb book. I would rank it as one of the top-three best-written computer science texts that I know of. Unfortunately it is quite expensive. Fortunately I am allowing you to use the older edition which you can probably find used. Unfortunately that is probably expensive too. There are two reasons that it is mandatory: (1) the exercises will be taken from this book, and (2) for the purposes of the exams, you will be responsible for knowing the material in the relevant sections of the text. I cannot guarantee that my coverage of the material in class will be as comprehensive as the coverage in the textbook.


Grading Scheme

CPSC 421 students

·         20%: Assignments

·         30%: Midterm

·         50%: Final exam

CPSC 501 students

·         15%: Assignments

·         25%: Midterm

·         40%: Final exam

·         20%: Project




The most important prerequisite for this course is the ability to write a logical proof, especially an inductive proof. I also expect you to be familiar with the following concepts:

To review these topics, see the first chapter of the textbook, or Lehman, Leighton and Meyer Ch 1-5, 11, 13.


Academic Misconduct

Submitting the work of another person, whether that be another student, something from a book, or something off the web and representing it as your own is plagiarism and constitutes academic misconduct. If the source is clearly cited, then it is not academic misconduct. If you tell me “This is copied word for word from Jane Foo’s solution” that is not academic misconduct. It will be graded as one solution for two people and each will get half credit.

I encourage you to discuss the homework problems with each other outside of class. You can help each other understand the concepts and techniques needed to solve the problems, and you can brainstorm together to figure out ideas for solving the problem. If you come up with the actual solution yourself, that’s fine. If you’re brainstorming with some friends and the key idea comes up, that’s OK too – in this case, just add a note to your solution that says something along the lines of “{Names of people in brainstorm session} and I were discussing this problem together and came up with the idea of {state the key idea from the brainstorm here}”.

If you say that you got it off of the web or from another text, you’ll be graded by the extent to which your solution shows that you actually understood the solution that you found and were able to reformulate it using your own reasoning.

If you get a solution by any means other than working it out yourself and don’t disclose it, then I will follow the university procedures for academic misconduct.

Please read Cheating: The List Of Things I Never Want To Hear Again