CS 311
Fall 2008
Audrey St. John

COMSC 311 Theory of Computation


What can a computer do? What problems can be solved and are some more difficult than others? Are there problems that a computer cannot solve?

In this course, you will learn to analyze computational problems within formal mathematical models of computation and begin to understand answers to these questions.

The textbook for this course is Introduction to the Theory of Computation by Michael Sipser. As in the text, the course will roughly be divided into three parts:
  1. Automata and Languages
  2. Computability Theory
  3. Complexity Theory
In the first part, "Automata and Languages," you will be exposed to limited formal models of computation. This will allow you to gain experience reasoning within a mathematical model and proving properties about it. During this part, we will be learning about regular languages and context-free languages. How much can be expressed in each type of language?

The second part, "Computability Theory," explores the question of what limitations a computer has when solving problems. Are there problems that a computer provably cannot solve?

Finally, we will look at "Complexity Theory" and begin to reason about a formal notion of "how difficult" a problem is. Are some problems easier than others? Are some of the same "difficulty"?

Course Requirements


  • Ten weekly assignments.
  • Two in-class exams and a final in the final exam period.


  • Assignments 30%.
  • In-class exams 40%.
  • Final exam 30%.
For the final grade, you have the option to choose one out of the assignments - presumably the one with the lowest grade - which will be dropped from the final average computation. However, you can only choose to drop a homework for which you did the work. If you miss a homework you get 0 points on it (and that will count towards the final average).

Reminder: we are under the Honor code

While I encourage you to talk to your class mates about the assignments and organize study groups, I also have to remind you that all the work that you submit should be yours! It is against the honor code to have somebody else do the assignment for you (including tutors) or to copy it from somewhere else (including books or the internet).

Please be sure to write at the top of each assignment anyone you discussed the assignment with.

Lateness Policy (or lack thereof)

NO late homework will be accepted, except for very special, documented circumstances. Assignments will be due at the beginning of class (usually on a Monday); paper submissions or online submissions via Ella are acceptable.

Thanks to Randy Shull for so generously letting me use his notes from his version of this course!