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:
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"?
Reminder: we are under the Honor codeWhile 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!