The City College of New York • Grove School of Engineering • Computer Science Department • Course Syllabus
Course number | CSc 30400 | Course name | Theoretical Computer Science |
Credits & hours | 3 cr., 3 hr. | Course coordinator | Prof. Stephen Lucci |
Textbook, title, author, and year
- One of Introduction to the Theory of Computation, 3rd Ed, Michael Sipser, 2012, Elements of the Theory of Computation 2nd Ed, Lewis and Papadimitriou, 2007, and Introduction to Automata Theory, Languages and Computation 3rd Ed, Hopcroft and Motwani, 2006
- Other supplemental materials: additional matierials provided in class
Specific course information
- Finite state automata, pushdown automata, Turing Machines, and the languages they can recognize. Church's Thesis. Computability. The classes P and NP; NP-complete problems and intractable problems.
- Prereq.: CSc 10400 and CSc 22000
- Required course
Specific goals for the course and Relationship to student outcomes
| |||||||||||||||||||||||||||||||||||
|
Brief list of topics to be covered
Seq. | Topics |
1 | Mathematical notions and terminology - brief review |
2 | Types of proofs |
3 | Regular languages - finite automata, nondeterminism, regular expressions, non-regular languages (pumping lemma) |
4 | Context-free languages - context-free grammars (including ambiguity and Chomsky normal form), pushdown automata, non-context-free languages (pumping lemma) |
5 | Computability theory - Turing machines (including the Church-Turing thesis) |
6 | Decidability - decidable languages, undecidability (diagonalization) |
7 | Complexity theory - reducibility, P, NP, NP-completeness (several examples, including the vertex cover, Hamiltonian path, and subset sum problems |
8 | Cook-Levin theorem usually remains just beyond the reach of the semester |
Last Updated: 05/22/2018 20:04