CISC 7221X Theoretical Computer Science

37 hours plus conference and independent work; 3 credits

Overview of theoretical computer science. Finite automata and pushdown automata, grammars, Turing machines, the Halting Problem, unsolvable problems. Time complexity, space complexity, complexity classes, P, NP, NP-Complete, PSPACE, EXPTIME. Not open to students who have completed a course in theoretical computer science.

Prerequisite: a course in discrete structures. .


The City University reserves the right, because of changing conditions, to make modifications of any nature in academic programs and requirements of the university and its constituent colleges without advanced notice. Students are advised to consult regularly with college and department counselors concerning their programs of study.

Access the college's current and recent course bulletins.