Prerequisites: Math 3336 and COSC 2320. Math 3336 will be strictly enforced.
Textbook
• Introduction to the Theory of Computation by M. Sipser, PWS Publishing Co.
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 com
putation, 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 de¯nitions.
Instructor:
Rakesh Verma.
Office 532 PGH, Ph: 743-3348.
Office Hours for Fall 04: TuTh: 5.30-6.25pm (or by appt.)
TA: TBA
Academic Honesty Policy: Assistance of or Collaboration with any animate or inani
mate 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: Homeworks 10%, Exam 1 24%, Exam 2 30%, Final 36%