CS 311Fall 2008 Audrey St. John |
## COMSC 311 Theory of Computation## SyllabusWhat 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: - Automata and Languages
- Computability Theory
- Complexity Theory
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## Work- Ten weekly assignments.
- Two in-class exams and a final in the final exam period.
## Grading- Assignments 30%.
- In-class exams 40%.
- Final exam 30%.
## Reminder: we are under the
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). |