» syllabus
Download
Prerequisites
Math 3336 and COSC 2320. Math 3336 will be strictly enforced.
Books and References
Textbook
- Introduction to the Theory of Computation by M. Sipser, 2nd ed. Thomson Course Tech.
References
- Elements of the Theory of Computation by H. Lewis and C. Papadimitriou, Prentice Hall, First and second editions.
- Introduction to Automata Theory, Languages and Computation by J. Hopcroft, R. Motwani and J. Ullman, Addison-Wesley, 2001.
Goals
To provide computer science students with a broad understanding of various models of computation, several different characterizations of the power of each model, and the relative power of the models. Students are taught what can and what cannot be computed even by idealized computing devices. They are exposed to essential computational paradigms in a rigorous way.
Topics
- Finite Automata and Regular languages
- Pushdown Automata and Context-free languages
- Turing Machines
- Church's thesis, Grammars, Universal Turing Machines
- The Halting Problem, Turing-Acceptability, Turing Decidability, and Unsolvable problems about Turing machines
- Cardinality of sets, Proof techniques, and basic defnitions
Academic Honesty Policy
Assistance of or Collaboration with any animate or inanimate object (except the instructor and the TAs) is completely disallowed on all exams; any violation will be severely penalized with the minimum penalty on FIRST violation being an F grade.
Grading (subject to change)
- Class participation - 3%
- Homeworks - 10%
- Exam 1 - 10%
- Exam 2 - 20%
- Term Paper - 10%
- Final - 47%